1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Afsnit 3 - Mere behagelig]

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ørgsmål er mærkeligt formuleret.

5
00:00:12,700 --> 00:00:17,480
GDB lader dig "debug" et program, men mere specifikt, hvad betyder det lade dig gøre?

6
00:00:17,480 --> 00:00:22,590
Jeg vil svare, at én, og jeg ved ikke, hvad der præcist forventet,

7
00:00:22,590 --> 00:00:27,910
så jeg gætte det er noget i retning af det lader dig trin for trin

8
00:00:27,910 --> 00:00:31,540
gå gennem programmet, interagere med det, ændre variabler, gøre alle disse ting -

9
00:00:31,540 --> 00:00:34,270
dybest set fuldstændigt styre udførelsen af ​​et program

10
00:00:34,270 --> 00:00:38,410
og inspicere enhver given del af gennemførelsen af ​​programmet.

11
00:00:38,410 --> 00:00:43,030
Så disse funktioner kan du debug ting.

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

13
00:00:44,830 --> 00:00:50,520
Hvorfor binær søgning kræver, at et array skal sorteres?

14
00:00:50,520 --> 00:00:53,360
Hvem ønsker at besvare dette?

15
00:00:56,120 --> 00:01:00,070
[Studerende] Da det ikke virker, hvis det ikke er sorteret. >> Yeah. [Latter]

16
00:01:00,070 --> 00:01:04,910
Hvis det ikke er sorteret, så det er umuligt at splitte det på midten

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

18
00:01:07,850 --> 00:01:10,490
er større end den midterste værdi.

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

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

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

22
00:01:17,570 --> 00:01:23,230
Er der nogen først ønsker at give en meget hurtig på højt niveau overblik over, hvad boble slags er?

23
00:01:25,950 --> 00:01:33,020
[Studerende] Du dybest set gå gennem hvert element, og du tjekke de første par elementer.

24
00:01:33,020 --> 00:01:37,150
Hvis de er ude, hvor du bytte dem, så du tjekke de næste par elementer og så videre.

25
00:01:37,150 --> 00:01:40,770
Når du når til slutningen, så du ved, at det største element er placeret i slutningen,

26
00:01:40,770 --> 00:01:42,750
så du ignorere, at man så skal du holde på går igennem,

27
00:01:42,750 --> 00:01:48,490
og hver gang du er nødt til at kontrollere en mindre element indtil du foretager nogen ændringer. >> Yeah.

28
00:01:48,490 --> 00:01:58,470
Det hedder boble slags, fordi hvis du spejlvende array på sin side, så det er op og ned, lodret,

29
00:01:58,470 --> 00:02:03,100
så de store værdier vil synke til bunds, og de små værdier vil boble op til toppen.

30
00:02:03,100 --> 00:02:05,210
Det er, hvordan det fik sit navn.

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

32
00:02:08,220 --> 00:02:11,190
Du holde ud gennem opstillingen, bytte større værdi

33
00:02:11,190 --> 00:02:14,040
at få de største værdier til bunden.

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

35
00:02:18,690 --> 00:02:24,620
Først er der nogen ønsker at sige, hvorfor det er O n kvadreret?

36
00:02:24,620 --> 00:02:28,760
[Studerende] Fordi for hver kørsel det går n gange.

37
00:02:28,760 --> 00:02:32,100
Du kan kun være sikker på, at du har taget det største element hele vejen ned,

38
00:02:32,100 --> 00:02:35,230
så er du nødt til at gentage, at så mange elementer. >> Yeah.

39
00:02:35,230 --> 00:02:41,800
Så huske på, hvad big O betyder, og hvad store Omega betyder.

40
00:02:41,800 --> 00:02:50,560
Den store O er ligesom den øvre grænse for, hvor langsomt det faktisk kan køre.

41
00:02:50,560 --> 00:02:58,990
Så ved at sige det er O n kvadreret, er det ikke O n ellers ville være i stand til at køre

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

43
00:03:02,640 --> 00:03:06,390
fordi den er afgrænset af O n cubed.

44
00:03:06,390 --> 00:03:12,300
Hvis det er afgrænset af O n kvadreret, så er det afgrænset også af n kubik.

45
00:03:12,300 --> 00:03:20,280
Så det er n kvadreret, og i den absolutte værste fald kan det ikke gøre det bedre end n kvadreret,

46
00:03:20,280 --> 00:03:22,830
hvilket er hvorfor det er O i n potens.

47
00:03:22,830 --> 00:03:31,200
Så for at se lidt matematik på, hvordan det kommer ud at være n kvadreret,

48
00:03:31,200 --> 00:03:40,530
hvis vi har fem ting i vores liste, den første gang, hvor mange swaps kunne vi potentielt nødt til at gøre

49
00:03:40,530 --> 00:03:47,170
med henblik på at få dette? Lad os faktisk bare -

50
00:03:47,170 --> 00:03:52,040
Hvor mange swaps skal vi nødt til at gøre i den første kørsel af boble sortere gennem array?

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

52
00:03:53,540 --> 00:03:58,340
>> Hvis der er 5 elementer, vi vil få brug for at gøre n - 1.

53
00:03:58,340 --> 00:04:01,100
Så på den anden, hvor mange swaps skal vi nødt til at gøre?

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

55
00:04:03,440 --> 00:04:11,640
Og den tredje vil være n - 3 og derefter for nemheds jeg vil skrive de sidste to

56
00:04:11,640 --> 00:04:15,270
som dengang vil vi nødt til at gøre 2 swaps og 1 swap.

57
00:04:15,270 --> 00:04:19,899
Jeg gætte den sidste måske eller måske ikke rent faktisk skal ske.

58
00:04:19,899 --> 00:04:22,820
Er det en swap? Det ved jeg ikke.

59
00:04:22,820 --> 00:04:26,490
Så dette er det samlede beløb af swaps eller i det mindste sammenligninger du har at gøre.

60
00:04:26,490 --> 00:04:29,910
Selv hvis du ikke bytte, har du stadig nødt til at sammenligne værdierne.

61
00:04:29,910 --> 00:04:33,910
Så der er n - 1 sammenligninger i den første kørsel gennem opstillingen.

62
00:04:33,910 --> 00:04:42,050
Hvis du omarrangere disse ting, lad os rent faktisk gøre det seks ting, så tingene stak op pænt,

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

64
00:04:44,790 --> 00:04:49,910
Så bare omarrangere disse beløb, vi ønsker at se, hvor mange sammenligninger vi gør

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

66
00:04:52,700 --> 00:04:56,550
Så hvis vi bringer disse fyre hernede,

67
00:04:56,550 --> 00:05:07,470
så er vi stadig lige summere dog mange sammenligninger der var.

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

69
00:05:13,280 --> 00:05:18,130
det er stadig det samme problem. Vi har lige opsummere disse særlige grupper.

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

71
00:05:22,400 --> 00:05:27,650
Det er altid vil være n / 2 n s.

72
00:05:27,650 --> 00:05:29,430
Så her har vi tilfældigvis har 6.

73
00:05:29,430 --> 00:05:34,830
Hvis vi havde 10 ting, så vi kunne gøre denne gruppering for 5 forskellige par ting

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

75
00:05:37,180 --> 00:05:45,840
Så du altid vil få n / 2 n s, og så dette vil vi notere det ud til n squared / 2.

76
00:05:45,840 --> 00:05:48,890
Og så selvom det er den faktor af halvdelen, der sker for at komme i

77
00:05:48,890 --> 00:05:54,190
på grund af det faktum, at ved hver iteration over arrayet vi sammenligner en mindre

78
00:05:54,190 --> 00:05:58,040
så det er, hvordan vi får mere end 2, men det er stadig n potens.

79
00:05:58,040 --> 00:06:01,650
Vi er ligeglade med den konstante faktor af en halv.

80
00:06:01,650 --> 00:06:07,760
Så en masse af stor O ting som dette beror på bare lidt at gøre denne form for matematik,

81
00:06:07,760 --> 00:06:12,260
laver aritmetiske beløb og kvotientrække kram,

82
00:06:12,260 --> 00:06:17,750
men de fleste af dem i dette kursus er temmelig ligetil.

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

84
00:06:19,290 --> 00:06:24,430
Hvorfor er indsættelse slags i Omega n? Hvad betyder omega betyde?

85
00:06:24,430 --> 00:06:27,730
[To studerende taler på én gang - uforståelige] >> Yeah.

86
00:06:27,730 --> 00:06:30,630
Omega du kan tænke på som den nedre grænse.

87
00:06:30,630 --> 00:06:36,550
>> Så uanset hvor effektiv din indsættelse slags algoritme er,

88
00:06:36,550 --> 00:06:41,810
uanset den liste, der er gået i, det altid har at sammenligne mindst n ting

89
00:06:41,810 --> 00:06:44,620
eller det skal gentage over n ting.

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

91
00:06:47,280 --> 00:06:51,190
[Studerende] Fordi hvis listen allerede er sorteret, så gennem den første iteration

92
00:06:51,190 --> 00:06:54,080
du kan kun garantere, at det allerførste element er mindst,

93
00:06:54,080 --> 00:06:56,490
og den anden iteration du kan kun garantere de første to er

94
00:06:56,490 --> 00:07:00,010
fordi du ikke ved, at resten af ​​listen er sorteret. >> Yeah.

95
00:07:00,010 --> 00:07:08,910
Hvis du passerer i en helt sorteret liste, i det mindste du nødt til at gå over alle de elementer,

96
00:07:08,910 --> 00:07:12,180
at se, at intet skal flyttes rundt.

97
00:07:12,180 --> 00:07:14,720
Så passerer hen over listen og siger åh, dette allerede sorteret,

98
00:07:14,720 --> 00:07:18,240
det er umuligt for dig at vide det er sorteret, indtil du tjekker hvert element

99
00:07:18,240 --> 00:07:20,660
at se, at de er i sorteret orden.

100
00:07:20,660 --> 00:07:25,290
Så den nedre grænse på indsættelse slags er Omega n.

101
00:07:25,290 --> 00:07:28,210
Hvad er det værste tilfælde køretid for merge slags,

102
00:07:28,210 --> 00:07:31,390
worst case er store O igen?

103
00:07:31,390 --> 00:07:37,660
Så i værste fald, hvordan merge sort kører?

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

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

106
00:07:51,930 --> 00:07:55,130
>> Der er særlige tilfælde, og hvis vi har tid i dag - men vi sandsynligvis won't -

107
00:07:55,130 --> 00:07:59,330
vi kunne se en, der gør bedre end n log n.

108
00:07:59,330 --> 00:08:04,050
Men i det generelle tilfælde, kan du ikke gøre det bedre end n log n.

109
00:08:04,050 --> 00:08:09,680
Og fusionere slags sker for at være den, du skal vide for dette kursus, der er n log n.

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

111
00:08:13,260 --> 00:08:18,070
Og endelig, i højst tre sætninger, hvordan virker udvælgelse sort arbejde?

112
00:08:18,070 --> 00:08:20,370
Er der nogen ønsker at besvare, og jeg vil tælle dine sætninger

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
Er der nogen huske udvælgelse slags?

115
00:08:31,280 --> 00:08:37,809
Selection slags er normalt temmelig nemt at huske lige fra navnet.

116
00:08:37,809 --> 00:08:45,350
Du skal bare gentage over opstillingen, finde, hvad den største værdi er eller mindste -

117
00:08:45,350 --> 00:08:47,290
uanset rækkefølge, du sortere i.

118
00:08:47,290 --> 00:08:50,750
Så lad os sige vi sortering fra den mindste til største.

119
00:08:50,750 --> 00:08:55,250
Du gentage over opstillingen, søger uanset minimum element er,

120
00:08:55,250 --> 00:08:59,750
vælg det, og så bare bytte det, hvad der er i første omgang.

121
00:08:59,750 --> 00:09:04,090
Og så på den anden passage over array, kigge efter den mindste element igen,

122
00:09:04,090 --> 00:09:07,490
vælge den og derefter bytter den med hvad der er i den anden position.

123
00:09:07,490 --> 00:09:10,650
Så vi er bare plukke og vælge de minimumsværdier

124
00:09:10,650 --> 00:09:16,050
og indsætte dem i den forreste del af arrayet, indtil det sorteres.

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

126
00:09:21,560 --> 00:09:25,710
>> Disse uundgåeligt forekommer i de former du skal udfylde, når du indsender Pset.

127
00:09:29,010 --> 00:09:32,360
Det er dybest set svarene på dem.

128
00:09:32,360 --> 00:09:34,230
Okay, så nu kodning problemer.

129
00:09:34,230 --> 00:09:40,140
Jeg har allerede sendt ud via e-mail - Har nogen ikke få denne e-mail? Okay.

130
00:09:40,140 --> 00:09:46,630
Jeg har allerede sendt ud via e-mail den plads, vi skal bruge,

131
00:09:46,630 --> 00:09:52,120
og hvis du klikker på mit navn - så jeg tror, ​​jeg har tænkt mig at være nederst

132
00:09:52,120 --> 00:09:57,170
på grund af den baglæns r - men hvis du klikker på mit navn vil du se 2 revisioner.

133
00:09:57,170 --> 00:10:02,650
Revision 1 vil blive jeg allerede kopieret og indsat koden i Spaces

134
00:10:02,650 --> 00:10:06,900
for søgning ting du bliver nødt til at gennemføre.

135
00:10:06,900 --> 00:10:10,540
Og Revision 2 vil være den slags ting, vi gennemfører efter det.

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

137
00:10:17,350 --> 00:10:22,060
Og nu ønsker vi at implementere binær søgning.

138
00:10:22,060 --> 00:10:26,470
>> Er der nogen bare ønsker at give en pseudokode højt plan forklaring

139
00:10:26,470 --> 00:10:31,440
af, hvad vi er nødt til at gøre for søgning? Yeah.

140
00:10:31,440 --> 00:10:36,170
[Studerende] Du skal bare tage midten af ​​arrayet og se, om det, du leder efter

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

142
00:10:38,650 --> 00:10:41,080
Og hvis det er mindre, skal du gå til den halvdel, der er mindre,

143
00:10:41,080 --> 00:10:44,750
og hvis det er mere, du går til den halvdel, der er mere og du gentage det, indtil du bare én ting.

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

145
00:10:46,570 --> 00:10:51,320
Bemærk, at vores numre opstilling allerede er sorteret,

146
00:10:51,320 --> 00:10:57,190
og så betyder, at vi kan drage fordel af det, og vi kunne først tjekke,

147
00:10:57,190 --> 00:11:00,390
okay, jeg leder efter tallet 50.

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

149
00:11:03,720 --> 00:11:07,380
Middle er svært at definere, hvornår det er en endnu flere ting,

150
00:11:07,380 --> 00:11:10,820
men lad os bare sige, vi vil altid afkorte til midten.

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

152
00:11:14,420 --> 00:11:17,330
Jeg leder efter 50, så 50 er større end 16.

153
00:11:17,330 --> 00:11:21,310
Så nu kan jeg dybest set behandle min array som disse elementer.

154
00:11:21,310 --> 00:11:23,450
Jeg kan smide væk alt fra 16 over.

155
00:11:23,450 --> 00:11:27,440
Nu er mit array er netop disse 4 elementer, og jeg gentager.

156
00:11:27,440 --> 00:11:31,910
Så da jeg ønsker at finde i midten igen, som kommer til at være 42.

157
00:11:31,910 --> 00:11:34,730
42 er mindre end 50, så jeg kan smide disse to elementer.

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

159
00:11:36,890 --> 00:11:38,430
Jeg har tænkt mig at finde midten igen.

160
00:11:38,430 --> 00:11:42,100
Jeg gætter 50 var et dårligt eksempel, fordi jeg altid var at smide ting til venstre,

161
00:11:42,100 --> 00:11:48,280
men ved den samme foranstaltning, hvis jeg leder efter noget

162
00:11:48,280 --> 00:11:52,100
og det er mindre end det element, jeg i øjeblikket kigger på,

163
00:11:52,100 --> 00:11:55,080
så jeg har tænkt mig at smide alt til højre.

164
00:11:55,080 --> 00:11:58,150
Så nu er vi nødt til at gennemføre det.

165
00:11:58,150 --> 00:12:02,310
Bemærk, at vi er nødt til at passere i størrelse.

166
00:12:02,310 --> 00:12:06,730
Vi kan også ikke at hard-code format.

167
00:12:06,730 --> 00:12:11,640
Så hvis vi slippe af med det # define -

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

169
00:12:21,430 --> 00:12:27,180
Hvordan kan jeg pænt regne ud, hvad størrelsen af ​​numre arrayet øjeblikket er?

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

171
00:12:30,950 --> 00:12:33,630
[Studerende] Numbers, beslag,. Længde?

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

173
00:12:36,600 --> 00:12:38,580
Behov. Længde.

174
00:12:38,580 --> 00:12:42,010
Arrays ikke har egenskaber, så der er ingen længden ejendom arrays

175
00:12:42,010 --> 00:12:45,650
der vil bare give dig uanset hvor længe det sker for at være.

176
00:12:48,180 --> 00:12:51,620
[Studerende] Se hvor meget hukommelse det har og dividere med hvor meget - >> Yeah.

177
00:12:51,620 --> 00:12:55,810
Så hvordan kan vi se, hvor meget hukommelse det har? >> [Studerende] sizeof. >> Ja, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof er operatør, der kommer til at returnere størrelsen af ​​numre array.

179
00:13:01,680 --> 00:13:10,060
Og det kommer til at være uanset hvor mange heltal der er tidspunkter på størrelse med et heltal

180
00:13:10,060 --> 00:13:14,050
da det er hvor meget hukommelse det er faktisk optage.

181
00:13:14,050 --> 00:13:17,630
Så hvis jeg vil have antallet af ting i array,

182
00:13:17,630 --> 00:13:20,560
så jeg har tænkt mig at vil opdele ved størrelsen af ​​et heltal.

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

184
00:13:26,010 --> 00:13:29,430
Hvorfor skal jeg nødt til at passere i størrelse på alle?

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

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

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

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack eksisterer, og vi passerer i antal som høstak,

189
00:13:51,540 --> 00:13:54,700
og det er lidt af en forudanelse om, hvad der er at komme. Yeah.

190
00:13:54,700 --> 00:14:00,170
[Studerende] Haystack er blot en henvisning til det, så det ville vende tilbage, hvor stor denne henvisning er.

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

192
00:14:02,150 --> 00:14:09,000
Jeg tvivler på foredrag, som du har set stakken endnu virkelig, right?

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

194
00:14:11,270 --> 00:14:16,090
Så stakken er hvor alle dine variabler vil blive gemt.

195
00:14:16,090 --> 00:14:19,960
>> Enhver hukommelse, der er allokeret til lokale variabler går i stakken,

196
00:14:19,960 --> 00:14:24,790
og hver funktion får sin egen plads på stakken, sin egen stakramme er, hvad det hedder.

197
00:14:24,790 --> 00:14:31,590
Så main har sin stakramme, og inde i det vil eksistere dette tal array,

198
00:14:31,590 --> 00:14:34,270
og det vil være af størrelse sizeof (tal).

199
00:14:34,270 --> 00:14:38,180
Det kommer til at have størrelse af tal divideret med størrelsen af ​​elementer,

200
00:14:38,180 --> 00:14:42,010
men at alle bor inden for main stak ramme.

201
00:14:42,010 --> 00:14:45,190
Når vi kalder søgning, søge får sin egen stakramme,

202
00:14:45,190 --> 00:14:48,840
sin egen plads til at gemme alle sine lokale variabler.

203
00:14:48,840 --> 00:14:56,420
Men disse argumenter - så høstak er ikke en kopi af hele denne opstilling.

204
00:14:56,420 --> 00:15:00,990
Vi videregiver ikke i hele systemet som en kopi i søgning.

205
00:15:00,990 --> 00:15:04,030
Det bare passerer en henvisning til den pågældende array.

206
00:15:04,030 --> 00:15:11,470
Så søg kan få adgang til disse numre gennem denne reference.

207
00:15:11,470 --> 00:15:17,100
Det er stadig adgang til de ting, der lever inde i main er stakramme,

208
00:15:17,100 --> 00:15:22,990
men dybest set, når vi kommer til pegepinde, som bør være snart,

209
00:15:22,990 --> 00:15:24,980
dette er, hvad pegepinde er.

210
00:15:24,980 --> 00:15:29,400
Pointers er blot henvisninger til ting, og du kan bruge pegepinde til at få adgang tingene

211
00:15:29,400 --> 00:15:32,030
der er i andre ting "stakrammer.

212
00:15:32,030 --> 00:15:37,660
Så selvom numre er lokal til vigtigste, vi kan stadig få adgang til det gennem denne pointer.

213
00:15:37,660 --> 00:15:41,770
Men da det er bare en pointer, og det er bare en henvisning,

214
00:15:41,770 --> 00:15:45,040
sizeof (høstak) blot returnerer størrelsen af ​​referencen selv.

215
00:15:45,040 --> 00:15:47,950
Den returnerer ikke størrelsen af ​​de ting den peger mod.

216
00:15:47,950 --> 00:15:51,110
Den returnerer ikke den faktiske størrelse af tal.

217
00:15:51,110 --> 00:15:55,660
Og så dette ikke kommer til at virke, som vi ønsker det.

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

219
00:15:57,320 --> 00:16:03,250
Pointers vil være væk i betydeligt mere blodige detaljer i kommende uger.

220
00:16:06,750 --> 00:16:13,740
Og det er grunden til en masse ting, som du ser, de fleste søge ting eller sortere ting,

221
00:16:13,740 --> 00:16:16,990
de er næsten alle vil få brug for at tage den faktiske størrelse af array,

222
00:16:16,990 --> 00:16:20,440
fordi i C, har vi ingen idé om, hvad størrelsen af ​​array er.

223
00:16:20,440 --> 00:16:22,720
Du er nødt til manuelt at passere det i.

224
00:16:22,720 --> 00:16:27,190
Og du kan ikke manuelt passere i hele systemet, fordi du blot passerer i referencen

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

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

227
00:16:32,300 --> 00:16:38,160
Så nu er vi ønsker at gennemføre, hvad der blev forklaret før.

228
00:16:38,160 --> 00:16:41,530
Du kan arbejde på det i et minut,

229
00:16:41,530 --> 00:16:45,250
og du behøver ikke at bekymre dig om at få alting perfekt 100% arbejder.

230
00:16:45,250 --> 00:16:51,410
Bare skrive op den halve pseudokoden for, hvordan du mener, det burde virke.

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

232
00:16:53,630 --> 00:16:56,350
Ingen grund til at være helt færdig med dette endnu.

233
00:16:56,350 --> 00:17:02,380
Men er der nogen føle sig godt tilpas med, hvad de har så langt,

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

235
00:17:05,599 --> 00:17:09,690
Er der nogen ønsker at arbejde frivilligt? Eller jeg vil tilfældigt vælge.

236
00:17:12,680 --> 00:17:18,599
Det behøver ikke at være lige ved enhver foranstaltning, men noget vi kan ændre i en arbejdsgruppe tilstand.

237
00:17:18,599 --> 00:17:20,720
[Studerende] Sure. >> Okay.

238
00:17:20,720 --> 00:17:27,220
Så kan du spare en revision ved at klikke på det lille Gem ikonet.

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

240
00:17:29,950 --> 00:17:35,140
Så nu kan jeg se din revision og enhver kan trække op til revision.

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

242
00:17:38,600 --> 00:17:43,160
Så Ramya gik med den rekursive løsning, som er absolut en gyldig løsning.

243
00:17:43,160 --> 00:17:44,970
Der er to måder, du kan gøre dette problem.

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

245
00:17:48,060 --> 00:17:53,860
De fleste problemer, du støder på, der kan gøres rekursivt kan også gø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
>> Er der nogen ønsker at definere, hvad det vil sige at lave en funktion rekursiv?

248
00:18:07,210 --> 00:18:08,920
[Studerende] Når du har en funktion kalder sig selv

249
00:18:08,920 --> 00:18:13,470
og derefter kalde sig indtil det kommer ud med sand og sand. >> Yeah.

250
00:18:13,470 --> 00:18:17,680
En rekursiv funktion er bare en funktion, som kalder sig selv.

251
00:18:17,680 --> 00:18:24,140
Der er tre store ting, som en rekursiv funktion skal have.

252
00:18:24,140 --> 00:18:27,310
Den første er selvfølgelig, det kalder sig.

253
00:18:27,310 --> 00:18:29,650
Det andet er basisscenariet.

254
00:18:29,650 --> 00:18:33,390
Så på et tidspunkt funktionen skal stoppe med at kalde sig selv,

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

256
00:18:35,610 --> 00:18:43,860
Så her ved vi, at vi skal stoppe, skal vi give op i vores søgen

257
00:18:43,860 --> 00:18:48,150
når start er lig ende - og vi vil gå over, hvad det betyder.

258
00:18:48,150 --> 00:18:52,130
Men endelig den sidste ting, der er vigtige for rekursive funktioner:

259
00:18:52,130 --> 00:18:59,250
funktionerne eller anden måde skal henvende sig til basisscenariet.

260
00:18:59,250 --> 00:19:04,140
Ligesom hvis du ikke faktisk opdaterer noget, når du gør det andet rekursivt kald,

261
00:19:04,140 --> 00:19:07,880
hvis du bogstaveligt talt bare kalde funktionen igen med de samme argumenter

262
00:19:07,880 --> 00:19:10,130
og ingen globale variable har ændret eller noget,

263
00:19:10,130 --> 00:19:14,430
du vil aldrig nå den oprindelige sag, i hvilket tilfælde det er skidt.

264
00:19:14,430 --> 00:19:17,950
Det vil være en uendelig løkke, og en stak overflow.

265
00:19:17,950 --> 00:19:24,330
Men her ser vi, at opdateringen sker da vi opdaterer starte + ende / 2,

266
00:19:24,330 --> 00:19:28,180
Vi opdaterer slutningen argument her, vi opdaterer start argument her.

267
00:19:28,180 --> 00:19:32,860
Så i alle rekursive kald vi opdaterer noget. Okay.

268
00:19:32,860 --> 00:19:38,110
Ønsker du at gå os gennem din løsning? >> Sure.

269
00:19:38,110 --> 00:19:44,270
Jeg bruger SearchHelp så hver gang jeg gør dette funktionskald

270
00:19:44,270 --> 00:19:47,910
Jeg har i starten af ​​hvor jeg leder efter i rækken, og enden

271
00:19:47,910 --> 00:19:49,380
hvor jeg leder opstillingen.

272
00:19:49,380 --> 00:19:55,330
>> På hvert trin, hvor det siger det er midt element, som er starten + ende / 2,

273
00:19:55,330 --> 00:19:58,850
er, at lige til, hvad vi leder efter?

274
00:19:58,850 --> 00:20:04,650
Og hvis det er, så vi fandt det, og jeg tror, ​​der bliver gået op indholdet af rekursion.

275
00:20:04,650 --> 00:20:12,540
Og hvis det ikke er sandt, så kontrollerer vi, om denne midterste værdi af array er for stor,

276
00:20:12,540 --> 00:20:19,320
i hvilket tilfælde ser vi på den venstre halvdel af opstillingen ved at gå fra start til midten indeks.

277
00:20:19,320 --> 00:20:22,710
Og ellers gør vi i slutningen halvdel.

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

279
00:20:24,740 --> 00:20:27,730
Det lyder godt.

280
00:20:27,730 --> 00:20:36,640
Okay, så et par ting, og faktisk, det er en meget højt niveau ting

281
00:20:36,640 --> 00:20:41,270
at du aldrig bliver nødt til at vide for dette kursus, men det er sandt.

282
00:20:41,270 --> 00:20:46,080
Rekursive funktioner, du altid hører, at de er en dårlig aftale

283
00:20:46,080 --> 00:20:51,160
fordi hvis du rekursivt kalde dig selv for mange gange, får du stack overflow

284
00:20:51,160 --> 00:20:54,990
siden, som jeg sagde før, hver funktion får sin egen stakramme.

285
00:20:54,990 --> 00:20:59,500
Så hvert opkald af rekursive funktion får sin egen stakramme.

286
00:20:59,500 --> 00:21:04,140
Så hvis du laver 1.000 rekursive kald, du får 1.000 stakrammer,

287
00:21:04,140 --> 00:21:08,390
og hurtigt du fører til at have alt for mange stakrammer og ting bare bryde.

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

289
00:21:13,480 --> 00:21:19,370
Men der er en nice delmængde af rekursive funktioner kaldet hale-rekursive funktioner,

290
00:21:19,370 --> 00:21:26,120
og dette sker for at være et eksempel på en, hvor hvis compileren opdager dette

291
00:21:26,120 --> 00:21:29,920
og det burde, tror jeg - i Dunk hvis du passerer det-O2 flag

292
00:21:29,920 --> 00:21:33,250
så det vil bemærke dette er halerekursive og gøre tingene godt.

293
00:21:33,250 --> 00:21:40,050
>> Det vil genbruge den samme stakramme igen og igen for hver rekursivt kald.

294
00:21:40,050 --> 00:21:47,010
Og så fordi du bruger den samme stakramme, behøver du ikke at bekymre dig om

295
00:21:47,010 --> 00:21:51,690
nogensinde stable overfyldte, og på samme tid, som du sagde før,

296
00:21:51,690 --> 00:21:56,380
hvor når du returnere sandt, så er det nødt til at returnere op alle disse stakrammer

297
00:21:56,380 --> 00:22:01,740
og 10. opkald til SearchHelp skal vende tilbage til 9., er at gå tilbage til det 8..

298
00:22:01,740 --> 00:22:05,360
Så det behøver ikke at ske, når funktioner er halerekursive.

299
00:22:05,360 --> 00:22:13,740
Og så hvad gør denne funktion halerekursive er opmærksom på, at for en given indkaldelse til searchHelp

300
00:22:13,740 --> 00:22:18,470
den rekursive kald at det gør er, hvad det er at vende tilbage.

301
00:22:18,470 --> 00:22:25,290
Så i den første indkaldelse til SearchHelp, vi enten umiddelbart returnere falsk,

302
00:22:25,290 --> 00:22:29,590
straks returnere sandt, eller vi laver en rekursiv opkald til SearchHelp

303
00:22:29,590 --> 00:22:33,810
hvor hvad vi vender tilbage er, hvad som opkaldet er tilbage.

304
00:22:33,810 --> 00:22:51,560
Og vi kunne ikke gøre det, hvis vi gjorde noget lignende int x = SearchHelp, afkast x * 2,

305
00:22:51,560 --> 00:22:55,440
bare nogle tilfældige ændringer.

306
00:22:55,440 --> 00:23:01,470
>> Så nu dette rekursivt kald, denne int x = SearchHelp rekursivt kald,

307
00:23:01,470 --> 00:23:05,740
er ikke længere hale rekursiv fordi det faktisk behøver at vende tilbage

308
00:23:05,740 --> 00:23:10,400
tilbage til en tidligere stakramme således at dette tidligere opfordring til funktionen

309
00:23:10,400 --> 00:23:13,040
Derefter kan gøre noget med den returnerede værdi.

310
00:23:13,040 --> 00:23:22,190
Så dette er ikke halerekursive, men hvad vi havde før, er pænt halerekursive. Yeah.

311
00:23:22,190 --> 00:23:27,000
[Studerende] Bør ikke det andet hovedforslag kontrolleres først

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

313
00:23:30,640 --> 00:23:35,770
De har start = ende, men de er nålen værdi.

314
00:23:35,770 --> 00:23:47,310
Spørgsmålet blev ikke vi løber ind i, hvis end er nålen værdi

315
00:23:47,310 --> 00:23:52,000
eller starte = ende, passende, start = ende

316
00:23:52,000 --> 00:23:59,480
og du har faktisk ikke tjekket den bestemte værdi endnu,

317
00:23:59,480 --> 00:24:03,910
derefter starte + ende / 2 er bare at være den samme værdi.

318
00:24:03,910 --> 00:24:07,890
Men vi har allerede vendt tilbage falsk og vi faktisk aldrig tjekket værdien.

319
00:24:07,890 --> 00:24:14,240
Så i det mindste i den første indkaldelse, hvis størrelse er 0, så vi ønsker at vende tilbage falsk.

320
00:24:14,240 --> 00:24:17,710
Men hvis størrelse er 1, så start ikke kommer til at lige ende,

321
00:24:17,710 --> 00:24:19,820
og vi vil i det mindste kontrollere det ene element.

322
00:24:19,820 --> 00:24:26,750
Men jeg tror du har ret i, at vi kan ende i en sag, hvor starter + ende / 2,

323
00:24:26,750 --> 00:24:31,190
starte ender med at blive det samme som start + afslutning / 2,

324
00:24:31,190 --> 00:24:35,350
men vi har faktisk aldrig tjekket dette element.

325
00:24:35,350 --> 00:24:44,740
>> Så hvis vi først tjekke er den midterste element den værdi, vi leder efter,

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

327
00:24:47,110 --> 00:24:50,740
Else hvis de er ens, så er der ingen grund til at fortsætte

328
00:24:50,740 --> 00:24:58,440
da vi bare vil opdatere til en sag, hvor vi er på en enkelt-element array.

329
00:24:58,440 --> 00:25:01,110
Hvis det enkelt element ikke er den, vi leder efter,

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

331
00:25:03,530 --> 00:25:08,900
[Studerende] Sagen er, at da størrelse er faktisk større end antallet af elementer i array,

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

333
00:25:13,070 --> 00:25:19,380
[Studerende] Sig Hvis matrixen var størrelsen 0, er SearchHelp rent faktisk vil kontrollere høstak fra 0

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

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

336
00:25:25,300 --> 00:25:30,750
Der er en anden ting, - det kunne være godt. Lad os tænke.

337
00:25:30,750 --> 00:25:40,120
Så hvis opstillingen havde 10 elementer og den midterste vi vil tjekke indeks 5,

338
00:25:40,120 --> 00:25:45,700
så vi tjekker 5, og lad os sige, at værdien er mindre.

339
00:25:45,700 --> 00:25:50,720
Så vi smider alt væk fra 5 og fremefter.

340
00:25:50,720 --> 00:25:54,030
Så start + afslutning / 2 vil være vores nye ende,

341
00:25:54,030 --> 00:25:57,450
så ja, det altid vil bo ud over slutningen af ​​array.

342
00:25:57,450 --> 00:26:03,570
Hvis det er en sag, hvis det var lige eller ulige, så ville vi kontrollere, siger, 4,

343
00:26:03,570 --> 00:26:05,770
men vi er stadig smide væk -

344
00:26:05,770 --> 00:26:13,500
Så yeah, er ende altid vil være ud over den faktiske ende af array.

345
00:26:13,500 --> 00:26:18,350
Så de elementer, som vi fokuserer på, er ende altid vil være det ene efter det.

346
00:26:18,350 --> 00:26:24,270
Og så hvis starten ikke nogensinde lige ende, er vi i en vifte af størrelse 0.

347
00:26:24,270 --> 00:26:35,600
>> Den anden ting jeg tænkte er, vi opdaterer begynder at være starte + ende / 2,

348
00:26:35,600 --> 00:26:44,020
så dette er tilfældet, at jeg har problemer med, hvor starter + ende / 2

349
00:26:44,020 --> 00:26:46,820
er det element, vi tjekker.

350
00:26:46,820 --> 00:26:58,150
Lad os sige, vi havde denne 10-element array. Uanset hvad.

351
00:26:58,150 --> 00:27:03,250
Så start + afslutning / 2 vil være noget som dette,

352
00:27:03,250 --> 00:27:07,060
og hvis det ikke er den værdi, siger, vi ønsker at opdatere.

353
00:27:07,060 --> 00:27:10,060
Værdien er større, så vi ønsker at se på denne halvdel af rækken.

354
00:27:10,060 --> 00:27:15,910
Så hvordan vi opdaterer start, opdaterer vi start til nu være dette element.

355
00:27:15,910 --> 00:27:23,790
Men det kan stadig arbejde, eller i det mindste, du kan gøre starten + ende / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Studerende] Du behøver ikke at være starte + ende [uhørligt] >> Yeah.

357
00:27:27,850 --> 00:27:33,240
Vi har allerede tjekket dette element og ved, det er ikke den, vi leder efter.

358
00:27:33,240 --> 00:27:36,800
Så vi behøver ikke at opdatere begynder at være dette element.

359
00:27:36,800 --> 00:27:39,560
Vi kan bare springe det over og opdatere begynde at være dette element.

360
00:27:39,560 --> 00:27:46,060
Og er der overhovedet en sag, lad os sige, at dette var ende,

361
00:27:46,060 --> 00:27:53,140
så derefter begynde ville være denne, start + afslutning / 2 ville være denne,

362
00:27:53,140 --> 00:28:00,580
starte + ende - Ja, jeg tror, ​​det kan ende i uendelig rekursion.

363
00:28:00,580 --> 00:28:12,690
Lad os sige det er bare en vifte af størrelse 2 eller en vifte af størrelse 1. Jeg tror, ​​det vil virke.

364
00:28:12,690 --> 00:28:19,490
Så i øjeblikket, start er at element og ende er 1 ud over det.

365
00:28:19,490 --> 00:28:24,110
Så det element, vi vil kontrollere, er denne ene,

366
00:28:24,110 --> 00:28:29,400
og så når vi opdaterer start, opdaterer vi begynder at være 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
der kommer til at ende os tilbage med start bliver dette element.

368
00:28:33,160 --> 00:28:36,210
>> Så vi tjekker det samme element igen og igen.

369
00:28:36,210 --> 00:28:43,310
Så dette er tilfældet, når hver rekursivt kald skal faktisk opdatere noget.

370
00:28:43,310 --> 00:28:48,370
Så vi er nødt til at gøre starten + ende / 2 + 1, ellers er der en sag

371
00:28:48,370 --> 00:28:50,710
hvor vi faktisk ikke at opdatere start.

372
00:28:50,710 --> 00:28:53,820
Enhver kan se, at?

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

374
00:28:56,310 --> 00:29:03,860
Er der nogen der har spørgsmål om denne løsning eller nogen flere kommentarer?

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

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

377
00:29:20,940 --> 00:29:25,950
Eller også jeg gætte, hvis du har åbnet hendes, så skal du måske have tilsidesat det tidligere.

378
00:29:25,950 --> 00:29:28,810
Betyder det automatisk gemme? Jeg er ikke positiv.

379
00:29:35,090 --> 00:29:39,130
Er der nogen der har iterativ?

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

381
00:29:46,080 --> 00:29:48,100
Tanken vil 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 vil ønsker at stort set gøre det samme idé

384
00:30:07,140 --> 00:30:16,530
hvor vi ønsker at holde styr på den nye ende af rækken, og den nye begyndelse af arrayet

385
00:30:16,530 --> 00:30:18,510
og gøre det igen og igen.

386
00:30:18,510 --> 00:30:22,430
Og hvis, hvad vi holde styr på som starten og slutningen nogensinde skærer hinanden,

387
00:30:22,430 --> 00:30:29,020
så vi ikke finde det, og vi kan returnere falsk.

388
00:30:29,020 --> 00:30:37,540
Så hvordan gør jeg det? Nogen der har forslag eller kode for mig at trække op?

389
00:30:42,190 --> 00:30:47,450
[Studerende] Do en while-løkke. >> Yeah.

390
00:30:47,450 --> 00:30:49,450
Du kommer til at ønsker at gøre en løkke.

391
00:30:49,450 --> 00:30:51,830
>> Har du have kode jeg kunne trække op, eller hvad ville du foreslå?

392
00:30:51,830 --> 00:30:56,340
[Studerende] Jeg tror det. >> Okay. Det gør tingene lettere. Hvad var dit navn?

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

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

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

396
00:31:13,200 --> 00:31:17,080
Up er ikke helt, hvad vi kaldte ende før.

397
00:31:17,080 --> 00:31:22,750
Faktisk ende er nu inden for opstillingen. Det er et element, vi bør overveje.

398
00:31:22,750 --> 00:31:26,890
Så lav er 0, op er størrelsen af ​​grupperingen - 1,

399
00:31:26,890 --> 00:31:34,780
og nu er vi looping, og vi tjekker -

400
00:31:34,780 --> 00:31:37,340
Jeg tror, ​​du kan gå igennem det.

401
00:31:37,340 --> 00:31:41,420
Hvad var dine tanker gennem dette? Gå os gennem din kode.

402
00:31:41,420 --> 00:31:49,940
[Studerende] Sure. Kig på høstakken værdien i midten og sammenligne det med nål.

403
00:31:49,940 --> 00:31:58,520
Så hvis det er større end din nål, så du ønsker at - oh, faktisk skulle der være baglæns.

404
00:31:58,520 --> 00:32:05,180
Du vil ønsker at smide den højre halvdel, og så ja, skal der være vejen.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Så det bør være mindre? Er det, hvad du sagde? >> [Studerende] 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 kigger på, er mindre end det, vi ønsker,

408
00:32:15,700 --> 00:32:19,410
så ja, vi ønsker at smide den venstre halvdel,

409
00:32:19,410 --> 00:32:22,210
hvilket betyder, at vi opdaterer alt, hvad vi overvejer

410
00:32:22,210 --> 00:32:26,610
ved at flytte lav til højre for arrayet.

411
00:32:26,610 --> 00:32:30,130
Det ser godt ud.

412
00:32:30,130 --> 00:32:34,550
Jeg tror, ​​det har det samme problem, som vi sagde på den foregående,

413
00:32:34,550 --> 00:32:49,760
hvor hvis lav er 0 og op er 1, så lav + op / 2 vil sætte op til at være det samme igen.

414
00:32:49,760 --> 00:32:53,860
>> Og selv hvis det ikke er tilfældet, er det stadig mere effektivt i det mindste

415
00:32:53,860 --> 00:32:57,630
bare smide det element, vi kiggede bare på som vi ved er forkert.

416
00:32:57,630 --> 00:33:03,240
Så lav + op / 2 + 1 - >> [studerende] Det burde være den anden vej.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Eller det skal være - 1, og den anden skal være + 1.

418
00:33:05,900 --> 00:33:09,580
[Studerende] Og der bør være en dobbelt lighedstegn. >> [Bowden] Yeah.

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

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

421
00:33:15,910 --> 00:33:21,280
Og endelig, nu hvor vi har dette + 1 - 1 ting,

422
00:33:21,280 --> 00:33:31,520
er det - er det måske ikke - er det stadigt muligt for lav til at ende op med en værdi større end op?

423
00:33:35,710 --> 00:33:40,320
Jeg tror den eneste måde, der kan ske - Er det muligt? >> [Studerende] Jeg ved det ikke.

424
00:33:40,320 --> 00:33:45,220
Men hvis det bliver afkortet, og derefter får minus, at 1 og derefter - >> Yeah.

425
00:33:45,220 --> 00:33:47,480
[Studerende] Det ville muligvis få rodet op.

426
00:33:49,700 --> 00:33:53,940
Jeg tror, ​​det skulle være godt kun fordi

427
00:33:53,940 --> 00:33:58,800
for det til at ende lavere de skulle være lige, tror jeg.

428
00:33:58,800 --> 00:34:03,070
Men hvis de er ens, så ville vi ikke have gjort det, mens løkken til at begynde med

429
00:34:03,070 --> 00:34:06,670
og vi bare ville have returneret værdien. Så jeg tror, ​​vi er godt nu.

430
00:34:06,670 --> 00:34:11,530
Bemærk, at selv om dette problem ikke længere rekursivt

431
00:34:11,530 --> 00:34:17,400
den samme slags idéer anvendelse, når vi kan se, hvordan dette så let egner sig

432
00:34:17,400 --> 00:34:23,659
til en rekursiv løsning ved, at vi bare er ved at opdatere de indeks, igen og igen,

433
00:34:23,659 --> 00:34:29,960
vi gør problemet mindre og mindre, vi fokuserer på en delmængde af array.

434
00:34:29,960 --> 00:34:40,860
[Studerende] Hvis lav er 0 og op er 1, ville de begge være 0 + 1/2, der ville gå til 0,

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

436
00:34:47,000 --> 00:34:50,870
[Studerende] Hvor skal vi tjekker ligestilling?

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

438
00:34:55,100 --> 00:34:58,590
Vi er ikke i øjeblikket gø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 gøre testen ned her, fordi lad os sige det første midten -

441
00:35:13,740 --> 00:35:16,430
[Studerende] Det er faktisk godt lide ikke smide den bundne.

442
00:35:16,430 --> 00:35:20,220
Så hvis du smider den bundne, er du nødt til at tjekke det først, eller whatever.

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

444
00:35:23,350 --> 00:35:29,650
Så nu har vi smidt væk den, vi i øjeblikket kigget på,

445
00:35:29,650 --> 00:35:33,260
hvilket betyder, at vi nu er nødt til at også have

446
00:35:33,260 --> 00:35:44,810
if (høstak [(lav + op) / 2] == nål), så kan vi returnere sandt.

447
00:35:44,810 --> 00:35:52,070
Og uanset om jeg sætter andre eller bare hvis det betyder bogstaveligt talt den samme ting

448
00:35:52,070 --> 00:35:57,110
fordi dette ville have returneret sandt.

449
00:35:57,110 --> 00:36:01,450
Så jeg vil sætte ellers hvis, men det gør ikke noget.

450
00:36:01,450 --> 00:36:10,440
>> Så ellers hvis dette, ellers dette, og det er en fælles ting jeg gør

451
00:36:10,440 --> 00:36:14,340
hvor selv hvis det er tilfældet, hvor alt er godt her,

452
00:36:14,340 --> 00:36:22,780
ligesom lav aldrig kan være større end op, det er ikke værd at ræsonnement om, hvorvidt det er sandt.

453
00:36:22,780 --> 00:36:28,010
Så du kan lige så godt sige, mens lav, er mindre end eller lig med

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

455
00:36:30,720 --> 00:36:35,300
så hvis de nogensinde lig med eller lav sker til at gå op,

456
00:36:35,300 --> 00:36:40,130
så vi kan bryde ud af denne løkke.

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

458
00:36:47,080 --> 00:36:49,270
Okay. Det ser godt ud.

459
00:36:49,270 --> 00:36:52,230
Nu skal vi ønsker at gøre slags.

460
00:36:52,230 --> 00:37:04,030
Hvis vi går til min anden revision, ser vi de samme tal,

461
00:37:04,030 --> 00:37:07,550
men nu er de ikke længere er i sorteret orden.

462
00:37:07,550 --> 00:37:12,840
Og vi ønsker at gennemføre sortere ved hjælp af en algoritme i O n log n.

463
00:37:12,840 --> 00:37:17,240
Så hvilken algoritme tror du, vi bør gennemføre her? >> [Studerende] Flet slags.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Yeah. Flet slags er O (n log n), så det er hvad vi vil gøre.

465
00:37:23,810 --> 00:37:26,680
Og problemet bliver temmelig ens,

466
00:37:26,680 --> 00:37:31,920
hvor den let egner sig til en rekursiv løsning.

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

468
00:37:35,580 --> 00:37:42,540
men rekursion vil være lettere her, og vi bør gøre rekursion.

469
00:37:45,120 --> 00:37:49,530
Jeg tror vi vil gå gennem sammenfletning slags først,

470
00:37:49,530 --> 00:37:54,280
selv om der er en dejlig video på merge sort allerede. [Latter]

471
00:37:54,280 --> 00:37:59,780
Så fusionere slags der er - jeg spilder så meget af dette papir.

472
00:37:59,780 --> 00:38:02,080
Åh, der er kun en tilbage.

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

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

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

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

477
00:38:33,460 --> 00:38:36,780
Hver af disse to arrays begge sorteres.

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

479
00:38:40,970 --> 00:38:46,710
Nu hvad fletning skal gøre, er at kombinere dem i et enkelt array, der selv er sorteret.

480
00:38:46,710 --> 00:38:57,130
Så vi ønsker en vifte af str. 6, der vil have disse elementer inde i det

481
00:38:57,130 --> 00:38:59,390
i sorteret orden.

482
00:38:59,390 --> 00:39:03,390
>> Og så vi kan drage fordel af det faktum, at disse to arrays sorteres

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

484
00:39:06,800 --> 00:39:13,510
lineær tid betydning, hvis dette array er størrelse x, og det er størrelse y,

485
00:39:13,510 --> 00:39:20,970
så den totale algoritmen skal 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
[Studerende] Kunne vi starte fra venstre?

488
00:39:26,030 --> 00:39:30,150
Så du sætter 0 ned først og derefter 1 og derefter her du er på 2.

489
00:39:30,150 --> 00:39:33,320
Så det er lidt ligesom du har en fane, der er flytter til højre. >> [Bowden] Yeah.

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

491
00:39:41,070 --> 00:39:43,530
Fordi begge arrays er sorteret, vi ved, at disse 2 elementer

492
00:39:43,530 --> 00:39:46,920
er de mindste elementer i hver række.

493
00:39:46,920 --> 00:39:53,500
Så det betyder, at 1 af disse 2 elementer skal være det mindste element i vores fusionerede array.

494
00:39:53,500 --> 00:39:58,190
Det bare så sker det, at den mindste er det en på højre denne gang.

495
00:39:58,190 --> 00:40:02,580
Så vi tager 0, indsætte det på venstre, fordi 0 er mindre end 1,

496
00:40:02,580 --> 00:40:08,210
så tage 0, skal du indsætte det i vores første position, og så opdaterer vi denne

497
00:40:08,210 --> 00:40:12,070
til nu fokusere på det første element.

498
00:40:12,070 --> 00:40:14,570
Og nu gentager vi.

499
00:40:14,570 --> 00:40:20,670
Så nu vi sammenligner 2 og 1. 1 er mindre, så vi indsætter 1.

500
00:40:20,670 --> 00:40:25,300
Vi opdaterer denne pegepind til at pege på den fyr.

501
00:40:25,300 --> 00:40:33,160
Nu skal vi gøre det igen, så 2. Dette vil opdatere, sammenligne disse 2, 3.

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

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

504
00:40:42,110 --> 00:40:49,010
>> Det burde være temmelig indlysende, at det er lineær tid siden vi bare gå på tværs af hvert element én gang.

505
00:40:49,010 --> 00:40:55,980
Og det er det største skridt til at gennemføre merge sort gør dette.

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

507
00:40:59,330 --> 00:41:15,020
Et par ting at bekymre sig om, er lad os sige, at vi var sammenlægning 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
I dette tilfælde ender vi i den situation, hvor denne ene vil være mindre,

509
00:41:30,930 --> 00:41:36,160
så vi opdatere denne pointer, denne ene vil være mindre, opdatere denne,

510
00:41:36,160 --> 00:41:41,280
denne ene er mindre, og nu har du nødt til at erkende

511
00:41:41,280 --> 00:41:44,220
når du har faktisk løber tør for materiale til at sammenligne med.

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

513
00:41:49,400 --> 00:41:55,190
alt i dette array er nu lige har indsat ind på her.

514
00:41:55,190 --> 00:42:02,040
Så hvis vi nogensinde løbe ind i det punkt, hvor en af ​​vores arrays er helt flettes allerede,

515
00:42:02,040 --> 00:42:06,510
så vi bare tage alle elementer i den anden array og indsætte dem i slutningen af ​​array.

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

517
00:42:13,630 --> 00:42:18,070
Det er én ting at holde øje med.

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

519
00:42:26,120 --> 00:42:32,600
Flet sortere så er baseret på det, det er 2 trin, 2 dumme trin.

520
00:42:38,800 --> 00:42:42,090
Lad os bare give denne array.

521
00:42:57,920 --> 00:43:05,680
Så fusionere sortere, trin 1 er at rekursivt bryde array i to halvdele.

522
00:43:05,680 --> 00:43:09,350
Så delt dette array i to halvdele.

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

524
00:43:22,920 --> 00:43:25,800
Og nu gør vi det igen og vi delt dem i to halvdele.

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

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

527
00:43:34,790 --> 00:43:37,440
Vi ville gøre det samme herovre.

528
00:43:37,440 --> 00:43:40,340
Og nu vi dele det op i to halvdele igen.

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 vores base case.

531
00:43:53,170 --> 00:44:00,540
Når arrays er af størrelse 1, så holder vi op med opsplitningen i to halvdele.

532
00:44:00,540 --> 00:44:03,190
>> Nu hvad gør vi med det?

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

534
00:44:15,730 --> 00:44:24,000
Så nu, at vi er på dette punkt, nu træde to af merge slags er bare fusionerende par til listerne.

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

536
00:44:27,610 --> 00:44:31,410
Vi ved sammenfletning vil returnere disse i sorteret orden.

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

538
00:44:33,920 --> 00:44:41,440
Nu ønsker vi at flette disse, og som vil returnere en liste med dem i sorteret orden,

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 flettede par gang.

542
00:45:02,890 --> 00:45:05,140
Nu skal vi bare fusionere igen.

543
00:45:05,140 --> 00:45:10,130
Bemærk, at hver af disse lister sorteres i sig selv,

544
00:45:10,130 --> 00:45:15,220
og så kan vi bare flette disse lister til at få en liste over størrelse 4, som er sorteret

545
00:45:15,220 --> 00:45:19,990
og flette disse to lister for at få en liste over størrelse 4, der er sorteret.

546
00:45:19,990 --> 00:45:25,710
Og endelig kan vi flette de to lister over størrelse 4 for at få en liste over størrelse 8, der er sorteret.

547
00:45:25,710 --> 00:45:34,030
Så for at se, at dette er samlet n log n, vi allerede har set, at fletningen er lineær,

548
00:45:34,030 --> 00:45:40,390
så når vi har at gøre med sammenlægningen disse, så ligesom de samlede omkostninger i fletningen

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

550
00:45:43,410 --> 00:45:49,610
Eller ja, det er O n, men n her er bare disse 2 elementer, så det er 2.

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

552
00:45:52,850 --> 00:45:58,820
så på tværs af alle de smelter sammen, vi skal gøre, vi ender med at gøre n..

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

554
00:46:03,210 --> 00:46:08,060
så omkostningerne ved sammenlægningen i dette sæt 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 fusionere disse 2, da disse 2, og individuelt denne sammenfletning vil tage fire operationer,

557
00:46:16,980 --> 00:46:23,610
denne sammenfletning vil tage fire operationer, men endnu en gang, mellem alle disse,

558
00:46:23,610 --> 00:46:29,030
vi ender sammenlægning N Total ting, og så tager dette trin n..

559
00:46:29,030 --> 00:46:33,670
Og så hvert niveau tager n elementer er slået sammen.

560
00:46:33,670 --> 00:46:36,110
>> Og hvor mange niveauer er der?

561
00:46:36,110 --> 00:46:40,160
På hvert niveau, vokser vores array efter størrelse 2.

562
00:46:40,160 --> 00:46:44,590
Her vores arrays er af størrelse 1, her de er af størrelse 2, her de er af størrelse 4,

563
00:46:44,590 --> 00:46:46,470
og endelig, de er af størrelse 8.

564
00:46:46,470 --> 00:46:56,450
Så da det er en fordobling, er der vil være i alt log n af disse niveauer.

565
00:46:56,450 --> 00:47:02,090
Så med log n niveauer, hvert enkelt niveau under n samlede transaktioner,

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ørgsmål?

568
00:47:08,940 --> 00:47:13,320
Har folk allerede gjort fremskridt på hvordan man gennemfører dette?

569
00:47:13,320 --> 00:47:18,260
Er der nogen, der allerede er i en tilstand, hvor jeg bare kan trække op deres kode?

570
00:47:20,320 --> 00:47:22,260
Jeg kan give et minut.

571
00:47:24,770 --> 00:47:27,470
Denne ene vil være længere.

572
00:47:27,470 --> 00:47:28,730
Jeg anbefaler stærkt tilbagevendende -

573
00:47:28,730 --> 00:47:30,510
Du behøver ikke at gøre rekursion for sammenfletningen

574
00:47:30,510 --> 00:47:33,750
fordi at gøre rekursion for fletningen, er du nødt til at passere en masse forskellige størrelser.

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

576
00:47:37,150 --> 00:47:43,720
Men rekursion for sort selv er temmelig let.

577
00:47:43,720 --> 00:47:49,190
Du skal bare bogstaveligt kalde slags på venstre halvdel, sort på højre halvdel. Okay.

578
00:47:51,770 --> 00:47:54,860
Nogen der har noget jeg kan trække op endnu?

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

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

581
00:47:59,900 --> 00:48:02,970
Nogen der har noget, vi kan arbejde med?

582
00:48:05,450 --> 00:48:09,680
Ellers vil vi bare arbejde med dette og derefter udvide derfra.

583
00:48:09,680 --> 00:48:14,050
>> Nogen der har mere end dette, at jeg kan trække op?

584
00:48:14,050 --> 00:48:17,770
[Studerende] Yeah. Du kan trække op mine. >> Okay.

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

586
00:48:22,170 --> 00:48:25,280
[Studerende] Der var en masse betingelser. >> Åh, skyde. Kan du -

587
00:48:25,280 --> 00:48:28,110
[Studerende] Jeg er nødt til at gemme det. >> Yeah.

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

589
00:48:35,730 --> 00:48:38,570
Åh, men det er ikke så slemt.

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

591
00:48:41,650 --> 00:48:47,080
Så sort er selv bare ringer mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Forklar os, hvad mergeSortHelp gør.

593
00:48:49,530 --> 00:48:55,700
[Studerende] MergeSortHelp temmelig meget gør de to vigtigste skridt,

594
00:48:55,700 --> 00:49:01,270
nemlig at sortere hver halvdel af opstillingen og derefter at fusionere dem begge.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Okay, så giv mig et sekund.

596
00:49:10,850 --> 00:49:13,210
Jeg tror, ​​at dette - >> [studerende] Jeg har brug for -

597
00:49:17,100 --> 00:49:19,400
Yeah. Jeg mangler noget.

598
00:49:19,400 --> 00:49:23,100
I fusionere, indser jeg, at jeg har brug for at oprette et nyt array

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

600
00:49:26,530 --> 00:49:28,170
[Studerende] Så jeg opretter et nyt array.

601
00:49:28,170 --> 00:49:31,510
Jeg glemte i slutningen af ​​fusionere til re-skifte.

602
00:49:31,510 --> 00:49:34,490
Okay. Vi har brug for et nyt array.

603
00:49:34,490 --> 00:49:41,000
I sammenfletning sortere, er det næsten altid sandt.

604
00:49:41,000 --> 00:49:44,340
Del af omkostningerne ved en bedre algoritme tidsmæssigt

605
00:49:44,340 --> 00:49:47,310
næsten altid behøver at bruge lidt mere hukommelse.

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

607
00:49:51,570 --> 00:49:54,780
du ville uundgåeligt nødt til at bruge nogle ekstra hukommelse.

608
00:49:54,780 --> 00:49:58,240
Han eller hun skabte et nyt array.

609
00:49:58,240 --> 00:50:03,400
Og så siger du i slutningen vi bare nødt til at kopiere ny array i den oprindelige array.

610
00:50:03,400 --> 00:50:04,830
[Studerende] Jeg tror så, ja.

611
00:50:04,830 --> 00:50:08,210
Jeg ved ikke, om det virker i forhold til at tælle ved henvisning eller hvad -

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

613
00:50:20,620 --> 00:50:24,480
Har du prøve at køre dette? >> [Studerende] Nej, ikke endnu. >> Okay.

614
00:50:24,480 --> 00:50:28,880
Prøv at køre det, og så vil jeg tale om det for et sekund.

615
00:50:28,880 --> 00:50:35,200
[Studerende] Jeg har brug for at have alle de funktioner prototyper og alt, selv om, ikke?

616
00:50:37,640 --> 00:50:40,840
De funktionelle prototyper. Åh, du mener ligesom - Ja.

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

618
00:50:43,040 --> 00:50:47,390
>> Så for at sortere at kalde mergeSortHelp skal mergeSortHelp enten er blevet defineret

619
00:50:47,390 --> 00:50:56,370
før sortere eller vi bare brug for prototypen. Du skal blot kopiere og indsætte det.

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

621
00:50:59,490 --> 00:51:03,830
men merge er ikke blevet defineret endnu, så vi kan bare lade mergeSortHelp vide

622
00:51:03,830 --> 00:51:08,700
at det er hvad fusionere kommer til at se ud, 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 ikke har nogen base case.

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

626
00:51:38,110 --> 00:51:42,610
vil få brug for en slags base case til at vide, hvornår de skal stoppe rekursivt kalder sig.

627
00:51:42,610 --> 00:51:45,590
Hvad er vores base case vil være her? Yeah.

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

629
00:51:49,110 --> 00:51:56,220
Så ligesom vi så lige der, stoppede vi opdele arrays

630
00:51:56,220 --> 00:52:01,850
når vi fik ind arrays af størrelse 1, der uundgåeligt er sorteret sig selv.

631
00:52:01,850 --> 00:52:09,530
Så hvis størrelse er lig med 1, vi kender array er allerede sorteret,

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

633
00:52:12,970 --> 00:52:16,880
>> Bemærk, at er ugyldige, så vi ikke returnere noget særligt, vi bare vende tilbage.

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

635
00:52:19,580 --> 00:52:27,440
Jeg gætter vores base case kunne også være, hvis vi tilfældigvis sammenlægning et array af størrelse 0,

636
00:52:27,440 --> 00:52:30,030
vi nok ønsker at stoppe på et tidspunkt,

637
00:52:30,030 --> 00:52:33,610
så vi kan blot sige størrelse mindre end 2 eller mindre end eller lig med 1.

638
00:52:33,610 --> 00:52:37,150
således at dette vil arbejde for enhver opstilling nu.

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

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

641
00:52:42,740 --> 00:52:45,950
Nu vil du gå os gennem fletningen?

642
00:52:45,950 --> 00:52:49,140
Hvad har alle disse tilfælde betyder?

643
00:52:49,140 --> 00:52:54,480
Heroppe, vi bare gør det samme idé, det -

644
00:52:56,970 --> 00:53:02,470
[Studerende] Jeg har brug for at være forbi størrelse med alle de mergeSortHelp opkald.

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

646
00:53:10,080 --> 00:53:16,210
[Bowden] Åh, størrelse / 2, størrelse / 2. >> [Studerende] Ja, og også i den ovennævnte funktion som godt.

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

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

649
00:53:23,010 --> 00:53:26,580
Lad mig tænke et sekund.

650
00:53:26,580 --> 00:53:28,780
Må vi løber ind i et problem?

651
00:53:28,780 --> 00:53:33,690
Vi er altid at behandle venstre som 0. >> [Studerende] Nej.

652
00:53:33,690 --> 00:53:36,340
Det er også forkert. Undskyld. Det bør være start. Yeah.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Okay. Jeg kan godt lide, at bedre.

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

655
00:53:43,880 --> 00:53:47,200
Så nu vil du gå os gennem fletningen? >> [Studerende] Okay.

656
00:53:47,200 --> 00:53:52,150
Jeg er bare walking gennem denne nye array, jeg har oprettet.

657
00:53:52,150 --> 00:53:57,420
Dens størrelse er størrelsen af ​​den del af sættet, som vi ønsker at blive sorteret

658
00:53:57,420 --> 00:54:03,460
og forsøger at finde det element, at jeg skulle lægge i det nye array-trin.

659
00:54:03,460 --> 00:54:10,140
Så for at gøre det, først jeg kontrollere, hvis den venstre halvdel af arrayet fortsætter med at have nogen flere elementer,

660
00:54:10,140 --> 00:54:14,260
og hvis den ikke gør det, så skal du gå ned til det andet betingelse, der bare siger

661
00:54:14,260 --> 00:54:20,180
okay, skal det være i den rigtige opstilling, og vi vil sætte det i det aktuelle indeks i newArray.

662
00:54:20,180 --> 00:54:27,620
>> Og så ellers, jeg tjekker hvis den rigtige side af array også er færdig,

663
00:54:27,620 --> 00:54:30,630
i hvilket tilfælde jeg bare sætte i venstre.

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

665
00:54:34,180 --> 00:54:40,970
Men alligevel, den anden to check hvilke af de to er mindre i venstre eller højre.

666
00:54:40,970 --> 00:54:49,770
Og også i hvert enkelt tilfælde, jeg inkrementering uanset hvilken pladsholder jeg tilvækst.

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

668
00:54:52,040 --> 00:54:53,840
Det ser godt ud.

669
00:54:53,840 --> 00:54:58,800
Er der nogen der har kommentarer eller bekymringer eller spørgsmål?

670
00:55:00,660 --> 00:55:07,720
Så de fire sager, som vi er nødt til at bringe tingene i bare at være - eller det ligner fem -

671
00:55:07,720 --> 00:55:13,100
men vi er nødt til at overveje, om den venstre-array er løbet tør for ting, vi skal fusionere,

672
00:55:13,100 --> 00:55:16,390
hvorvidt retten arrayet er løbet tør for ting, vi skal fusionere -

673
00:55:16,390 --> 00:55:18,400
Jeg peger på ingenting.

674
00:55:18,400 --> 00:55:21,730
Så hvad enten venstre-array er løbet tør for ting eller det rigtige opstilling er løbet tør for ting.

675
00:55:21,730 --> 00:55:24,320
Det er to sager.

676
00:55:24,320 --> 00:55:30,920
Vi har også brug for trivielle tilfælde af, om den venstre ting er mindre end det rigtige.

677
00:55:30,920 --> 00:55:33,910
Så vi ønsker at vælge den venstre ting.

678
00:55:33,910 --> 00:55:37,630
Det er de sager.

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

680
00:55:40,990 --> 00:55:46,760
Array tilbage. Det er 1, 2, 3. Okay. Så ja, det er de fire ting, vi måske ønsker at gø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 art er et eksempel på en funktion, der både er ikke halerekursive,

684
00:56:03,070 --> 00:56:07,040
det er ikke nemt at gøre det halerekursive,

685
00:56:07,040 --> 00:56:13,450
men også det er ikke meget let at gøre det iterativ.

686
00:56:13,450 --> 00:56:16,910
Dette er meget let.

687
00:56:16,910 --> 00:56:19,170
Denne implementering af fletningen slags,

688
00:56:19,170 --> 00:56:22,140
fusionere, uanset hvad du gør, er du nødt til at bygge merge.

689
00:56:22,140 --> 00:56:29,170
>> Så fusionere slags bygget oven på fletningen rekursivt er bare disse tre linjer.

690
00:56:29,170 --> 00:56:34,700
Iterativt, det er mere irriterende og vanskeligere at tænke over.

691
00:56:34,700 --> 00:56:41,860
Men bemærk at det ikke er halerekursive siden mergeSortHelp - når den kalder sig selv -

692
00:56:41,860 --> 00:56:46,590
det stadig nødvendigt at gøre ting efter dette rekursivt kald afkast.

693
00:56:46,590 --> 00:56:50,830
Så denne stakramme skal fortsætte med at eksistere, selv efter at kalde dette.

694
00:56:50,830 --> 00:56:54,170
Og så når du kalder det, skal stakrammen fortsætte med at eksistere

695
00:56:54,170 --> 00:56:57,780
fordi selv efter denne samtale, vi stadig nødt til at fusionere.

696
00:56:57,780 --> 00:57:01,920
Og det er nontrivial at gøre denne halerekursive.

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

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

699
00:57:09,860 --> 00:57:13,400
Så gå tilbage til at sortere - Åh, der er to ting, jeg gerne vil vise. Okay.

700
00:57:13,400 --> 00:57:17,840
Går tilbage til at sortere, vil vi gøre dette hurtigt.

701
00:57:17,840 --> 00:57:21,030
Eller søg. Sorter? Sorter. Yeah.

702
00:57:21,030 --> 00:57:22,730
Går tilbage til begyndelsen af ​​slags.

703
00:57:22,730 --> 00:57:29,870
Vi ønsker at skabe en algoritme, der sorterer array ved hjælp af 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 muligt? Er der nogen der har nogen form for -

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

707
00:57:44,300 --> 00:57:48,300
Hvis vi er ved at blive forbedret fra n log n til O i n,

708
00:57:48,300 --> 00:57:51,450
vi har forbedret vores algoritme tidsmæssigt,

709
00:57:51,450 --> 00:57:55,250
hvilket betyder hvad skal vi gøre for at gøre op for det?

710
00:57:55,250 --> 00:57:59,520
[Studerende] Space. >> Yeah. Vi skal bruge mere plads.

711
00:57:59,520 --> 00:58:04,490
Og ikke bare mere plads, det er eksponentielt mere plads.

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

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

714
00:58:18,980 --> 00:58:22,210
Men det er fordi vi er nødt til at bruge så meget plads

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

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

717
00:58:31,220 --> 00:58:36,810
Vi kan opnå dette, hvis vi garanterer, at nogen bestemt element i arrayet

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

719
00:58:42,070 --> 00:58:44,500
Så lad os bare sige, at størrelse er 200,

720
00:58:44,500 --> 00:58:48,130
ethvert element i et array er under størrelse 200.

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

722
00:58:51,080 --> 00:58:58,660
Du kan meget let få et array, som du ved alt i det

723
00:58:58,660 --> 00:59:00,570
vil være mindre end et vist antal.

724
00:59:00,570 --> 00:59:07,400
Ligesom hvis du har nogle absolut massiv vektor eller noget

725
00:59:07,400 --> 00:59:11,810
men du ved alt kommer til at ligge mellem 0 og 5,

726
00:59:11,810 --> 00:59:14,790
så det vil være betydeligt hurtigere at gøre dette.

727
00:59:14,790 --> 00:59:17,930
Og det bundne på et af elementerne er 5,

728
00:59:17,930 --> 00:59:21,980
så denne bundne, er, at hvor meget hukommelse, du skal bruge.

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

730
00:59:26,300 --> 00:59:32,960
I teorien er der altid en bundet eftersom et heltal kun kan være op til 4000000000,

731
00:59:32,960 --> 00:59:40,600
men det er urealistisk siden da vi ville bruge plads

732
00:59:40,600 --> 00:59:44,400
af størrelsesordenen 4 mia. Så det er urealistisk.

733
00:59:44,400 --> 00:59:47,060
Men her vil vi sige, at vores grænse er 200.

734
00:59:47,060 --> 00:59:59,570
Det trick til at gøre det i O n er vi gøre en anden array kaldet tællinger af størrelse BUNDET.

735
00:59:59,570 --> 01:00:10,470
Så faktisk, det er en genvej til - jeg faktisk ikke, om Dunk gør dette.

736
01:00:11,150 --> 01:00:15,330
Men i GCC i det mindste - jeg antager Dunk gør det også -

737
01:00:15,330 --> 01:00:18,180
Dette vil bare initialisere hele array'et at være 0'erne.

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

739
01:00:25,320 --> 01:00:31,500
i <bundet; i + +) og tæller [i] = 0;

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

741
01:00:35,260 --> 01:00:39,570
Jeg gentage over mit array,

742
01:00:39,570 --> 01:00:51,920
og hvad jeg laver, er jeg tælle antallet af hver - Lad os gå ned her.

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

744
01:00:55,480 --> 01:01:00,010
Hvad jeg tælle er antallet af forekomster af hver af disse elementer.

745
01:01:00,010 --> 01:01:03,470
Lad os faktisk tilføje et par mere i her med nogle gentagelser.

746
01:01:03,470 --> 01:01:11,070
Så den værdi, vi har her, er værdien af ​​det vil være array [i].

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

748
01:01:14,850 --> 01:01:18,870
Og nu vil jeg tælle hvor mange af denne værdi jeg har set,

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

750
01:01:21,230 --> 01:01:29,430
Når dette er gjort, er tæller kommer til at ligne 0001.

751
01:01:29,430 --> 01:01:42,190
Lad os gøre tæller [val] - BUNDET + 1.

752
01:01:42,190 --> 01:01:48,230
>> Nu det er bare at redegøre for det faktum, at vi starter fra 0.

753
01:01:48,230 --> 01:01:50,850
Så hvis 200 bliver vores største antal,

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

755
01:01:54,720 --> 01:02:01,540
Så tæller, vil det se ud som 00.001, da vi har en 4.

756
01:02:01,540 --> 01:02:10,210
Så må vi have 0001, hvor vi vil have en 1 i det 8. indeks tæller.

757
01:02:10,210 --> 01:02:14,560
Vi vil have en 2 i det 23. indeks tæller.

758
01:02:14,560 --> 01:02:17,630
Vi vil have en 2 i den 42. indekset tæller.

759
01:02:17,630 --> 01:02:21,670
Så vi kan bruge tæller.

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

761
01:02:44,920 --> 01:02:52,540
Og så hvis num_of_item er 2, der betyder, at vi ønsker at indsætte 2 i antallet i

762
01:02:52,540 --> 01:02:55,290
i vores sorteret array.

763
01:02:55,290 --> 01:03:02,000
Så vi er nødt til at holde styr på, hvor langt vi er i opstillingen.

764
01:03:02,000 --> 01:03:05,470
Så index = 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
Tæller -

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

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

769
01:03:35,100 --> 01:03:38,290
Ja, det ser godt ud. Okay.

770
01:03:38,290 --> 01:03:43,050
Så gør alle forstå, hvad formålet med mit tæller array er?

771
01:03:43,050 --> 01:03:48,140
Det er at tælle antallet af forekomster af hver af disse numre.

772
01:03:48,140 --> 01:03:51,780
Så jeg iteration over der tæller array,

773
01:03:51,780 --> 01:03:57,190
og den i'te position i tællinger matrix

774
01:03:57,190 --> 01:04:01,930
er antallet af i'erne, der skal vises i min sorteret array.

775
01:04:01,930 --> 01:04:06,840
Det er derfor tællinger af 4 kommer til at være 1

776
01:04:06,840 --> 01:04:11,840
og tæller på 8 vil være 1, tællinger af 23 vil være 2.

777
01:04:11,840 --> 01:04:16,900
Så det er hvor mange af dem jeg ønsker at indsætte i min sorteret array.

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

779
01:04:19,200 --> 01:04:28,960
Jeg indsætter num_of_item i'erne ind i min sorteret array.

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

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

782
01:04:43,100 --> 01:04:47,470
men det er også lineær i, hvad dette nummer sker for at være,

783
01:04:47,470 --> 01:04:50,730
og så det afhænger i høj grad af, hvad din grænse er.

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

785
01:04:53,290 --> 01:04:58,330
Hvis din bundne vil være 10.000, så det er lidt værre,

786
01:04:58,330 --> 01:05:01,360
men hvis det indbundne vil være 4 milliarder, det er helt urealistisk

787
01:05:01,360 --> 01:05:07,720
og dette array er nødt til at være af størrelse 4 mia.kr., hvilket er urealistisk.

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

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

790
01:05:13,270 --> 01:05:15,710
Jeg indså en anden ting, når vi skulle igennem.

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

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

793
01:05:26,330 --> 01:05:31,040
Det eneste, jeg ønskede at kommentere, er, at når du har at gøre med ting som indeks,

794
01:05:31,040 --> 01:05:38,320
du aldrig 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 har at gøre med disse indekser,

796
01:05:41,120 --> 01:05:45,950
bør du stort set altid beskæftige sig med unsigned heltal.

797
01:05:45,950 --> 01:05:53,850
Grunden til dette er, når du har at gøre med signerede heltal,

798
01:05:53,850 --> 01:05:56,090
så hvis du har 2 signerede heltal, og du tilføjer dem sammen

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

800
01:06:00,640 --> 01:06:03,410
Så det er, hvad heltalsoverløb er.

801
01:06:03,410 --> 01:06:10,500
>> Hvis jeg tilføjer 2 mia og 1 mia jeg ender med negativ 1 mia.

802
01:06:10,500 --> 01:06:15,480
Det er, hvordan heltal arbejde på computere.

803
01:06:15,480 --> 01:06:17,510
Så problemet med at bruge -

804
01:06:17,510 --> 01:06:23,500
Det er fint, undtagen hvis lav sker for at være 2 milliarder og op sker for at være 1 mia

805
01:06:23,500 --> 01:06:27,120
så dette vil være negativ 1 mia så vil vi dele dette med 2

806
01:06:27,120 --> 01:06:29,730
og ender med negativ 500 mio.

807
01:06:29,730 --> 01:06:33,760
Så det er kun et problem, hvis du tilfældigvis være at søge gennem et array

808
01:06:33,760 --> 01:06:38,070
af milliarder af ting.

809
01:06:38,070 --> 01:06:44,050
Men hvis lav + op sker med overløb, så det er et problem.

810
01:06:44,050 --> 01:06:47,750
Så snart vi gør dem usigneret, så 2 milliarder plus 1 mia 3 mia.

811
01:06:47,750 --> 01:06:51,960
3 milliarder divideret med 2 er 1,5 mia.

812
01:06:51,960 --> 01:06:55,670
Så så snart de er unsigned, alt er perfekt.

813
01:06:55,670 --> 01:06:59,900
Og så det er også et problem, når du skriver din efter sløjfer,

814
01:06:59,900 --> 01:07:03,940
og faktisk er det sandsynligvis gør det automatisk.

815
01:07:09,130 --> 01:07:12,330
Det vil faktisk bare råbe på dig.

816
01:07:12,330 --> 01:07:21,610
Så hvis dette tal er for stor til at være i bare et heltal, men det ville passe ind i en usigneret heltal,

817
01:07:21,610 --> 01:07:24,970
det vil råbe på dig, så det er derfor, du aldrig rigtig løber ind i problemet.

818
01:07:29,150 --> 01:07:34,820
Du kan se, at et indeks aldrig kommer til at være negativ,

819
01:07:34,820 --> 01:07:39,220
og så når du iteration over et array,

820
01:07:39,220 --> 01:07:43,970
du kan næsten altid sige unsigned int i, men du behøver ikke virkelig nødt til at.

821
01:07:43,970 --> 01:07:47,110
Tingene kommer til at arbejde temmelig meget lige så godt.

822
01:07:48,740 --> 01:07:50,090
Okay. [Hvisker] Hvad er klokken?

823
01:07:50,090 --> 01:07:54,020
Det sidste, jeg ønskede at vise - og jeg vil bare gøre det virkelig hurtig.

824
01:07:54,020 --> 01:08:03,190
Du ved, hvordan vi har # define så vi # kan definere MAX som 5 eller noget?

825
01:08:03,190 --> 01:08:05,940
Lad os ikke gøre MAX. # Define bundet som 200. Det er, hvad vi gjorde før.

826
01:08:05,940 --> 01:08:10,380
Det definerer en konstant, som er lige til at blive kopieret og indsat

827
01:08:10,380 --> 01:08:13,010
hvor vi tilfældigvis skrive BUNDET.

828
01:08:13,010 --> 01:08:18,189
>> Så vi kan faktisk gøre mere med # definerer.

829
01:08:18,189 --> 01:08:21,170
Vi kan # define funktioner.

830
01:08:21,170 --> 01:08:23,410
De er ikke rigtig fungerer, men vi vil kalde dem funktioner.

831
01:08:23,410 --> 01:08:36,000
Et eksempel ville være noget MAX (x, y) er defineret som (x <y y:? X). Okay.

832
01:08:36,000 --> 01:08:40,660
Så du bør vænne sig til ternære operatør syntaks,

833
01:08:40,660 --> 01:08:49,029
men er x mindre end y? Returnerer y, ellers returnerer x.

834
01:08:49,029 --> 01:08:54,390
Så du kan se, kan du gøre dette til en særskilt funktion,

835
01:08:54,390 --> 01:09:01,399
og funktionen kunne være som bool MAX tager 2 argumenter, returnere dette.

836
01:09:01,399 --> 01:09:08,340
Dette er en af ​​de mest almindelige jeg ser gjort på denne måde. Vi kalder 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 blot syntaksen for det.

839
01:09:15,859 --> 01:09:18,740
Du kan skrive en makro til at gøre hvad du vil.

840
01:09:18,740 --> 01:09:22,649
Du ofte se makroer for debugging printfs og kram.

841
01:09:22,649 --> 01:09:29,410
Så en form for printf, er der specielle konstanter i C ligesom underscore LINE understregning,

842
01:09:29,410 --> 01:09:31,710
2 understreger LINE understregning,

843
01:09:31,710 --> 01:09:37,550
og der er også jeg tror 2 understregninger FUNC. Det kunne være det. Noget i den retning.

844
01:09:37,550 --> 01:09:40,880
Disse ting vil blive erstattet med navnet på den funktion

845
01:09:40,880 --> 01:09:42,930
eller nummeret på den linje, du er på.

846
01:09:42,930 --> 01:09:48,630
Ofte skriver du debugging printfs der ned her kunne jeg så bare skrive

847
01:09:48,630 --> 01:09:54,260
Debug og det vil udskrive linjenummer og funktion, som jeg tilfældigvis er i

848
01:09:54,260 --> 01:09:57,020
at det stødte at DEBUG erklæring.

849
01:09:57,020 --> 01:09:59,550
Og du kan også udskrive andre ting.

850
01:09:59,550 --> 01:10:05,990
Så en ting du skal holde øje med er, hvis jeg tilfældigvis # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
som noget i retning af 2 * y og 2 * x.

852
01:10:11,380 --> 01:10:14,310
Så uanset årsagen, sker dig at gøre det en masse.

853
01:10:14,310 --> 01:10:16,650
Så gør det til en makro.

854
01:10:16,650 --> 01:10:18,680
Dette er faktisk brudt.

855
01:10:18,680 --> 01:10:23,050
Jeg ville kalde det ved at gøre noget lignende DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Så hvad skal returneres?

857
01:10:28,840 --> 01:10:30,580
[Studerende] 12.

858
01:10:30,580 --> 01:10:34,800
Ja, 12 blive returneret, og 12 er returneret.

859
01:10:34,800 --> 01:10:43,350
3 bliver erstattet for x, bliver 6 erstattes for y, og vi vender tilbage 2 * 6, hvilket er 12.

860
01:10:43,350 --> 01:10:47,710
Nu hvad med det her? Hvad skal returneres?

861
01:10:47,710 --> 01:10:50,330
[Studerende] 14. >> Ideelt 14.

862
01:10:50,330 --> 01:10:55,290
Spørgsmålet er, hvordan hash definerer arbejdet, husk det er en bogstavelig kopiere og indsætte

863
01:10:55,290 --> 01:11:00,160
af stort set alt, hvad så dette vil blive fortolket som

864
01:11:00,160 --> 01:11:11,270
er 3 mindre end 1 plus 6, 2 gange 1 plus 6, 2 gange 3.

865
01:11:11,270 --> 01:11:19,780
>> Så af denne grund du næsten altid wrap alt i parentes.

866
01:11:22,180 --> 01:11:25,050
Enhver variabel, du næsten altid wrap i parentes.

867
01:11:25,050 --> 01:11:29,570
Der er tilfælde, hvor du ikke behøver at, ligesom jeg ved, at jeg ikke behøver at gøre det her

868
01:11:29,570 --> 01:11:32,110
fordi mindre end er temmelig meget altid bare at gå på arbejde,

869
01:11:32,110 --> 01:11:34,330
selv om det måske ikke engang være sandt.

870
01:11:34,330 --> 01:11:41,870
Hvis der er noget latterligt som DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
så der kommer til at få erstattet med 3 mindre end 1 lig lig med 2,

872
01:11:49,760 --> 01:11:53,460
og så derefter det kommer til at gøre 3 mindre end 1, betyder det lige 2,

873
01:11:53,460 --> 01:11:55,620
der er ikke det, vi ønsker.

874
01:11:55,620 --> 01:12:00,730
Så for at undgå eventuelle operatør forrang problemer,

875
01:12:00,730 --> 01:12:02,870
altid wrap 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 spørgsmål om Pset, så lad os det vide.

878
01:12:12,470 --> 01:12:18,010
Det skal være sjovt, og hacker-udgaven også er meget mere realistisk

879
01:12:18,010 --> 01:12:22,980
end hacker udgave af sidste års, så vi håber, at en masse af jer prøve det.

880
01:12:22,980 --> 01:12:26,460
Sidste års var meget overvældende.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]