1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Avsnitt 3 - Mer Bekväm]

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

3
00:00:05,070 --> 00:00:07,310
>> [Detta är CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Så den första frågan konstigt formulerad.

5
00:00:12,700 --> 00:00:17,480
GDB kan du "felsöka" ett program, men mer specifikt, vad kan du göra?

6
00:00:17,480 --> 00:00:22,590
Jag svarar att en, och jag vet inte exakt vad som förväntas,

7
00:00:22,590 --> 00:00:27,910
så jag gissar att det är något i stil med det kan du steg för steg

8
00:00:27,910 --> 00:00:31,540
gå igenom programmet, interagera med, ändra variabler, göra alla dessa saker -

9
00:00:31,540 --> 00:00:34,270
princip helt styra exekvering av ett program

10
00:00:34,270 --> 00:00:38,410
och inspektera varje given del av genomförandet av programmet.

11
00:00:38,410 --> 00:00:43,030
Så dessa funktioner kan du felsöka saker.

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

13
00:00:44,830 --> 00:00:50,520
Varför kräver binär sökning som en array sorteras?

14
00:00:50,520 --> 00:00:53,360
Vem vill svara på det?

15
00:00:56,120 --> 00:01:00,070
[Eleven] Eftersom det inte fungerar om det inte sorteras. >> Ja. [Skratt]

16
00:01:00,070 --> 00:01:04,910
Om det inte sorteras, då är det omöjligt att dela den på mitten

17
00:01:04,910 --> 00:01:07,850
och vet att allt till vänster är mindre och allt till höger

18
00:01:07,850 --> 00:01:10,490
är större än det mittersta värdet.

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

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

21
00:01:14,170 --> 00:01:17,570
Varför är bubbla typ i O n kvadrat?

22
00:01:17,570 --> 00:01:23,230
Vill någon först ge en mycket snabb hög nivå översikt över vad bubbla sortera är?

23
00:01:25,950 --> 00:01:33,020
[Eleven] Du princip gå igenom varje element och du kolla de första delarna.

24
00:01:33,020 --> 00:01:37,150
Om de är ute var du byta dem, kan du kontrollera de närmaste delarna och så vidare.

25
00:01:37,150 --> 00:01:40,770
När du når slutet, då vet du att det största elementet är placerat i slutet,

26
00:01:40,770 --> 00:01:42,750
så du ignorerar att en då du håller på att gå igenom,

27
00:01:42,750 --> 00:01:48,490
och varje gång du måste kolla en mindre del tills du gör några ändringar. >> Ja.

28
00:01:48,490 --> 00:01:58,470
Det kallas bubbla Sortera eftersom om du vänder matrisen på sidan så det är upp och ner, vertikal,

29
00:01:58,470 --> 00:02:03,100
då de stora värdena kommer att sjunka till botten och de små värdena kommer att bubbla upp till toppen.

30
00:02:03,100 --> 00:02:05,210
Det är hur det fick sitt namn.

31
00:02:05,210 --> 00:02:08,220
Och ja, du går bara igenom.

32
00:02:08,220 --> 00:02:11,190
Du fortsätter att gå igenom arrayen, byta ut större värde

33
00:02:11,190 --> 00:02:14,040
att få de största värdena till botten.

34
00:02:14,040 --> 00:02:17,500
>> Varför är det O n kvadrat?

35
00:02:18,690 --> 00:02:24,620
Först, inte vill att någon ska säga varför det är O n kvadrat?

36
00:02:24,620 --> 00:02:28,760
[Elev] Eftersom för varje körning går n gånger.

37
00:02:28,760 --> 00:02:32,100
Du kan bara vara säker på att du har tagit den största delen hela vägen ner,

38
00:02:32,100 --> 00:02:35,230
då måste man upprepa det så många delar. >> Ja.

39
00:02:35,230 --> 00:02:41,800
Så kom ihåg vad Big O betyder och vilka stora Omega innebär.

40
00:02:41,800 --> 00:02:50,560
Den stora O är som den övre gränsen på hur långsamt det kan faktiskt köra.

41
00:02:50,560 --> 00:02:58,990
Så genom att säga att det är O n kvadrat, är det inte O n annars skulle kunna köra

42
00:02:58,990 --> 00:03:02,640
i linjär tid, men det är O n kubik

43
00:03:02,640 --> 00:03:06,390
eftersom den begränsas av O n kubik.

44
00:03:06,390 --> 00:03:12,300
Om det är avgränsas av O n kvadrat, då är det avgränsas också av n kubik.

45
00:03:12,300 --> 00:03:20,280
Så det är n kvadrat, och i absolut värsta fall inte kan göra bättre än n kvadrat,

46
00:03:20,280 --> 00:03:22,830
vilket är varför det är O n kvadrat.

47
00:03:22,830 --> 00:03:31,200
Så för att se lätt matematik på hur det kommer sig vara n kvadrat,

48
00:03:31,200 --> 00:03:40,530
om vi har fem saker i vår lista, första gången hur många swappar kunde vi behöver eventuellt göra

49
00:03:40,530 --> 00:03:47,170
för att få det? Låt oss faktiskt bara -

50
00:03:47,170 --> 00:03:52,040
Hur många swappar ska vi behöva göra i den första körningen av bubbla sortera arrayen?

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

52
00:03:53,540 --> 00:03:58,340
>> Om det finns 5 delar, kommer vi att behöva göra n - 1.

53
00:03:58,340 --> 00:04:01,100
Sedan den andra en hur många swappar ska vi behöva göra?

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

55
00:04:03,440 --> 00:04:11,640
Och den tredje kommer att vara n - 3 och därefter för enkelhetens jag kommer att skriva de två sista

56
00:04:11,640 --> 00:04:15,270
som då vi kommer att behöva göra 2 swappar och 1 swap.

57
00:04:15,270 --> 00:04:19,899
Jag antar den sista eller inte kan faktiskt behöva hända.

58
00:04:19,899 --> 00:04:22,820
Är det en swap? Jag vet inte.

59
00:04:22,820 --> 00:04:26,490
Så dessa är de totala mängderna av swappar eller åtminstone jämförelser du måste göra.

60
00:04:26,490 --> 00:04:29,910
Även om du inte byta, måste du ändå jämföra värdena.

61
00:04:29,910 --> 00:04:33,910
Så det finns n - 1 jämförelser i den första körningen genom uppsättningen.

62
00:04:33,910 --> 00:04:42,050
Om du ordna dessa saker, låt oss faktiskt göra det sex saker så saker stack upp snyggt,

63
00:04:42,050 --> 00:04:44,790
och då ska jag göra 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Så bara ordna dessa summor vill vi se hur många jämförelser vi gör

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

66
00:04:52,700 --> 00:04:56,550
Så om vi tar de här killarna här nere,

67
00:04:56,550 --> 00:05:07,470
då vi fortfarande bara summera hur många jämförelser fanns.

68
00:05:07,470 --> 00:05:13,280
Men om vi summerar dessa och vi summerar dessa och vi summerar dessa,

69
00:05:13,280 --> 00:05:18,130
det är fortfarande samma problem. Vi summerar bara just dessa grupper.

70
00:05:18,130 --> 00:05:22,400
>> Så nu är vi summera 3 ns. Det är inte bara 3 ns.

71
00:05:22,400 --> 00:05:27,650
Det kommer alltid att vara n / 2 ns.

72
00:05:27,650 --> 00:05:29,430
Så här har vi råkar ha 6.

73
00:05:29,430 --> 00:05:34,830
Om vi ​​hade 10 saker vi kunde göra detta gruppering för 5 olika par saker

74
00:05:34,830 --> 00:05:37,180
och sluta med n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Så att du alltid kommer att få n / 2 ns, och så detta kommer vi krafsa ut det till n kvadrat / 2.

76
00:05:45,840 --> 00:05:48,890
Och så även om det är faktorn halv, som råkar komma i

77
00:05:48,890 --> 00:05:54,190
grund av det faktum att genom varje iteration över arrayen vi jämför 1 mindre

78
00:05:54,190 --> 00:05:58,040
så det är hur vi får över 2, men det är fortfarande n kvadrat.

79
00:05:58,040 --> 00:06:01,650
Vi bryr oss inte om den konstanta faktorn för en halv.

80
00:06:01,650 --> 00:06:07,760
Så många Big O sånt här förlitar sig på bara typ att göra denna typ av matematik,

81
00:06:07,760 --> 00:06:12,260
gör aritmetiska summor och geometriska serier grejer,

82
00:06:12,260 --> 00:06:17,750
men de flesta av dem i denna kurs är ganska enkelt.

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

84
00:06:19,290 --> 00:06:24,430
Varför är införandet Sortera i Omega n? Vad betyder omega?

85
00:06:24,430 --> 00:06:27,730
[Två studenter talar på en gång - obegripliga] >> yeah.

86
00:06:27,730 --> 00:06:30,630
Omega du kan tänka på som nedre gräns.

87
00:06:30,630 --> 00:06:36,550
>> Så oavsett hur effektiv din insättning Sortera algoritm är,

88
00:06:36,550 --> 00:06:41,810
oavsett den lista som har passerat i, har det alltid jämföra minst n ting

89
00:06:41,810 --> 00:06:44,620
eller det måste iterera över n saker.

90
00:06:44,620 --> 00:06:47,280
Varför det?

91
00:06:47,280 --> 00:06:51,190
[Eleven] För om listan redan sorteras, sedan genom den första iterationen

92
00:06:51,190 --> 00:06:54,080
Du kan bara garantera att den allra första elementet är minst,

93
00:06:54,080 --> 00:06:56,490
och den andra iterationen kan endast garantera de första två är

94
00:06:56,490 --> 00:07:00,010
eftersom du inte vet att resten av listan är sorterad. >> Ja.

95
00:07:00,010 --> 00:07:08,910
Om du skickar i en helt sorterad lista, åtminstone du måste gå över alla element

96
00:07:08,910 --> 00:07:12,180
att se att ingenting behöver flyttas runt.

97
00:07:12,180 --> 00:07:14,720
Så passerar över listan och säger åh, detta redan sorteras,

98
00:07:14,720 --> 00:07:18,240
det är omöjligt för dig att veta att det är sorterade tills du kontrollera varje del

99
00:07:18,240 --> 00:07:20,660
att se till att de är i sorterad ordning.

100
00:07:20,660 --> 00:07:25,290
Så nedre gräns för insättning typ är Omega n.

101
00:07:25,290 --> 00:07:28,210
Vad är det värsta fallet gångtid sammanslagning sortera,

102
00:07:28,210 --> 00:07:31,390
värsta fall är Big O igen?

103
00:07:31,390 --> 00:07:37,660
Så i värsta fall, hur merge sort kör?

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

105
00:07:43,690 --> 00:07:49,990
De snabbaste generella sortering algoritmer är n log n. Du kan inte göra bättre.

106
00:07:51,930 --> 00:07:55,130
>> Det finns särskilda fall, och om vi har tid i dag - men vi förmodligen won't -

107
00:07:55,130 --> 00:07:59,330
kunde vi se en som gör bättre än n log n.

108
00:07:59,330 --> 00:08:04,050
Men i det allmänna fallet kan du inte bättre än n log n.

109
00:08:04,050 --> 00:08:09,680
Och sammanfoga Sortera råkar vara den du bör veta för denna kurs som är n log n.

110
00:08:09,680 --> 00:08:13,260
Och så kommer vi faktiskt genomföra det i dag.

111
00:08:13,260 --> 00:08:18,070
Och slutligen, i högst tre meningar, hur fungerar val Sortera?

112
00:08:18,070 --> 00:08:20,370
Vill någon svara, och jag ska räkna dina meningar

113
00:08:20,370 --> 00:08:22,390
för om du går över 3 -

114
00:08:25,530 --> 00:08:28,330
Minns någon val Sortera?

115
00:08:31,280 --> 00:08:37,809
Val Sortera är oftast ganska lätt att komma ihåg bara från namnet.

116
00:08:37,809 --> 00:08:45,350
Du bara iterera över arrayen, hitta vad det största värdet är eller minsta -

117
00:08:45,350 --> 00:08:47,290
vilken ordning du sorterar i.

118
00:08:47,290 --> 00:08:50,750
Så låt oss säga att vi sorterar från minsta till största.

119
00:08:50,750 --> 00:08:55,250
Du iterera över arrayen, söker oavsett minsta elementet är,

120
00:08:55,250 --> 00:08:59,750
markera den och sedan bara byta den allt som finns i första hand.

121
00:08:59,750 --> 00:09:04,090
Och sedan på den andra passerar över arrayen, leta efter minsta elementet igen,

122
00:09:04,090 --> 00:09:07,490
markera den och sedan byta den med vad som finns i det andra läget.

123
00:09:07,490 --> 00:09:10,650
Så vi bara plocka och välja de lägsta värdena

124
00:09:10,650 --> 00:09:16,050
och föra in dem i den främre delen av matrisen tills den sorteras.

125
00:09:19,210 --> 00:09:21,560
Frågor på det?

126
00:09:21,560 --> 00:09:25,710
>> Dessa visas oundvikligen i de former som du måste fylla i när du skickar in pset.

127
00:09:29,010 --> 00:09:32,360
De är i stort sett svaren på dem.

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

129
00:09:34,230 --> 00:09:40,140
Jag skickade redan ut över e-post - Var det någon inte få att e-post? Okej.

130
00:09:40,140 --> 00:09:46,630
Jag skickade redan ut över e-post det utrymme som vi kommer att använda,

131
00:09:46,630 --> 00:09:52,120
och om du klickar på mitt namn - så jag tror jag kommer att vara i botten

132
00:09:52,120 --> 00:09:57,170
på grund av den bakåt R - men om du klickar på mitt namn ser du 2 revideringar.

133
00:09:57,170 --> 00:10:02,650
Revidering 1 kommer att jag redan kopieras och klistras in koden i Spaces

134
00:10:02,650 --> 00:10:06,900
för sökningen sak du kommer att behöva genomföra.

135
00:10:06,900 --> 00:10:10,540
Och revision 2 kommer att vara den typ sak som vi genomför efter det.

136
00:10:10,540 --> 00:10:15,770
Så du kan klicka på min Revision 1 och arbeta därifrån.

137
00:10:17,350 --> 00:10:22,060
Och nu vill vi genomföra binär sökning.

138
00:10:22,060 --> 00:10:26,470
>> Vill någon att bara ge en pseudokod hög nivå förklaring

139
00:10:26,470 --> 00:10:31,440
av vad vi kommer att behöva göra för sökning? Ja.

140
00:10:31,440 --> 00:10:36,170
[Eleven] Du tar bara mitten av matris och se om det du letar efter

141
00:10:36,170 --> 00:10:38,650
är mindre än eller mer än så.

142
00:10:38,650 --> 00:10:41,080
Och om det är mindre, går du till hälften är mindre,

143
00:10:41,080 --> 00:10:44,750
och om det är mer, går du till halv som är mer och du upprepa det tills du får bara en sak.

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

145
00:10:46,570 --> 00:10:51,320
Observera att våra nummer array redan sorteras,

146
00:10:51,320 --> 00:10:57,190
och så det betyder att vi kan dra nytta av detta och vi kan först kontrollera,

147
00:10:57,190 --> 00:11:00,390
Okej, jag letar efter numret 50.

148
00:11:00,390 --> 00:11:03,720
Så jag kan gå in i mitten.

149
00:11:03,720 --> 00:11:07,380
Mitten är svårt att definiera när det är ett jämnt antal saker,

150
00:11:07,380 --> 00:11:10,820
men låt oss bara säga att vi alltid kommer trunkera till mitten.

151
00:11:10,820 --> 00:11:14,420
Så här har vi 8 saker, så i mitten skulle vara 16.

152
00:11:14,420 --> 00:11:17,330
Jag letar efter 50, så 50 är större än 16.

153
00:11:17,330 --> 00:11:21,310
Så nu kan jag i princip behandla min array som dessa element.

154
00:11:21,310 --> 00:11:23,450
Jag kan kasta bort allt från 16 över.

155
00:11:23,450 --> 00:11:27,440
Nu är min matris är bara dessa 4 element, och jag upprepar.

156
00:11:27,440 --> 00:11:31,910
Så då vill jag hitta mitten igen, vilket kommer att bli 42.

157
00:11:31,910 --> 00:11:34,730
42 är mindre än 50, så jag kan kasta bort dessa två element.

158
00:11:34,730 --> 00:11:36,890
Detta är min återstående matris.

159
00:11:36,890 --> 00:11:38,430
Jag ska hitta mitten igen.

160
00:11:38,430 --> 00:11:42,100
Jag antar att 50 var ett dåligt exempel eftersom jag var alltid kasta bort saker till vänster,

161
00:11:42,100 --> 00:11:48,280
men samma åtgärd, om jag letar efter något

162
00:11:48,280 --> 00:11:52,100
och det är mindre än elementet jag för närvarande är ute på,

163
00:11:52,100 --> 00:11:55,080
då ska jag kasta bort allt till höger.

164
00:11:55,080 --> 00:11:58,150
Så nu måste vi genomföra det.

165
00:11:58,150 --> 00:12:02,310
Observera att vi måste gå i storlek.

166
00:12:02,310 --> 00:12:06,730
Vi kan inte heller behöver hård-kod storlek.

167
00:12:06,730 --> 00:12:11,640
Så om vi bli av med den # define -

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

169
00:12:21,430 --> 00:12:27,180
Hur kan jag räkna fint ut vad storleken på siffrorna arrayen närvarande är?

170
00:12:27,180 --> 00:12:30,950
>> Hur många element är i siffrorna arrayen?

171
00:12:30,950 --> 00:12:33,630
[Studerande] Siffror, konsoler,. Längd?

172
00:12:33,630 --> 00:12:36,600
[Bowden] som inte finns i C.

173
00:12:36,600 --> 00:12:38,580
Behöver. Längd.

174
00:12:38,580 --> 00:12:42,010
Arrayer inte har egenskaper, så det finns ingen längd egendom matriser

175
00:12:42,010 --> 00:12:45,650
som bara kommer att ge dig hur lång tid det råkar vara.

176
00:12:48,180 --> 00:12:51,620
[Elev] Se hur mycket minne den har och dividera med hur mycket - >> Ja.

177
00:12:51,620 --> 00:12:55,810
Så hur kan vi se hur mycket minne den har? >> [Elev] sizeof. >> Ja, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof är den operatör som kommer att returnera storleken på siffrorna arrayen.

179
00:13:01,680 --> 00:13:10,060
Och det kommer att bli men många heltal finns det tillfällen storleken av ett heltal

180
00:13:10,060 --> 00:13:14,050
eftersom det är hur mycket minne det faktiskt tar upp.

181
00:13:14,050 --> 00:13:17,630
Så om jag vill ha många saker i matrisen,

182
00:13:17,630 --> 00:13:20,560
då ska jag vill dela av storleken på ett heltal.

183
00:13:22,820 --> 00:13:26,010
Okej. Så det låter mig passera i storlek här.

184
00:13:26,010 --> 00:13:29,430
Varför måste jag passera i storlek alls?

185
00:13:29,430 --> 00:13:38,570
Varför kan jag inte bara göra här uppe int size = sizeof (höstack) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Varför fungerar det inte?

187
00:13:41,490 --> 00:13:44,470
[Elev] Det är inte en global variabel.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack finns och vi passerar i antal som höstack,

189
00:13:51,540 --> 00:13:54,700
och detta är lite av en föraning om vad som komma skall. Ja.

190
00:13:54,700 --> 00:14:00,170
[Elev] Haystack är bara hänvisa till det, så det skulle återvända hur stor en sådan hänvisning.

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

192
00:14:02,150 --> 00:14:09,000
Jag tvivlar på föreläsning som du har sett stapeln ännu inte riktigt, eller hur?

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

194
00:14:11,270 --> 00:14:16,090
Så stack är där alla dina variabler kommer att lagras.

195
00:14:16,090 --> 00:14:19,960
>> Varje minne som är tilldelade för lokala variabler går i stacken,

196
00:14:19,960 --> 00:14:24,790
och varje funktion får sitt eget utrymme på stacken, är sin egen stack ram vad det kallas.

197
00:14:24,790 --> 00:14:31,590
Så stora har sin stack ram och inuti det kommer att finnas här siffrorna array,

198
00:14:31,590 --> 00:14:34,270
och det kommer att vara av storlek sizeof (tal).

199
00:14:34,270 --> 00:14:38,180
Det kommer att ha storlek med siffror uppdelade efter storlek av element,

200
00:14:38,180 --> 00:14:42,010
men att alla bor inom huvud stack ram.

201
00:14:42,010 --> 00:14:45,190
När vi kallar sökning, får söka sin egen stack ram,

202
00:14:45,190 --> 00:14:48,840
sitt eget utrymme för att lagra alla sina lokala variabler.

203
00:14:48,840 --> 00:14:56,420
Men dessa argument - så höstack är inte en kopia av hela denna uppsättning.

204
00:14:56,420 --> 00:15:00,990
Vi klarar inte i hela arrayen som en kopia i sökning.

205
00:15:00,990 --> 00:15:04,030
Det går bara en referens till den arrayen.

206
00:15:04,030 --> 00:15:11,470
Så sökning kan komma åt dessa siffror genom denna referens.

207
00:15:11,470 --> 00:15:17,100
Det är fortfarande komma åt saker som lever inne i huvud stack ram,

208
00:15:17,100 --> 00:15:22,990
men i grunden, när vi kommer till pekare, vilket bör vara snart,

209
00:15:22,990 --> 00:15:24,980
detta är vad pekare är.

210
00:15:24,980 --> 00:15:29,400
Pekare är bara referenser till saker, och du kan använda pekare att komma åt saker

211
00:15:29,400 --> 00:15:32,030
som är i annat "stack ramar.

212
00:15:32,030 --> 00:15:37,660
Så även om siffrorna är lokal till viktigaste, kan vi komma åt den genom denna pekare.

213
00:15:37,660 --> 00:15:41,770
Men eftersom det är bara en pekare och det är bara en referens,

214
00:15:41,770 --> 00:15:45,040
sizeof (höstack) returnerar bara storleken på själva referensen.

215
00:15:45,040 --> 00:15:47,950
Det returnerar inte storleken på sak det pekar på.

216
00:15:47,950 --> 00:15:51,110
Det returnerar inte den faktiska storleken på tal.

217
00:15:51,110 --> 00:15:55,660
Och så detta kommer inte att fungera som vi vill.

218
00:15:55,660 --> 00:15:57,320
>> Frågor på det?

219
00:15:57,320 --> 00:16:03,250
Pekare kommer att vara borta i betydligt mera blodig detalj i veckor framöver.

220
00:16:06,750 --> 00:16:13,740
Och det är därför en massa saker som du ser, det mesta sökning eller saker sortera,

221
00:16:13,740 --> 00:16:16,990
de är nästan alla kommer att behöva ta den verkliga storleken av arrayen,

222
00:16:16,990 --> 00:16:20,440
eftersom C har vi ingen aning om vad storleken på arrayen är.

223
00:16:20,440 --> 00:16:22,720
Du måste manuellt föra in den

224
00:16:22,720 --> 00:16:27,190
Och du kan inte manuellt gå i hela arrayen eftersom du bara passerar i referens

225
00:16:27,190 --> 00:16:30,390
och det kan inte få storleken från referensvärdet.

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

227
00:16:32,300 --> 00:16:38,160
Så nu vill vi genomföra det förklarades tidigare.

228
00:16:38,160 --> 00:16:41,530
Du kan arbeta på det under en minut,

229
00:16:41,530 --> 00:16:45,250
och du behöver inte oroa dig för att få allt perfekt 100% arbetar.

230
00:16:45,250 --> 00:16:51,410
Bara skriva upp halv pseudokod för hur du tror att det ska fungera.

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

232
00:16:53,630 --> 00:16:56,350
Du behöver vara helt klar med detta ännu.

233
00:16:56,350 --> 00:17:02,380
Men känner någon bekväm med vad de har än så länge,

234
00:17:02,380 --> 00:17:05,599
som något vi kan arbeta med tillsammans?

235
00:17:05,599 --> 00:17:09,690
Vill någon att volontär? Eller jag kommer slumpmässigt välja.

236
00:17:12,680 --> 00:17:18,599
Det behöver inte vara rätt av varje åtgärd, men något vi kan ändra till ett fungerande tillstånd.

237
00:17:18,599 --> 00:17:20,720
[Elev] Visst. >> Okej.

238
00:17:20,720 --> 00:17:27,220
Så kan du spara en översyn genom att klicka på den lilla ikonen Spara.

239
00:17:27,220 --> 00:17:29,950
Du Ramya, eller hur? >> [Elev] Ja. >> [Bowden] Okej.

240
00:17:29,950 --> 00:17:35,140
Så nu kan jag se din revision och alla kan dra upp översynen.

241
00:17:35,140 --> 00:17:38,600
Och här har vi - Okej.

242
00:17:38,600 --> 00:17:43,160
Så Ramya gick med rekursiva lösningen, som är definitivt en giltig lösning.

243
00:17:43,160 --> 00:17:44,970
Det finns två sätt att göra detta problem.

244
00:17:44,970 --> 00:17:48,060
Du kan antingen göra det iterativt eller rekursivt.

245
00:17:48,060 --> 00:17:53,860
De flesta problem du stöter på som kan göras rekursivt kan också göras iterativt.

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

247
00:17:58,510 --> 00:18:03,730
>> Vill någon att definiera vad det innebär att göra en funktion rekursiv?

248
00:18:07,210 --> 00:18:08,920
[Elev] När du har en funktion kallar sig

249
00:18:08,920 --> 00:18:13,470
och sedan kalla sig tills den kommer ut med sann och äkta. >> Ja.

250
00:18:13,470 --> 00:18:17,680
En rekursiv funktion är bara en funktion som kallar sig.

251
00:18:17,680 --> 00:18:24,140
Det finns tre stora saker som en rekursiv funktion måste ha.

252
00:18:24,140 --> 00:18:27,310
Den första är naturligtvis kallar det själv.

253
00:18:27,310 --> 00:18:29,650
Den andra är basfallet.

254
00:18:29,650 --> 00:18:33,390
Så någon gång funktionen måste sluta kalla sig,

255
00:18:33,390 --> 00:18:35,610
och det är vad basfallet är till för.

256
00:18:35,610 --> 00:18:43,860
Så här vet vi att vi måste sluta, måste vi ge upp i vårt sökande

257
00:18:43,860 --> 00:18:48,150
När börjar lika slut - och vi ska gå igenom vad det betyder.

258
00:18:48,150 --> 00:18:52,130
Men slutligen, det sista som är viktigt för rekursiva funktioner:

259
00:18:52,130 --> 00:18:59,250
funktionerna måste på något sätt närma sig basfallet.

260
00:18:59,250 --> 00:19:04,140
Som om du inte är egentligen uppdaterar något när du gör den andra rekursiva anropet,

261
00:19:04,140 --> 00:19:07,880
om du bokstavligen bara anropa funktionen igen med samma argument

262
00:19:07,880 --> 00:19:10,130
och inga globala variabler har förändrats eller något,

263
00:19:10,130 --> 00:19:14,430
du kommer aldrig att nå basfallet, i vilket fall som är dåligt.

264
00:19:14,430 --> 00:19:17,950
Det kommer att bli en oändlig rekursion och stackspill.

265
00:19:17,950 --> 00:19:24,330
Men här ser vi att uppdateringen sker eftersom vi uppdaterar start + slut / 2,

266
00:19:24,330 --> 00:19:28,180
Vi uppdaterar slut argumentet här, vi håller på att uppdatera start argumentet här.

267
00:19:28,180 --> 00:19:32,860
Så i alla rekursiva anrop som vi uppdaterar något. Okej.

268
00:19:32,860 --> 00:19:38,110
Vill du gå oss genom din lösning? >> Visst.

269
00:19:38,110 --> 00:19:44,270
Jag använder SearchHelp så att varje gång jag gör detta funktionsanrop

270
00:19:44,270 --> 00:19:47,910
Jag har i början av där jag söker i arrayen och slutet

271
00:19:47,910 --> 00:19:49,380
av där jag ser arrayen.

272
00:19:49,380 --> 00:19:55,330
>> Vid varje steg där det säger att det är i mitten delen, som är start + slut / 2,

273
00:19:55,330 --> 00:19:58,850
är att lika det vi letar efter?

274
00:19:58,850 --> 00:20:04,650
Och om det är så vi fann det, och jag antar att får gått upp nivåerna av rekursion.

275
00:20:04,650 --> 00:20:12,540
Och om det är inte sant, vi kontrollera om det mittersta värdet i matrisen är för stor,

276
00:20:12,540 --> 00:20:19,320
i vilket fall vi tittar på den vänstra halvan av uppsättningen genom att gå från start till mitten index.

277
00:20:19,320 --> 00:20:22,710
Och annars gör vi slut halv.

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

279
00:20:24,740 --> 00:20:27,730
Det låter bra.

280
00:20:27,730 --> 00:20:36,640
Okej, så ett par saker, och faktiskt, är detta en mycket hög nivå sak

281
00:20:36,640 --> 00:20:41,270
att du aldrig behöver veta för denna kurs, men det är sant.

282
00:20:41,270 --> 00:20:46,080
Rekursiva funktioner hör du alltid att de är en dålig affär

283
00:20:46,080 --> 00:20:51,160
för om du rekursivt kallar dig för många gånger får du spill

284
00:20:51,160 --> 00:20:54,990
Sedan, som jag sa tidigare, får varje funktion sin egen stack ram.

285
00:20:54,990 --> 00:20:59,500
Så varje samtal av rekursiv funktion får sin egen stack ram.

286
00:20:59,500 --> 00:21:04,140
Så om du gör 1.000 rekursiva anrop får du 1.000 stack ramar,

287
00:21:04,140 --> 00:21:08,390
och snabbt du leder att ha alltför många stack ramar och saker bara bryta.

288
00:21:08,390 --> 00:21:13,480
Så det är därför rekursiva funktioner är i allmänhet dåliga.

289
00:21:13,480 --> 00:21:19,370
Men det är en fin del av rekursiva funktioner kallas svans-rekursiva funktioner,

290
00:21:19,370 --> 00:21:26,120
och detta råkar vara ett exempel på en där om kompilatorn märker detta

291
00:21:26,120 --> 00:21:29,920
och det bör, tror jag - i klang om du klarar det-O2 flaggan

292
00:21:29,920 --> 00:21:33,250
så kommer det att märka att detta är svansen rekursiv och göra saker bra.

293
00:21:33,250 --> 00:21:40,050
>> Det kommer att återanvända samma stackram om och om igen för varje rekursivt anrop.

294
00:21:40,050 --> 00:21:47,010
Och så eftersom du använder samma stack ram, behöver du inte oroa dig för

295
00:21:47,010 --> 00:21:51,690
någonsin stack överfyllda, och på samma gång, som du sa tidigare,

296
00:21:51,690 --> 00:21:56,380
där en gång du kommer tillbaka sant, då måste återvända upp alla dessa stack ramar

297
00:21:56,380 --> 00:22:01,740
och den 10: e samtalet till SearchHelp måste återvända till 9 måste återvända till 8th.

298
00:22:01,740 --> 00:22:05,360
Så det behöver inte ske när funktioner är svansen rekursiv.

299
00:22:05,360 --> 00:22:13,740
Och så vad gör denna funktion svans rekursiv är notera att för en given samtal till searchHelp

300
00:22:13,740 --> 00:22:18,470
den rekursiva samtal som det gör är vad det återvänder.

301
00:22:18,470 --> 00:22:25,290
Så i det första samtalet till SearchHelp vi antingen omedelbart returnera false,

302
00:22:25,290 --> 00:22:29,590
omedelbart återlämna sant, eller vi gör ett rekursivt anrop till SearchHelp

303
00:22:29,590 --> 00:22:33,810
där vad vi återvänder är vad det samtalet återvänder.

304
00:22:33,810 --> 00:22:51,560
Och vi kunde inte göra detta om vi gjorde något liknande int x = SearchHelp, retur x * 2,

305
00:22:51,560 --> 00:22:55,440
bara några slumpmässig förändring.

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

307
00:23:01,470 --> 00:23:05,740
är inte längre svans rekursiv eftersom det faktiskt inte måste återvända

308
00:23:05,740 --> 00:23:10,400
tillbaka till en tidigare stack ram så att den tidigare anrop till funktionen

309
00:23:10,400 --> 00:23:13,040
kan sedan göra något med returvärdet.

310
00:23:13,040 --> 00:23:22,190
Så detta är inte svans rekursiv, men vad vi hade innan är snyggt svans rekursiv. Ja.

311
00:23:22,190 --> 00:23:27,000
[Elev] Borde inte det andra basfallet kontrolleras först

312
00:23:27,000 --> 00:23:30,640
eftersom det kan vara en situation där när du passerar det argumentet

313
00:23:30,640 --> 00:23:35,770
ni start = slut, men de är nålen värdet.

314
00:23:35,770 --> 00:23:47,310
Frågan var inte vi kan stöta på vid slutet är nålen värdet

315
00:23:47,310 --> 00:23:52,000
eller starta = slut, lämpligt, start = slut

316
00:23:52,000 --> 00:23:59,480
och du inte har faktiskt kontrollerat att särskilt värde ännu,

317
00:23:59,480 --> 00:24:03,910
börja + END / 2 bara kommer att vara samma värde.

318
00:24:03,910 --> 00:24:07,890
Men vi har redan återvänt falska och vi aldrig kontrollerat värde.

319
00:24:07,890 --> 00:24:14,240
Så åtminstone i första samtalet, om storleken är 0, då vi vill returnera false.

320
00:24:14,240 --> 00:24:17,710
Men om storlek är 1, så börjar inte kommer att lika slut,

321
00:24:17,710 --> 00:24:19,820
och vi ska åtminstone kolla en del.

322
00:24:19,820 --> 00:24:26,750
Men jag tror att ni har rätt i att vi kan hamna i ett fall där start + slut / 2,

323
00:24:26,750 --> 00:24:31,190
start slutar vara detsamma som start + slut / 2,

324
00:24:31,190 --> 00:24:35,350
men vi aldrig kontrollerat det elementet.

325
00:24:35,350 --> 00:24:44,740
>> Så om vi först kontrollera är den mellersta delen det värde vi letar efter,

326
00:24:44,740 --> 00:24:47,110
då kan vi genast returnera sant.

327
00:24:47,110 --> 00:24:50,740
Annars om de är lika, så finns det ingen mening med att fortsätta

328
00:24:50,740 --> 00:24:58,440
eftersom vi bara kommer att uppdatera till ett fall där vi är på en enda faktor matris.

329
00:24:58,440 --> 00:25:01,110
Om det enda element inte den vi letar efter,

330
00:25:01,110 --> 00:25:03,530
då allting är fel. Ja.

331
00:25:03,530 --> 00:25:08,900
[Elev] Saken är att eftersom storlek är faktiskt större än antalet element i arrayen,

332
00:25:08,900 --> 00:25:13,070
Det finns redan en förskjutning - >> Så kommer storlek -

333
00:25:13,070 --> 00:25:19,380
[Elev] Säg om arrayen var storlek 0, då SearchHelp kommer faktiskt kontrollera höstack av 0

334
00:25:19,380 --> 00:25:21,490
på första samtalet.

335
00:25:21,490 --> 00:25:25,300
Matrisen har storlek 0, så 0 är - >> Ja.

336
00:25:25,300 --> 00:25:30,750
Det finns en annan sak som - det kan vara bra. Låt oss tänka.

337
00:25:30,750 --> 00:25:40,120
Så om arrayen hade 10 element och den mittersta vi ska kontrollera är index 5

338
00:25:40,120 --> 00:25:45,700
så vi kontrollerar 5, och låt oss säga att värdet är mindre.

339
00:25:45,700 --> 00:25:50,720
Så vi kastar allt ifrån 5 och framåt.

340
00:25:50,720 --> 00:25:54,030
Så börja + END / 2 kommer att bli vår nya ände,

341
00:25:54,030 --> 00:25:57,450
så ja, det kommer alltid att bo utanför slutet av arrayen.

342
00:25:57,450 --> 00:26:03,570
Om det är ett ärende om det var jämnt eller udda, då skulle vi kontrollera, säger, 4,

343
00:26:03,570 --> 00:26:05,770
men vi är fortfarande kastar bort -

344
00:26:05,770 --> 00:26:13,500
Så ja, är slut kommer alltid att vara utom själva slutet av arrayen.

345
00:26:13,500 --> 00:26:18,350
Så de delar som vi fokuserar på är slut kommer alltid att vara en efter det.

346
00:26:18,350 --> 00:26:24,270
Och så om start gör någonsin lika ändamål, är vi i en rad storlek 0.

347
00:26:24,270 --> 00:26:35,600
>> Det andra jag tänkte är att vi uppdaterar börjar bli start + slut / 2,

348
00:26:35,600 --> 00:26:44,020
så detta är det så att jag har problem med, där start + slut / 2

349
00:26:44,020 --> 00:26:46,820
är elementet vi kontroll.

350
00:26:46,820 --> 00:26:58,150
Låt oss säga att vi hade denna 10-elementet array. Oavsett.

351
00:26:58,150 --> 00:27:03,250
Så börja + END / 2 kommer att bli något liknande den här,

352
00:27:03,250 --> 00:27:07,060
och om det inte är värdet, säger vi vill uppdatera.

353
00:27:07,060 --> 00:27:10,060
Värdet är större, så vi vill titta på denna halva uppsättningen.

354
00:27:10,060 --> 00:27:15,910
Så hur vi uppdaterar start, vi uppdaterar start nu detta element.

355
00:27:15,910 --> 00:27:23,790
Men det kan fortfarande fungera, eller åtminstone, kan du göra start + slut / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Elev] Du inte behöver börja + slut [ohörbart] >> Ja.

357
00:27:27,850 --> 00:27:33,240
Vi har redan kontrollerat detta element och vet att det inte är en vi letar efter.

358
00:27:33,240 --> 00:27:36,800
Så vi behöver inte uppdatera börjar bli detta element.

359
00:27:36,800 --> 00:27:39,560
Vi kan bara hoppa över det och uppdatera börjar bli detta element.

360
00:27:39,560 --> 00:27:46,060
Och är det någonsin ett fall, låt oss säga att detta var slutet,

361
00:27:46,060 --> 00:27:53,140
så börja skulle vara så här, börja + slut / 2 skulle vara så här,

362
00:27:53,140 --> 00:28:00,580
start + slut - Ja, jag tror att det kan hamna i oändlig rekursion.

363
00:28:00,580 --> 00:28:12,690
Låt oss säga att det är bara en rad storlek 2 eller en rad storlek 1. Jag tror att detta kommer att fungera.

364
00:28:12,690 --> 00:28:19,490
Så nu är början att element och slutet är 1 bortom det.

365
00:28:19,490 --> 00:28:24,110
Så element som vi kommer att kontrollera detta är,

366
00:28:24,110 --> 00:28:29,400
och sedan när vi uppdaterar start, vi uppdaterar börjar bli 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
som kommer att sluta oss tillbaka med start är detta element.

368
00:28:33,160 --> 00:28:36,210
>> Så vi kontrollerar samma element om och om igen.

369
00:28:36,210 --> 00:28:43,310
Så detta är fallet där varje rekursivt anrop måste faktiskt update något.

370
00:28:43,310 --> 00:28:48,370
Så vi måste göra start + slut / 2 + 1, annars finns det ett fall

371
00:28:48,370 --> 00:28:50,710
där vi inte faktiskt uppdaterar start.

372
00:28:50,710 --> 00:28:53,820
Alla ser det?

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

374
00:28:56,310 --> 00:29:03,860
Har någon frågor om denna lösning eller fler kommentarer?

375
00:29:05,220 --> 00:29:10,280
Okej. Har någon en iterativ lösning som vi alla kan titta på?

376
00:29:17,400 --> 00:29:20,940
Gjorde vi allt rekursivt?

377
00:29:20,940 --> 00:29:25,950
Eller också jag antar att om du öppnat hennes, så du kan ha åsidosatt din tidigare en.

378
00:29:25,950 --> 00:29:28,810
Sparar den automatiskt? Jag är inte positiv.

379
00:29:35,090 --> 00:29:39,130
Har någon iterativ?

380
00:29:39,130 --> 00:29:42,430
Vi kan gå igenom det tillsammans om inte.

381
00:29:46,080 --> 00:29:48,100
Tanken kommer att vara densamma.

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

383
00:30:02,830 --> 00:30:07,140
Vi kommer att vilja princip göra samma idé

384
00:30:07,140 --> 00:30:16,530
där vi vill hålla reda på den nya änden av arrayen och den nya början av uppsättningen

385
00:30:16,530 --> 00:30:18,510
och göra det om och om igen.

386
00:30:18,510 --> 00:30:22,430
Och om vad vi håller koll på som start och slut någonsin skär,

387
00:30:22,430 --> 00:30:29,020
då vi inte hitta det och vi kan returnera false.

388
00:30:29,020 --> 00:30:37,540
Så hur gör jag det? Någon har förslag eller kod för mig att dra upp?

389
00:30:42,190 --> 00:30:47,450
[Elev] Gör en while-slinga. >> Ja.

390
00:30:47,450 --> 00:30:49,450
Du kommer att vilja göra en loop.

391
00:30:49,450 --> 00:30:51,830
>> Hade du kod jag kunde dra upp, eller vad skulle du föreslå?

392
00:30:51,830 --> 00:30:56,340
[Elev] Jag tror det. >> Okej. Det gör saker och ting lättare. Vad var ditt namn?

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

394
00:31:00,140 --> 00:31:04,190
Revidering 1. Okej.

395
00:31:04,190 --> 00:31:13,200
Låg är vad vi kallade starta innan.

396
00:31:13,200 --> 00:31:17,080
Up är inte riktigt vad vi kallade slutet innan.

397
00:31:17,080 --> 00:31:22,750
Egentligen är slut nu inom matrisen. Det är en del som vi bör tänka på.

398
00:31:22,750 --> 00:31:26,890
Så låg är 0, upp är storleken på uppsättningen - 1,

399
00:31:26,890 --> 00:31:34,780
och nu är vi looping, och vi kontrollerar -

400
00:31:34,780 --> 00:31:37,340
Jag antar att du kan gå igenom den.

401
00:31:37,340 --> 00:31:41,420
Vad var ditt tänkande genom detta? Guida oss genom din kod.

402
00:31:41,420 --> 00:31:49,940
[Elev] Visst. Titta på höstacken värdet i mitten och jämför med nål.

403
00:31:49,940 --> 00:31:58,520
Så om det är större än din nål, då du vill - Åh, faktiskt, bör det vara bakåt.

404
00:31:58,520 --> 00:32:05,180
Du kommer att vilja kasta bort den högra, och så ja, bör det vara vägen.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Så detta bör vara mindre? Är det vad du sa? >> [Elev] Ja.

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

407
00:32:10,390 --> 00:32:15,700
Så om det vi tittar på är mindre än vad vi vill,

408
00:32:15,700 --> 00:32:19,410
då ja, vi vill kasta bort den vänstra halvan,

409
00:32:19,410 --> 00:32:22,210
vilket innebär att vi uppdaterar allt vi funderar

410
00:32:22,210 --> 00:32:26,610
genom att flytta låg till höger om gruppen.

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

412
00:32:30,130 --> 00:32:34,550
Jag tror att det har samma fråga som vi sade på den tidigare,

413
00:32:34,550 --> 00:32:49,760
där om låga är 0 och uppåt är 1, då låg + upp / 2 kommer att inrättas för att vara samma sak igen.

414
00:32:49,760 --> 00:32:53,860
>> Och även om det inte är fallet, är det fortfarande mer effektivt åtminstone

415
00:32:53,860 --> 00:32:57,630
att bara kasta bort elementet tittade vi bara på som vi vet är fel.

416
00:32:57,630 --> 00:33:03,240
Så låg + upp / 2 + 1 - >> [elev] Det borde vara tvärtom.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Eller detta bör vara - 1 och den andra bör vara + 1.

418
00:33:05,900 --> 00:33:09,580
[Elev] och det bör finnas en dubbel likhetstecken. >> [Bowden] Ja.

419
00:33:09,580 --> 00:33:11,340
[Eleven] Ja.

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

421
00:33:15,910 --> 00:33:21,280
Och slutligen, nu när vi har det + 1 - 1 sak,

422
00:33:21,280 --> 00:33:31,520
är det - det kanske inte - är det någonsin möjligt för låg för att sluta med ett värde större än upp?

423
00:33:35,710 --> 00:33:40,320
Jag tror att det enda sättet som kan hända - Är det möjligt? >> [Elev] Jag vet inte.

424
00:33:40,320 --> 00:33:45,220
Men om det blir stympad och sedan blir minus att 1 och sedan - >> Ja.

425
00:33:45,220 --> 00:33:47,480
[Elev] Det skulle möjligen bli förstörd.

426
00:33:49,700 --> 00:33:53,940
Jag tycker att det borde vara bra bara för att

427
00:33:53,940 --> 00:33:58,800
för att det ska hamna lägre de skulle behöva vara lika, tror jag.

428
00:33:58,800 --> 00:34:03,070
Men om de är lika, så skulle vi inte ha gjort while-slingan till att börja med

429
00:34:03,070 --> 00:34:06,670
och vi bara skulle ha återvänt värdet. Så jag tror att vi är bra nu.

430
00:34:06,670 --> 00:34:11,530
Lägg märke till att även om detta problem inte längre rekursiv,

431
00:34:11,530 --> 00:34:17,400
samma typ av idéer gäller där vi kan se hur detta så lätt lämpar sig

432
00:34:17,400 --> 00:34:23,659
till en rekursiv lösning av det faktum att vi bara ska uppdatera indexen om och om igen,

433
00:34:23,659 --> 00:34:29,960
vi gör problemet mindre och mindre, vi fokuserar på en delmängd av matrisen.

434
00:34:29,960 --> 00:34:40,860
[Elev] Om låg är 0 och uppåt är 1, skulle de båda vara 0 + 1/2, vilket skulle gå till 0,

435
00:34:40,860 --> 00:34:44,429
och då en vara + 1, skulle en vara - 1.

436
00:34:47,000 --> 00:34:50,870
[Elev] Vart ska vi kontrollera jämlikhet?

437
00:34:50,870 --> 00:34:55,100
Som om den mittersta faktiskt nål?

438
00:34:55,100 --> 00:34:58,590
Vi är inte närvarande gör det? Oh!

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

440
00:35:05,340 --> 00:35:13,740
Ja. Vi kan inte bara göra testet här nere eftersom låt oss säga de första mellersta -

441
00:35:13,740 --> 00:35:16,430
[Elev] Det är faktiskt gillar inte kasta bort den bundna.

442
00:35:16,430 --> 00:35:20,220
Så om du kasta bort den bundna, måste du kolla upp det först eller vad som helst.

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

444
00:35:23,350 --> 00:35:29,650
Så nu har vi kastat bort den vi nu tittat på,

445
00:35:29,650 --> 00:35:33,260
vilket innebär att vi nu måste även ha

446
00:35:33,260 --> 00:35:44,810
if (höstack [(lågt + upp) / 2] == nål), då kan vi återvända sant.

447
00:35:44,810 --> 00:35:52,070
Och om jag sätter annan eller bara om, betyder det bokstavligen samma sak

448
00:35:52,070 --> 00:35:57,110
eftersom detta skulle ha återvänt sant.

449
00:35:57,110 --> 00:36:01,450
Så jag sätter annat om, men det spelar ingen roll.

450
00:36:01,450 --> 00:36:10,440
>> Så annanstans om detta, annars detta, och det är en vanlig sak jag gör

451
00:36:10,440 --> 00:36:14,340
där även om det är fallet där allt är bra här,

452
00:36:14,340 --> 00:36:22,780
som låg aldrig kan vara större än upp, det är inte värt att resonemang om huruvida det är sant.

453
00:36:22,780 --> 00:36:28,010
Så du kan lika gärna säga när låg är mindre än eller lika med

454
00:36:28,010 --> 00:36:30,720
eller när låga är mindre än

455
00:36:30,720 --> 00:36:35,300
så om de någonsin lika eller låg råkar missa,

456
00:36:35,300 --> 00:36:40,130
då kan vi bryta denna slinga.

457
00:36:41,410 --> 00:36:44,630
Frågor, frågor, kommentarer?

458
00:36:47,080 --> 00:36:49,270
Okej. Detta ser bra ut.

459
00:36:49,270 --> 00:36:52,230
Nu vill vi göra slag.

460
00:36:52,230 --> 00:37:04,030
Om vi ​​går till min andra översynen ser vi samma siffror,

461
00:37:04,030 --> 00:37:07,550
men nu är de inte längre i sorterad ordning.

462
00:37:07,550 --> 00:37:12,840
Och vi vill genomföra Sortera använda någon algoritm i O n log n.

463
00:37:12,840 --> 00:37:17,240
Så vilken algoritm tror du att vi bör genomföra här? >> [Elev] Merge sort.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Ja. Merge Sortera är O (n log n), så det är vad vi ska göra.

465
00:37:23,810 --> 00:37:26,680
Och problemet kommer att vara ganska lika,

466
00:37:26,680 --> 00:37:31,920
där det lämpar lätt sig en rekursiv lösning.

467
00:37:31,920 --> 00:37:35,580
Vi kan också komma med en iterativ lösning om vi vill,

468
00:37:35,580 --> 00:37:42,540
men rekursion blir lättare här och vi bör göra rekursion.

469
00:37:45,120 --> 00:37:49,530
Jag antar att vi kommer att gå igenom sammanslagning Sortera först,

470
00:37:49,530 --> 00:37:54,280
även om det finns en härlig video på Merge Sortera redan. [Skratt]

471
00:37:54,280 --> 00:37:59,780
Så sammanfoga Sortera finns - jag slösa så mycket av detta papper.

472
00:37:59,780 --> 00:38:02,080
Åh, det finns bara en kvar.

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

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

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

476
00:38:29,910 --> 00:38:33,460
Sammanfoga tar två separata matriser.

477
00:38:33,460 --> 00:38:36,780
Individuellt dessa två arrayer båda sorteras.

478
00:38:36,780 --> 00:38:40,970
Så denna array, 1, 3, 5, sorteras. Denna matris, 0, 2, 4, sorteras.

479
00:38:40,970 --> 00:38:46,710
Nu vad sammanslagning bör göra är att kombinera dem till en enda array som själv sorteras.

480
00:38:46,710 --> 00:38:57,130
Så vi vill ha en rad storlek 6 som kommer att ha dessa element inuti det

481
00:38:57,130 --> 00:38:59,390
i sorterad ordning.

482
00:38:59,390 --> 00:39:03,390
>> Och så kan vi dra nytta av det faktum att dessa två matriser sorteras

483
00:39:03,390 --> 00:39:06,800
att göra detta i linjär tid,

484
00:39:06,800 --> 00:39:13,510
linjär tid betydelse om denna array är storlek x och detta är storleken y,

485
00:39:13,510 --> 00:39:20,970
då den totala algoritmen bör vara O (x + y). Okej.

486
00:39:20,970 --> 00:39:23,150
Så förslag.

487
00:39:23,150 --> 00:39:26,030
[Elev] Kan vi börja från vänster?

488
00:39:26,030 --> 00:39:30,150
Så du lägga 0 ner först och sedan 1 och sedan här du är på 2.

489
00:39:30,150 --> 00:39:33,320
Så det är ungefär som att du har en flik som rör sig åt höger. >> [Bowden] Ja.

490
00:39:33,320 --> 00:39:41,070
För båda dessa matriser om vi bara fokuserar på den vänstra delen.

491
00:39:41,070 --> 00:39:43,530
Eftersom båda uppsättningarna är sorterade vet vi att dessa 2 delar

492
00:39:43,530 --> 00:39:46,920
är de minsta elementen i endera matrisen.

493
00:39:46,920 --> 00:39:53,500
Så det betyder att 1 av dessa 2 element måste vara det minsta elementet i vår sammanslagna array.

494
00:39:53,500 --> 00:39:58,190
Det råkar vara så att den minsta är den på rätt den här gången.

495
00:39:58,190 --> 00:40:02,580
Så vi tar 0, sätt in den på vänster eftersom 0 är mindre än 1,

496
00:40:02,580 --> 00:40:08,210
så ta 0, sätt in det i vår första position, och sedan vi uppdatera denna

497
00:40:08,210 --> 00:40:12,070
att nu fokusera på det första elementet.

498
00:40:12,070 --> 00:40:14,570
Och nu har vi upprepa.

499
00:40:14,570 --> 00:40:20,670
Så nu vi jämför 2 och 1. 1 är mindre, så vi sätter 1.

500
00:40:20,670 --> 00:40:25,300
Vi uppdaterar denna pekare att peka på den här killen.

501
00:40:25,300 --> 00:40:33,160
Nu gör vi det igen, så 2. Detta kommer att uppdatera, jämföra dessa 2, 3.

502
00:40:33,160 --> 00:40:37,770
Då uppdateras, sedan 4 och 5.

503
00:40:37,770 --> 00:40:42,110
Så det är kopplingen.

504
00:40:42,110 --> 00:40:49,010
>> Det borde vara ganska uppenbart att det är linjär tid eftersom vi bara gå över varje element en gång.

505
00:40:49,010 --> 00:40:55,980
Och det är det största steget att genomföra sammanslagning Sortera gör detta.

506
00:40:55,980 --> 00:40:59,330
Och det är inte så svårt.

507
00:40:59,330 --> 00:41:15,020
Ett par saker att oroa sig är låt oss säga att vi var sammanslagning 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
I det här fallet hamnar vi i det scenario där denna kommer att bli mindre,

509
00:41:30,930 --> 00:41:36,160
då vi uppdaterar denna pekare, detta en kommer att bli mindre, uppdatera,

510
00:41:36,160 --> 00:41:41,280
detta en är mindre och nu måste du erkänna

511
00:41:41,280 --> 00:41:44,220
när du faktiskt har slut på element att jämföra med.

512
00:41:44,220 --> 00:41:49,400
Eftersom vi redan har använt det hela matrisen,

513
00:41:49,400 --> 00:41:55,190
allt i denna array är nu bara in i här.

514
00:41:55,190 --> 00:42:02,040
Så om vi kör någonsin på den punkt där en av våra matriser är helt samman redan,

515
00:42:02,040 --> 00:42:06,510
då tar vi bara alla delar av den andra gruppen och infoga dem i slutet av arrayen.

516
00:42:06,510 --> 00:42:13,630
Så vi kan bara sätta in 4, 5, 6. Okej.

517
00:42:13,630 --> 00:42:18,070
Det är en sak att se upp för.

518
00:42:22,080 --> 00:42:26,120
Genomförandet av det borde vara steg 1.

519
00:42:26,120 --> 00:42:32,600
Sammanfoga sortera sedan utifrån det, det är 2 steg, 2 dumma steg.

520
00:42:38,800 --> 00:42:42,090
Låt oss bara ge denna array.

521
00:42:57,920 --> 00:43:05,680
Så sammanfoga sortering, är steg 1 att rekursivt bryta arrayen i halvor.

522
00:43:05,680 --> 00:43:09,350
Så dela denna array i halvor.

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

524
00:43:22,920 --> 00:43:25,800
Och nu gör vi det igen och vi dela dem i halvor.

525
00:43:25,800 --> 00:43:27,530
Jag ska bara göra det på den här sidan.

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

527
00:43:34,790 --> 00:43:37,440
Vi skulle göra samma sak här.

528
00:43:37,440 --> 00:43:40,340
Och nu har vi dela den i halvor igen.

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

530
00:43:51,080 --> 00:43:53,170
Så det är vår bas fallet.

531
00:43:53,170 --> 00:44:00,540
När matriserna är av storlek 1, då vi sluta med en uppdelning i två hälfter.

532
00:44:00,540 --> 00:44:03,190
>> Vad gör vi med det här?

533
00:44:03,190 --> 00:44:15,730
Vi avslutar upp detta också kommer att bryta ner till 8, 23, 42, och 108.

534
00:44:15,730 --> 00:44:24,000
Så nu när vi är på denna punkt, nu steg två i merge sort är bara samman par till listorna.

535
00:44:24,000 --> 00:44:27,610
Så vi vill sammanfoga dessa. Vi kallar bara samman.

536
00:44:27,610 --> 00:44:31,410
Vi vet att sammanslagningen kommer att återvända dessa i sorterad ordning.

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

538
00:44:33,920 --> 00:44:41,440
Nu vill vi slå samman dessa, och det kommer tillbaka en lista med de i sorterad ordning,

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

540
00:44:44,160 --> 00:44:57,380
Vi samman dem - jag kan inte skriva - 8, 23 och 42, 108.

541
00:44:57,380 --> 00:45:02,890
Så vi har gått samman par en gång.

542
00:45:02,890 --> 00:45:05,140
Nu har vi samman bara igen.

543
00:45:05,140 --> 00:45:10,130
Observera att var och en av dessa listor sorteras i sig,

544
00:45:10,130 --> 00:45:15,220
och då kan vi bara slå samman dessa listor för att få en lista med storlek 4, som sorteras

545
00:45:15,220 --> 00:45:19,990
och slå samman dessa två listor för att få en lista över storlek 4 som är sorterad.

546
00:45:19,990 --> 00:45:25,710
Och slutligen, kan vi slå ihop de två listor med storlek 4 för att få en lista med storlek 8 som sorteras.

547
00:45:25,710 --> 00:45:34,030
Så för att se att detta är totalt n log n såg vi redan att sammanfogningen är linjär,

548
00:45:34,030 --> 00:45:40,390
så när vi har att göra med sammanslagningen dessa, så som den totala kostnaden för sammanslagning

549
00:45:40,390 --> 00:45:43,410
för dessa två listor är bara 2 eftersom -

550
00:45:43,410 --> 00:45:49,610
Eller ja, det är O n, men n här är bara dessa 2 faktorer, så det är 2.

551
00:45:49,610 --> 00:45:52,850
Och dessa 2 blir 2 och dessa 2 blir 2 och dessa 2 blir 2,

552
00:45:52,850 --> 00:45:58,820
så över alla de övergår vi behöver göra, hamnar vi gör n.

553
00:45:58,820 --> 00:46:03,210
Liksom 2 + 2 + 2 + 2 är 8, vilket är n,

554
00:46:03,210 --> 00:46:08,060
så kostnaden för sammanslagning i denna uppsättning är n.

555
00:46:08,060 --> 00:46:10,810
Och sedan samma sak här.

556
00:46:10,810 --> 00:46:16,980
Vi kommer sammanfoga dessa 2, då dessa 2 och individuellt denna sammanslagning kommer att ta fyra operationer,

557
00:46:16,980 --> 00:46:23,610
denna sammanslagning kommer att ta fyra operationer, men återigen, mellan alla dessa,

558
00:46:23,610 --> 00:46:29,030
hamnar vi sammanslagning n TOTALA saker, och så detta steg tar n.

559
00:46:29,030 --> 00:46:33,670
Och så varje nivå tar n element slagits samman.

560
00:46:33,670 --> 00:46:36,110
>> Och hur många nivåer finns det?

561
00:46:36,110 --> 00:46:40,160
På varje nivå, växer vår uppsättning av storlek 2.

562
00:46:40,160 --> 00:46:44,590
Här våra matriser är av storlek 1, här är de i storlek 2, här är de i storlek 4,

563
00:46:44,590 --> 00:46:46,470
och slutligen, de är storlek 8.

564
00:46:46,470 --> 00:46:56,450
Så eftersom det fördubbling, finns det kommer att bli totalt log n dessa nivåer.

565
00:46:56,450 --> 00:47:02,090
Så med log n nivåer, varje nivå med n total verksamhet,

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

567
00:47:05,720 --> 00:47:07,790
Frågor?

568
00:47:08,940 --> 00:47:13,320
Har människor gjort redan framsteg på hur man ska genomföra det här?

569
00:47:13,320 --> 00:47:18,260
Är det någon som redan i ett tillstånd där jag kan bara dra upp sin kod?

570
00:47:20,320 --> 00:47:22,260
Jag kan ge en minut.

571
00:47:24,770 --> 00:47:27,470
Den här kommer att bli längre.

572
00:47:27,470 --> 00:47:28,730
Jag rekommenderar starkt återkommande -

573
00:47:28,730 --> 00:47:30,510
Du behöver inte göra rekursion för sammanfogningen

574
00:47:30,510 --> 00:47:33,750
eftersom att göra rekursion för sammanfogningen, du kommer att behöva passera ett gäng olika storlekar.

575
00:47:33,750 --> 00:47:37,150
Du kan, men det är irriterande.

576
00:47:37,150 --> 00:47:43,720
Men rekursion för typ själv är ganska enkelt.

577
00:47:43,720 --> 00:47:49,190
Du bara bokstavligen ringa Sortera på vänster halv, sortera på höger halva. Okej.

578
00:47:51,770 --> 00:47:54,860
Någon har något jag kan dra upp ännu?

579
00:47:54,860 --> 00:47:57,540
Eller så ska jag ge en minut.

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

581
00:47:59,900 --> 00:48:02,970
Någon har något vi kan arbeta med?

582
00:48:05,450 --> 00:48:09,680
Eller så kommer vi bara arbeta med detta och expandera sedan därifrån.

583
00:48:09,680 --> 00:48:14,050
>> Någon har mer än detta som jag kan dra upp?

584
00:48:14,050 --> 00:48:17,770
[Eleven] Ja. Du kan dra upp mig. >> Okej.

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

586
00:48:22,170 --> 00:48:25,280
[Elev] Det fanns en hel del villkor. >> Åh, skjuta. Kan du -

587
00:48:25,280 --> 00:48:28,110
[Elev] Jag har att spara den. >> Ja.

588
00:48:32,420 --> 00:48:35,730
Så vi gjorde kopplingen separat.

589
00:48:35,730 --> 00:48:38,570
Åh, men det är inte så illa.

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

591
00:48:41,650 --> 00:48:47,080
Så Sortera själv bara ringa mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Förklara för oss vad mergeSortHelp gör.

593
00:48:49,530 --> 00:48:55,700
[Eleven] MergeSortHelp ganska gör mycket de två viktigaste stegen,

594
00:48:55,700 --> 00:49:01,270
vilket är att sortera varje halva av gruppen och sedan sammanfoga dem båda.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Okej, så ge mig en sekund.

596
00:49:10,850 --> 00:49:13,210
Jag tror att detta - >> [elev] Jag behöver -

597
00:49:17,100 --> 00:49:19,400
Ja. Jag saknar något.

598
00:49:19,400 --> 00:49:23,100
I samman, inser jag att jag måste skapa en ny array

599
00:49:23,100 --> 00:49:26,530
eftersom jag inte kunde göra det på plats. >> Ja. Du kan inte. Rätta.

600
00:49:26,530 --> 00:49:28,170
[Elev] Så jag skapar en ny array.

601
00:49:28,170 --> 00:49:31,510
Jag glömde i slutet av samman till nytt förändras.

602
00:49:31,510 --> 00:49:34,490
Okej. Vi behöver en ny array.

603
00:49:34,490 --> 00:49:41,000
I sammanslagning sortera, är det nästan alltid sant.

604
00:49:41,000 --> 00:49:44,340
En del av kostnaderna för en bättre algoritm tidsmässigt

605
00:49:44,340 --> 00:49:47,310
är nästan alltid behöva använda lite mer minne.

606
00:49:47,310 --> 00:49:51,570
Så här, oavsett hur du gör ihop sortera,

607
00:49:51,570 --> 00:49:54,780
du skulle oundvikligen behöva använda lite extra minne.

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

609
00:49:58,240 --> 00:50:03,400
Och då säger du i slutet vi bara behöver kopiera ny array i den ursprungliga arrayen.

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

611
00:50:04,830 --> 00:50:08,210
Jag vet inte om det fungerar när det gäller att räkna med hänvisning eller något annat -

612
00:50:08,210 --> 00:50:11,650
Ja, kommer det att fungera. >> [Elev] Okej.

613
00:50:20,620 --> 00:50:24,480
Har du försökt köra det här? >> [Elev] Nej, inte än. >> Okej.

614
00:50:24,480 --> 00:50:28,880
Försök att köra den och sedan ska jag prata om det för en sekund.

615
00:50:28,880 --> 00:50:35,200
[Elev] Jag behöver ha alla funktioner prototyper och allt, men hur?

616
00:50:37,640 --> 00:50:40,840
Funktionen prototyper. Du menar som - Ja.

617
00:50:40,840 --> 00:50:43,040
Sortera kallar mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Så för att sortera att kalla mergeSortHelp måste mergeSortHelp antingen har definierats

619
00:50:47,390 --> 00:50:56,370
innan sortera eller behöver vi bara en prototyp. Bara kopiera och klistra in det.

620
00:50:56,370 --> 00:50:59,490
Och på samma sätt är mergeSortHelp ringer samman,

621
00:50:59,490 --> 00:51:03,830
men sammanfogning inte har definierats ännu, så vi kan bara låta mergeSortHelp veta

622
00:51:03,830 --> 00:51:08,700
att det är vad samman kommer att se ut, och det är det.

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

624
00:51:22,770 --> 00:51:32,660
Vi har en fråga här där vi inte har någon basfall.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp är rekursiv, så någon rekursiv funktion

626
00:51:38,110 --> 00:51:42,610
kommer att behöva någon form av basfallet att veta när du ska sluta rekursivt kallar sig.

627
00:51:42,610 --> 00:51:45,590
Vad är vår bas fall kommer att vara här? Ja.

628
00:51:45,590 --> 00:51:49,110
[Eleven] Om storleken är 1? >> [Bowden] Ja.

629
00:51:49,110 --> 00:51:56,220
Så som vi såg där, vi slutade dela arrayer

630
00:51:56,220 --> 00:52:01,850
när vi fått in matriser av storlek 1, vilket oundvikligen är sorterade själva.

631
00:52:01,850 --> 00:52:09,530
Så om storlek är lika med 1, vet vi matrisen redan sorteras,

632
00:52:09,530 --> 00:52:12,970
så att vi kan bara gå tillbaka.

633
00:52:12,970 --> 00:52:16,880
>> Notera att det är ogiltigt, så att vi inte returnera något särskilt, återvänder vi bara.

634
00:52:16,880 --> 00:52:19,580
Okej. Så det är vår bas fallet.

635
00:52:19,580 --> 00:52:27,440
Jag antar att vår bas fall också skulle kunna vara om vi råkar sammanslagning en rad storlek 0,

636
00:52:27,440 --> 00:52:30,030
Vi vill nog stanna vid något tillfälle,

637
00:52:30,030 --> 00:52:33,610
så vi kan bara säga storlek mindre än 2 eller mindre än eller lika med 1

638
00:52:33,610 --> 00:52:37,150
så att detta kommer att fungera för alla matris nu.

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

640
00:52:38,870 --> 00:52:42,740
Så det är vår bas fallet.

641
00:52:42,740 --> 00:52:45,950
Nu vill du gå oss genom sammanslagning?

642
00:52:45,950 --> 00:52:49,140
Vad gör alla dessa fall menar?

643
00:52:49,140 --> 00:52:54,480
Här uppe, vi gör precis samma idé, -

644
00:52:56,970 --> 00:53:02,470
[Elev] Jag måste passera storlek med alla mergeSortHelp samtal.

645
00:53:02,470 --> 00:53:10,080
Jag lade storlek som en ytterligare primär och det är inte där, liksom storlek / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Åh, storlek / 2, storlek / 2. >> [Studenten] Ja, och även i ovanstående funktion.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Här? >> [Elev] Bara storlek. >> [Bowden] Oh. Storlek, storlek? >> [Elev] Ja.

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

649
00:53:23,010 --> 00:53:26,580
Låt mig tänka för en sekund.

650
00:53:26,580 --> 00:53:28,780
Kör vi på en fråga?

651
00:53:28,780 --> 00:53:33,690
Vi är alltid behandla vänster som 0. >> [Eleven] Nej

652
00:53:33,690 --> 00:53:36,340
Det är fel också. Ursäkta. Det bör vara början. Ja.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Okej. Jag gillar det bättre.

654
00:53:39,230 --> 00:53:43,880
Och slut. Okej.

655
00:53:43,880 --> 00:53:47,200
Så nu vill du gå oss genom sammanslagning? >> [Elev] Okej.

656
00:53:47,200 --> 00:53:52,150
Jag bara gå igenom det nya array som jag har skapat.

657
00:53:52,150 --> 00:53:57,420
Dess storlek är storleken på den del av matrisen som vi vill ska sorteras

658
00:53:57,420 --> 00:54:03,460
och försöker hitta element som jag skulle sätta i den nya arrayen steget.

659
00:54:03,460 --> 00:54:10,140
Så för att göra det först jag kontrollera om den vänstra halvan av matrisen fortsätter att ha några fler element,

660
00:54:10,140 --> 00:54:14,260
och om det inte gör det, då du gå ner till den andra tillstånd, som bara säger

661
00:54:14,260 --> 00:54:20,180
okej, det måste vara i rätt mängd, och vi ska sätta det i den nuvarande index newArray.

662
00:54:20,180 --> 00:54:27,620
>> Och sedan annars jag kontrollera om den högra sidan av matrisen också klar,

663
00:54:27,620 --> 00:54:30,630
i vilket fall jag satte bara i vänster.

664
00:54:30,630 --> 00:54:34,180
Det kanske inte egentligen behövas. Jag är inte säker.

665
00:54:34,180 --> 00:54:40,970
Men hur som helst, de andra två kontroll som av två är mindre i vänster eller höger.

666
00:54:40,970 --> 00:54:49,770
Och även i varje enskilt fall, jag uppräkning beroende platshållare jag öka.

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

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

669
00:54:53,840 --> 00:54:58,800
Har någon synpunkter eller funderingar eller frågor?

670
00:55:00,660 --> 00:55:07,720
Så de fyra fall som vi måste ta saker i att bara vara - eller det ser ut som fem -

671
00:55:07,720 --> 00:55:13,100
men vi måste överväga om den vänstra matrisen har slut på saker vi måste gå samman,

672
00:55:13,100 --> 00:55:16,390
om rätten arrayen har slut på saker vi måste slå samman -

673
00:55:16,390 --> 00:55:18,400
Jag pekar på ingenting.

674
00:55:18,400 --> 00:55:21,730
Så om den vänstra matrisen har slut på saker eller rätt arrayen har slut på saker.

675
00:55:21,730 --> 00:55:24,320
Det är två fall.

676
00:55:24,320 --> 00:55:30,920
Vi behöver också det triviala fallet om den vänstra sak är mindre än den rätta.

677
00:55:30,920 --> 00:55:33,910
Då vi vill välja den vänstra sak.

678
00:55:33,910 --> 00:55:37,630
Det är fallen.

679
00:55:37,630 --> 00:55:40,990
Så detta var rätt, så det är det.

680
00:55:40,990 --> 00:55:46,760
Array vänster. Det är 1, 2, 3. Okej. Så ja, det är de fyra saker vi kanske vill göra.

681
00:55:50,350 --> 00:55:54,510
Och vi kommer inte att gå över en iterativ lösning.

682
00:55:54,510 --> 00:55:55,980
Jag skulle inte rekommendera -

683
00:55:55,980 --> 00:56:03,070
Merge sortera är ett exempel på en funktion som är både inte svans rekursiv,

684
00:56:03,070 --> 00:56:07,040
det är inte lätt att göra det svans rekursiv,

685
00:56:07,040 --> 00:56:13,450
men även det är inte lätt att göra det iterativa.

686
00:56:13,450 --> 00:56:16,910
Detta är mycket enkelt.

687
00:56:16,910 --> 00:56:19,170
Denna implementering av sammanslagning sortera,

688
00:56:19,170 --> 00:56:22,140
samman, oavsett vad du gör, du kommer att bygga merge.

689
00:56:22,140 --> 00:56:29,170
>> Så sammanfoga Sortera byggd ovanpå Merge rekursivt bara dessa tre linjer.

690
00:56:29,170 --> 00:56:34,700
Iterativt, det är mer irriterande och svårare att tänka på.

691
00:56:34,700 --> 00:56:41,860
Men notera att det inte är svansen rekursivt sedan mergeSortHelp - när det kallar sig -

692
00:56:41,860 --> 00:56:46,590
Det behöver fortfarande göra saker efter detta rekursivt anrop avkastning.

693
00:56:46,590 --> 00:56:50,830
Så denna stack ram måste fortsätta att existera även efter kräver detta.

694
00:56:50,830 --> 00:56:54,170
Och sedan när du ringer detta måste stackram fortsätta att existera

695
00:56:54,170 --> 00:56:57,780
eftersom även efter det samtalet, måste vi ändå att gå samman.

696
00:56:57,780 --> 00:57:01,920
Och det är triviala att göra denna svans rekursiv.

697
00:57:04,070 --> 00:57:06,270
Frågor?

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

699
00:57:09,860 --> 00:57:13,400
Så gå tillbaka att sortera - Åh, det är två saker jag vill visa. Okej.

700
00:57:13,400 --> 00:57:17,840
Gå tillbaka för att sortera, vi gör det snabbt.

701
00:57:17,840 --> 00:57:21,030
Eller sök. Sortera? Sortera. Ja.

702
00:57:21,030 --> 00:57:22,730
Gå tillbaka till början av slag.

703
00:57:22,730 --> 00:57:29,870
Vi vill skapa en algoritm som sorterar arrayen med någon algoritm

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

705
00:57:33,660 --> 00:57:40,860
Så hur är detta möjligt? Har någon någon form av -

706
00:57:40,860 --> 00:57:44,300
Jag antydde tidigare på -

707
00:57:44,300 --> 00:57:48,300
Om vi ​​ska förbättras från n log n till O n,

708
00:57:48,300 --> 00:57:51,450
Vi har förbättrat vår algoritm tidsmässigt,

709
00:57:51,450 --> 00:57:55,250
vilket innebär vad vi kommer att behöva göra för att kompensera för det?

710
00:57:55,250 --> 00:57:59,520
[Elev] Space. >> Ja. Vi kommer att använda mer utrymme.

711
00:57:59,520 --> 00:58:04,490
Och inte ens bara mer utrymme, det är exponentiellt mer utrymme.

712
00:58:04,490 --> 00:58:14,320
Så jag tror att denna typ av algoritm är pseudo något, pseudo polynom -

713
00:58:14,320 --> 00:58:18,980
pseudo - Jag kan inte minnas. Pseudo något.

714
00:58:18,980 --> 00:58:22,210
Men det är för att vi måste använda så mycket utrymme

715
00:58:22,210 --> 00:58:28,610
att detta är möjligt, men inte realistiskt.

716
00:58:28,610 --> 00:58:31,220
>> Och hur uppnår vi detta?

717
00:58:31,220 --> 00:58:36,810
Vi kan uppnå detta om vi garanterar att en viss element i arrayen

718
00:58:36,810 --> 00:58:39,600
är under en viss storlek.

719
00:58:42,070 --> 00:58:44,500
Så låt oss bara säga att storleken är 200,

720
00:58:44,500 --> 00:58:48,130
alla element i en array är under storlek 200.

721
00:58:48,130 --> 00:58:51,080
Och detta är faktiskt mycket realistiskt.

722
00:58:51,080 --> 00:58:58,660
Du kan enkelt få en array som du vet allt i den

723
00:58:58,660 --> 00:59:00,570
kommer att vara mindre än ett visst antal.

724
00:59:00,570 --> 00:59:07,400
Precis som om du har några absolut massiva vektor eller något

725
00:59:07,400 --> 00:59:11,810
men du vet allt kommer att vara mellan 0 och 5,

726
00:59:11,810 --> 00:59:14,790
då det kommer att vara betydligt snabbare att göra detta.

727
00:59:14,790 --> 00:59:17,930
Och den bundna på något av elementen är 5,

728
00:59:17,930 --> 00:59:21,980
så detta bundna, det vill säga hur mycket minne du kommer att använda.

729
00:59:21,980 --> 00:59:26,300
Så bundna är 200.

730
00:59:26,300 --> 00:59:32,960
I teorin finns det alltid en bunden eftersom ett heltal kan bara vara upp till 4 miljarder,

731
00:59:32,960 --> 00:59:40,600
men det är orealistiskt sedan vi skulle använda utrymme

732
00:59:40,600 --> 00:59:44,400
i storleksordningen 4 miljarder. Så det är orealistiskt.

733
00:59:44,400 --> 00:59:47,060
Men här ska vi säga vår gräns är 200.

734
00:59:47,060 --> 00:59:59,570
Tricket att göra det i O n är att vi gör ett annat array med namnet räkningar av storlek bunden.

735
00:59:59,570 --> 01:00:10,470
Så egentligen är det en genväg för - jag faktiskt vet inte om klang gör detta.

736
01:00:11,150 --> 01:00:15,330
Men i GCC åtminstone - jag antar klang gör det också -

737
01:00:15,330 --> 01:00:18,180
Detta kommer bara initiera hela gruppen att vara 0s.

738
01:00:18,180 --> 01:00:25,320
Så om jag inte vill göra det, då kunde jag separat göra for (int i = 0;

739
01:00:25,320 --> 01:00:31,500
I <BOUND, jag + +) och räknar [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Så nu är allt initieras till 0.

741
01:00:35,260 --> 01:00:39,570
Jag iterera över min array,

742
01:00:39,570 --> 01:00:51,920
och vad jag gör är att jag räknar antalet av varje - låt oss gå ner hit.

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
Vad jag räknar är antalet förekomster av varje enskild beståndsdel.

745
01:01:00,010 --> 01:01:03,470
Låt oss verkligen lägga till ett par mer här med några upprepningar.

746
01:01:03,470 --> 01:01:11,070
Så värdet vi har här, är värdet av det kommer att vara array [i].

747
01:01:11,070 --> 01:01:14,850
Så val kan vara 4 eller 8 eller vad som helst.

748
01:01:14,850 --> 01:01:18,870
Och nu är jag räkna hur många av det värde som jag har sett,

749
01:01:18,870 --> 01:01:21,230
så räknas [Val] + +;

750
01:01:21,230 --> 01:01:29,430
Efter detta är gjort, är räkningar kommer att se ut ungefär som 0001.

751
01:01:29,430 --> 01:01:42,190
Låt oss göra räknas [Val] - BUNDEN + 1.

752
01:01:42,190 --> 01:01:48,230
>> Nu det är bara att ta hänsyn till att vi börjar från 0.

753
01:01:48,230 --> 01:01:50,850
Så om 200 kommer att bli vår största antalet,

754
01:01:50,850 --> 01:01:54,720
sedan från 0 till 200 är 201 saker.

755
01:01:54,720 --> 01:02:01,540
Så räknas, det ska se ut som 00.001 eftersom vi har en 4.

756
01:02:01,540 --> 01:02:10,210
Då kommer vi att ha 0001 där vi kommer att ha en 1 i den 8: e index räknas.

757
01:02:10,210 --> 01:02:14,560
Vi kommer att ha en 2 i den 23: e index räknas.

758
01:02:14,560 --> 01:02:17,630
Vi kommer att ha en 2 i den 42: a index räknas.

759
01:02:17,630 --> 01:02:21,670
Så vi kan använda räkningen.

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

761
01:02:44,920 --> 01:02:52,540
Och så om num_of_item är 2, betyder det att vi vill infoga 2 av antalet i

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

763
01:02:55,290 --> 01:03:02,000
Så vi måste hålla reda på hur långt vi är i arrayen.

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

765
01:03:05,470 --> 01:03:09,910
Array - Jag ska bara skriva det.

766
01:03:16,660 --> 01:03:18,020
Räknar -

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

768
01:03:28,580 --> 01:03:32,490
Är det vad jag vill? Jag tror att det är vad jag vill.

769
01:03:35,100 --> 01:03:38,290
Ja, här ser bra ut. Okej.

770
01:03:38,290 --> 01:03:43,050
Så förstår alla vad syftet med mitt räknas array är?

771
01:03:43,050 --> 01:03:48,140
Det räknar antalet förekomster av varje av dessa siffror.

772
01:03:48,140 --> 01:03:51,780
Då jag iteration över som räknas array,

773
01:03:51,780 --> 01:03:57,190
och den i: te plats i räknas arrayen

774
01:03:57,190 --> 01:04:01,930
är antalet i det som ska visas i mitt sorterade arrayen.

775
01:04:01,930 --> 01:04:06,840
Det är därför räknas av 4 kommer att bli 1

776
01:04:06,840 --> 01:04:11,840
och räkningar av 8 kommer att bli 1, räkningar av 23 kommer att vara 2.

777
01:04:11,840 --> 01:04:16,900
Så det är hur många av dem jag vill infoga i mitt sorterade arrayen.

778
01:04:16,900 --> 01:04:19,200
Sen gör jag just det.

779
01:04:19,200 --> 01:04:28,960
Jag sätter num_of_item I är i min sorterade arrayen.

780
01:04:28,960 --> 01:04:31,670
>> Frågor?

781
01:04:32,460 --> 01:04:43,100
Och så igen, detta är linjär tid eftersom vi bara iterera över detta en gång,

782
01:04:43,100 --> 01:04:47,470
men det är också linjär i vad denna siffra råkar vara,

783
01:04:47,470 --> 01:04:50,730
och så det beror mycket på vad din gräns är.

784
01:04:50,730 --> 01:04:53,290
Med en bunden av 200, det är inte så illa.

785
01:04:53,290 --> 01:04:58,330
Om din bunden kommer att bli 10.000, då det är lite värre,

786
01:04:58,330 --> 01:05:01,360
men om ditt bundna kommer att bli 4 miljarder, det är helt orealistiskt

787
01:05:01,360 --> 01:05:07,720
och denna uppsättning kommer att vara av storlek 4 miljarder, vilket är orealistiskt.

788
01:05:07,720 --> 01:05:10,860
Så det är det. Frågor?

789
01:05:10,860 --> 01:05:13,270
[Ohörbart elev svar] >> Okej.

790
01:05:13,270 --> 01:05:15,710
Jag insåg en annan sak när vi går igenom.

791
01:05:17,980 --> 01:05:23,720
Jag tror att problemet var i Lucas och förmodligen varenda en som vi har sett.

792
01:05:23,720 --> 01:05:26,330
Jag glömde helt.

793
01:05:26,330 --> 01:05:31,040
Det enda jag ville kommentera är att när du arbetar med saker som index,

794
01:05:31,040 --> 01:05:38,320
du aldrig riktigt se det när du skriver en for-slinga,

795
01:05:38,320 --> 01:05:41,120
men tekniskt, när du arbetar med dessa index,

796
01:05:41,120 --> 01:05:45,950
bör du ganska mycket alltid hantera heltal utan tecken.

797
01:05:45,950 --> 01:05:53,850
Anledningen till detta är när du arbetar med signerade heltal,

798
01:05:53,850 --> 01:05:56,090
så om du har 2 signerade heltal och du lägger ihop dem

799
01:05:56,090 --> 01:06:00,640
och de hamnar för stor, då du sluta med ett negativt tal.

800
01:06:00,640 --> 01:06:03,410
Så det är vad heltalsspill är.

801
01:06:03,410 --> 01:06:10,500
>> Om jag lägger 2 miljarder och 1 miljard avslutar jag med negativ 1 miljard.

802
01:06:10,500 --> 01:06:15,480
Det är så heltal fungerar på datorer.

803
01:06:15,480 --> 01:06:17,510
Så problemet med att använda -

804
01:06:17,510 --> 01:06:23,500
Det är bra förutom om låg råkar vara 2 miljarder och upp råkar vara 1 miljard

805
01:06:23,500 --> 01:06:27,120
då detta kommer att vara negativ 1 miljard och då ska vi dela den med 2

806
01:06:27,120 --> 01:06:29,730
och sluta med negativ 500 miljoner.

807
01:06:29,730 --> 01:06:33,760
Så detta är bara en fråga om du råkar vara att söka igenom en array

808
01:06:33,760 --> 01:06:38,070
av miljarder saker.

809
01:06:38,070 --> 01:06:44,050
Men om låg + upp händer att svämma över, så det är ett problem.

810
01:06:44,050 --> 01:06:47,750
Så snart vi gör dem osignerad, sedan 2 miljarder plus 1 miljard 3 miljarder.

811
01:06:47,750 --> 01:06:51,960
3 miljarder delat med 2 är 1,5 miljarder euro.

812
01:06:51,960 --> 01:06:55,670
Så snart som de är osignerad, är allt perfekt.

813
01:06:55,670 --> 01:06:59,900
Och så det är också en fråga när du skriver din för loopar,

814
01:06:59,900 --> 01:07:03,940
och faktiskt, det gör det nog det automatiskt.

815
01:07:09,130 --> 01:07:12,330
Det kommer faktiskt bara skrika på dig.

816
01:07:12,330 --> 01:07:21,610
Så om detta antal är för stor för att vara i bara ett heltal, men det skulle passa i ett heltal utan tecken,

817
01:07:21,610 --> 01:07:24,970
det kommer skrika på dig, så det är därför du aldrig verkligen köra i frågan.

818
01:07:29,150 --> 01:07:34,820
Du kan se att ett index aldrig kommer att bli negativt,

819
01:07:34,820 --> 01:07:39,220
och så när du iterera över en array,

820
01:07:39,220 --> 01:07:43,970
Du kan nästan alltid säga unsigned int i, men du egentligen inte behöver.

821
01:07:43,970 --> 01:07:47,110
Saker kommer att arbeta ganska mycket lika bra.

822
01:07:48,740 --> 01:07:50,090
Okej. [Viskar] Vad är klockan?

823
01:07:50,090 --> 01:07:54,020
Det sista jag ville visa - och jag ska bara göra det riktigt snabbt.

824
01:07:54,020 --> 01:08:03,190
Du vet hur vi # har definierar så att vi kan # define MAX som 5 eller något?

825
01:08:03,190 --> 01:08:05,940
Låt oss inte göra MAX. # Define bundna som 200. Det är vad vi gjorde innan.

826
01:08:05,940 --> 01:08:10,380
Som definierar en konstant, som just kommer att kopieras och klistras

827
01:08:10,380 --> 01:08:13,010
varhelst vi råkar skriva bunden.

828
01:08:13,010 --> 01:08:18,189
>> Så vi kan faktiskt göra mer med # definierar.

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

830
01:08:21,170 --> 01:08:23,410
De är inte riktigt fungerar, men vi kallar dem fungerar.

831
01:08:23,410 --> 01:08:36,000
Ett exempel skulle vara något som MAX (x, y) definieras som (x <y y:? X). Okej.

832
01:08:36,000 --> 01:08:40,660
Så du bör vänja sig ternära operatören syntax,

833
01:08:40,660 --> 01:08:49,029
men är x mindre än y? Avkastning y, annars återvänder X.

834
01:08:49,029 --> 01:08:54,390
Så du kan se att du kan göra detta till en separat funktion,

835
01:08:54,390 --> 01:09:01,399
och funktionen skulle kunna se ut bool MAX tar 2 argument, returnera denna.

836
01:09:01,399 --> 01:09:08,340
Detta är en av de vanligaste som jag ser gjort så här. Vi kallar dem makron.

837
01:09:08,340 --> 01:09:11,790
Detta är ett makro.

838
01:09:11,790 --> 01:09:15,859
Detta är bara syntaxen för det.

839
01:09:15,859 --> 01:09:18,740
Du kan skriva ett makro för att göra vad du vill.

840
01:09:18,740 --> 01:09:22,649
Du ser ofta makron för felsökning printfs och sånt.

841
01:09:22,649 --> 01:09:29,410
Så en typ av printf finns särskilda konstanter i C som understreck LINE understreck,

842
01:09:29,410 --> 01:09:31,710
2 understryker LINE understreck,

843
01:09:31,710 --> 01:09:37,550
och det finns också tror jag 2 understryker FUNC. Det kan vara det. Nåt sånt.

844
01:09:37,550 --> 01:09:40,880
Dessa saker kommer att ersättas med namnet på funktionen

845
01:09:40,880 --> 01:09:42,930
eller numret på linjen som du är på.

846
01:09:42,930 --> 01:09:48,630
Ofta skriver man felsökning printfs ner det här jag sedan bara kunde skriva

847
01:09:48,630 --> 01:09:54,260
Felsöka och det kommer ut radnummer och funktion som jag råkar vara i

848
01:09:54,260 --> 01:09:57,020
att det uppstått som DEBUG uttalande.

849
01:09:57,020 --> 01:09:59,550
Och du kan också skriva ut andra saker.

850
01:09:59,550 --> 01:10:05,990
Så en sak du bör se upp för är om jag råkar # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
som något som 2 * y och 2 * x.

852
01:10:11,380 --> 01:10:14,310
Så av någon anledning råkar dig att göra det en hel del.

853
01:10:14,310 --> 01:10:16,650
Så gör det till en makro.

854
01:10:16,650 --> 01:10:18,680
Detta är faktiskt bryts.

855
01:10:18,680 --> 01:10:23,050
Jag skulle vilja kalla det genom att göra något liknande DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Så vad ska återlämnas?

857
01:10:28,840 --> 01:10:30,580
[Elev] 12.

858
01:10:30,580 --> 01:10:34,800
Ja, 12 återlämnas, och 12 returneras.

859
01:10:34,800 --> 01:10:43,350
3 blir ersatt för x, blir 6 ersättas för y och vi återkommer 2 * 6, vilket är 12.

860
01:10:43,350 --> 01:10:47,710
Nu vad om det här? Vad ska återlämnas?

861
01:10:47,710 --> 01:10:50,330
[Elev] 14. >> Helst 14.

862
01:10:50,330 --> 01:10:55,290
Frågan är hur hash definierar arbetet, kom ihåg att det är en bokstavlig kopiera och klistra in

863
01:10:55,290 --> 01:11:00,160
av ganska mycket allt, så vad detta kommer att tolkas som

864
01:11:00,160 --> 01:11:11,270
är 3 färre än 1 plus 6, 2 gånger 1 plus 6, 2 gånger 3.

865
01:11:11,270 --> 01:11:19,780
>> Så av denna anledning du nästan alltid packa allt i parentes.

866
01:11:22,180 --> 01:11:25,050
Varje variabel som du nästan alltid packa inom parentes.

867
01:11:25,050 --> 01:11:29,570
Det finns fall där man inte behöver, som jag vet att jag inte behöver göra det här

868
01:11:29,570 --> 01:11:32,110
eftersom mindre än är ganska mycket alltid bara kommer att fungera,

869
01:11:32,110 --> 01:11:34,330
även om det kanske inte ens är sant.

870
01:11:34,330 --> 01:11:41,870
Om det är något löjligt som DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
då det kommer att bli ersatt med 3 mindre än 1 lika lika 2,

872
01:11:49,760 --> 01:11:53,460
och så då det kommer att göra 3 mindre än 1, betyder det lika 2,

873
01:11:53,460 --> 01:11:55,620
vilket är inte vad vi vill ha.

874
01:11:55,620 --> 01:12:00,730
Så för att undvika eventuella operatorprioritet problem,

875
01:12:00,730 --> 01:12:02,870
alltid svepa inom parentes.

876
01:12:03,290 --> 01:12:07,700
Okej. Och det är det, 5:30.

877
01:12:08,140 --> 01:12:12,470
Om du har några frågor om pset, låt oss veta.

878
01:12:12,470 --> 01:12:18,010
Det ska vara kul, och hacker upplagan är också betydligt mer realistisk

879
01:12:18,010 --> 01:12:22,980
än hackare upplagan av förra årets, så vi hoppas att många av er prova.

880
01:12:22,980 --> 01:12:26,460
Förra årets var mycket överväldigande.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]