1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Sectie 3 - Meer Comfortabele]

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

3
00:00:05,070 --> 00:00:07,310
>> [Dit is CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Dus de eerste vraag is vreemd geformuleerd.

5
00:00:12,700 --> 00:00:17,480
GDB kunt u "debuggen" een programma, maar, meer in het bijzonder, wat doet het laten doen?

6
00:00:17,480 --> 00:00:22,590
Ik zal antwoorden dat, en ik weet niet wat er precies verwacht,

7
00:00:22,590 --> 00:00:27,910
dus ik denk dat het iets in de trant van het laat je stap voor stap

8
00:00:27,910 --> 00:00:31,540
lopen door het programma, interactie met het, verandering variabelen, doe al deze dingen -

9
00:00:31,540 --> 00:00:34,270
wezen volledige controle uitvoering van een programma

10
00:00:34,270 --> 00:00:38,410
en inspecteren elk onderdeel van de uitvoering van het programma.

11
00:00:38,410 --> 00:00:43,030
Dus die functies kunt u debuggen dingen.

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

13
00:00:44,830 --> 00:00:50,520
Waarom heeft binair zoeken voor dat een array gesorteerd?

14
00:00:50,520 --> 00:00:53,360
Wie wil antwoord op geven?

15
00:00:56,120 --> 00:01:00,070
[Student] Omdat het niet werkt als het niet gesorteerd. >> Ja. [Gelach]

16
00:01:00,070 --> 00:01:04,910
Als het niet gesorteerd, dan is het onmogelijk om het in tweeën

17
00:01:04,910 --> 00:01:07,850
en weet dat alles aan de linkerkant is minder en alles op de juiste

18
00:01:07,850 --> 00:01:10,490
groter is dan de gemiddelde waarde.

19
00:01:10,490 --> 00:01:12,790
Dus het moet worden gesorteerd.

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

21
00:01:14,170 --> 00:01:17,570
Waarom is bubble sort in O n kwadraat?

22
00:01:17,570 --> 00:01:23,230
Is er iemand die wil eerst een zeer snelle high-level overzicht van wat bubble sort is geven?

23
00:01:25,950 --> 00:01:33,020
[Student] Je eigenlijk gaan door elk element en u de eerste paar elementen.

24
00:01:33,020 --> 00:01:37,150
Als ze uit waar je ruilen, dan u de komende elementen en ga zo maar door.

25
00:01:37,150 --> 00:01:40,770
Als u het einde bereikt, dan weet je dat het grootste element wordt geplaatst aan het einde,

26
00:01:40,770 --> 00:01:42,750
dus je negeren dat men dan blijf je doormaakt,

27
00:01:42,750 --> 00:01:48,490
en elke keer moet je een minder element controleren totdat u geen wijzigingen. >> Ja.

28
00:01:48,490 --> 00:01:58,470
Het heet bubble sort, want als je de array draait op zijn kant dus het is op en neer, verticaal,

29
00:01:58,470 --> 00:02:03,100
dan is de grote waarden zal zinken naar de bodem en de kleine waarden wil borrelen naar de top.

30
00:02:03,100 --> 00:02:05,210
Dat is hoe het zijn naam kreeg.

31
00:02:05,210 --> 00:02:08,220
En ja, je gewoon doorlopen.

32
00:02:08,220 --> 00:02:11,190
Je blijft gaan door de array, het omwisselen van de hogere waarde

33
00:02:11,190 --> 00:02:14,040
de grootste waarden op de bodem.

34
00:02:14,040 --> 00:02:17,500
>> Waarom is het O van n kwadraat?

35
00:02:18,690 --> 00:02:24,620
Ten eerste, wil iemand zeggen waarom het O van n kwadraat?

36
00:02:24,620 --> 00:02:28,760
[Student] Want voor elke run het n keer gaat.

37
00:02:28,760 --> 00:02:32,100
U kunt alleen zeker van zijn dat je hebt genomen het grootste element helemaal naar beneden,

38
00:02:32,100 --> 00:02:35,230
dan moet je dat herhalen voor zo veel elementen. >> Ja.

39
00:02:35,230 --> 00:02:41,800
Dus hou in gedachten wat grote O betekent en wat grote Omega betekent.

40
00:02:41,800 --> 00:02:50,560
De grote O is als de bovengrens op hoe traag het daadwerkelijk kan draaien.

41
00:02:50,560 --> 00:02:58,990
Dus door te zeggen dat de O van n kwadraat, is het niet O van n of anders zou het te kunnen draaien

42
00:02:58,990 --> 00:03:02,640
in lineaire tijd, maar het is O van n blokjes

43
00:03:02,640 --> 00:03:06,390
omdat het begrensd door O n blokjes.

44
00:03:06,390 --> 00:03:12,300
Als het begrensd door O van n kwadraat, dan is het ook begrensd door n blokjes.

45
00:03:12,300 --> 00:03:20,280
Zodat het N kwadraat en in het ergste geval kan niet beter dan n kwadraat,

46
00:03:20,280 --> 00:03:22,830
dat is waarom het is O van n in het kwadraat.

47
00:03:22,830 --> 00:03:31,200
Dus om lichte wiskunde zien hoe het komt te zijn n kwadraat,

48
00:03:31,200 --> 00:03:40,530
als we vijf dingen in onze lijst, de eerste keer hoeveel swaps kunnen we mogelijk moeten maken

49
00:03:40,530 --> 00:03:47,170
om dit te krijgen? Laten we eigenlijk alleen maar -

50
00:03:47,170 --> 00:03:52,040
Hoeveel swaps gaan we moeten in de eerste run van bubble sort maken door middel van de array?

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

52
00:03:53,540 --> 00:03:58,340
>> Als er 5 elementen, gaan we nodig hebben om n te maken - 1.

53
00:03:58,340 --> 00:04:01,100
Dan op de tweede hoeveel swaps gaan we moeten maken?

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

55
00:04:03,440 --> 00:04:11,640
En de derde gaat worden n - 3, en dan voor het gemak zal ik schrijven de laatste twee

56
00:04:11,640 --> 00:04:15,270
want dan gaan we nodig hebben om 2 swaps en 1 swap te maken.

57
00:04:15,270 --> 00:04:19,899
Ik denk dat de laatste al dan niet echt nodig te gebeuren.

58
00:04:19,899 --> 00:04:22,820
Is het een swap? Ik weet het niet.

59
00:04:22,820 --> 00:04:26,490
Dus dit zijn de totale bedragen van de swaps of op zijn minst vergelijkingen die je moet maken.

60
00:04:26,490 --> 00:04:29,910
Zelfs als je niet ruilen, moet je nog steeds de waarden te vergelijken.

61
00:04:29,910 --> 00:04:33,910
Er zijn n - 1 vergelijkingen in de eerste run door de array.

62
00:04:33,910 --> 00:04:42,050
Als u herschikken deze dingen, laten we in feite maakt het zes dingen dus dingen goed stapelen,

63
00:04:42,050 --> 00:04:44,790
en dan doe ik 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Dus gewoon herschikken deze bedragen, willen we zien hoeveel vergelijkingen maken we

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

66
00:04:52,700 --> 00:04:56,550
Dus als wij brengen deze jongens hier beneden,

67
00:04:56,550 --> 00:05:07,470
dan zijn we nog maar optellen hoeveel vergelijkingen er waren.

68
00:05:07,470 --> 00:05:13,280
Als we deze som en we optellen deze en we de som daarvan,

69
00:05:13,280 --> 00:05:18,130
het is nog steeds hetzelfde probleem. We vatten deze specifieke groepen.

70
00:05:18,130 --> 00:05:22,400
>> Dus nu zijn we optellen van 3 n's. Het is niet alleen 3 n's.

71
00:05:22,400 --> 00:05:27,650
Het is altijd gaat worden n / 2 n's.

72
00:05:27,650 --> 00:05:29,430
Dus hier zijn we toevallig 6 hebben.

73
00:05:29,430 --> 00:05:34,830
Als we 10 dingen, dan kunnen we dit doen groepering voor 5 verschillende paren van de dingen

74
00:05:34,830 --> 00:05:37,180
en eindigen met n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Dus je zal altijd n / 2 n's te krijgen, en dus dit zullen we noteren het uit tot n kwadraat / 2.

76
00:05:45,840 --> 00:05:48,890
En dus zelfs al is het de factor van de helft, die toevallig om binnen te komen

77
00:05:48,890 --> 00:05:54,190
vanwege het feit dat door elke iteratie over de array vergelijken we een minder

78
00:05:54,190 --> 00:05:58,040
dus dat is hoe we de meer dan 2, maar het is nog steeds n in het kwadraat.

79
00:05:58,040 --> 00:06:01,650
We geven niet om de constante factor van een half.

80
00:06:01,650 --> 00:06:07,760
Dus een veel grote O dingen zoals dit is gebaseerd op gewoon een soort van het doen van dit soort wiskunde,

81
00:06:07,760 --> 00:06:12,260
uitvoeren van rekenkundige bewerkingen bedragen en geometrische reeks dingen,

82
00:06:12,260 --> 00:06:17,750
maar de meeste van hen in deze cursus zijn vrij eenvoudig.

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

84
00:06:19,290 --> 00:06:24,430
Waarom is insertion sort in Omega van n? Wat betekent omega bedoel je?

85
00:06:24,430 --> 00:06:27,730
[Twee studenten spreken in een keer - onverstaanbaar] >> Ja.

86
00:06:27,730 --> 00:06:30,630
Omega kunt u denken aan de ondergrens.

87
00:06:30,630 --> 00:06:36,550
>> Dus het maakt niet uit hoe efficiënt uw insertion sort-algoritme is,

88
00:06:36,550 --> 00:06:41,810
ongeacht de lijst die wordt doorgegeven in, het heeft altijd te vergelijken ten minste n dingen

89
00:06:41,810 --> 00:06:44,620
of het moet itereren over n dingen.

90
00:06:44,620 --> 00:06:47,280
Hoe komt dat?

91
00:06:47,280 --> 00:06:51,190
[Student] Want als de lijst is al gesorteerd, vervolgens door de eerste iteratie

92
00:06:51,190 --> 00:06:54,080
kunt u alleen garanderen dat het eerste element is het minst,

93
00:06:54,080 --> 00:06:56,490
en de tweede iteratie kun je alleen garanderen dat de eerste twee zijn

94
00:06:56,490 --> 00:07:00,010
omdat je niet weet dat de rest van de lijst is gesorteerd. >> Ja.

95
00:07:00,010 --> 00:07:08,910
Als u slaagt in een volledig gesorteerde lijst, op zijn minst moet je gaan over alle elementen

96
00:07:08,910 --> 00:07:12,180
zien dat er niets moet worden verplaatst.

97
00:07:12,180 --> 00:07:14,720
Dus die over de lijst en zegt oh, dit al gesorteerd,

98
00:07:14,720 --> 00:07:18,240
is het onmogelijk voor u om te weten dat het gesorteerd totdat u de elk element

99
00:07:18,240 --> 00:07:20,660
zien dat ze in gesorteerde volgorde.

100
00:07:20,660 --> 00:07:25,290
Dus de ondergrens op insertion sort is Omega van n.

101
00:07:25,290 --> 00:07:28,210
Wat is het ergste geval looptijd van merge sort,

102
00:07:28,210 --> 00:07:31,390
ergste geval groot zijn O weer?

103
00:07:31,390 --> 00:07:37,660
Dus in het ergste geval, hoe merge sort lopen?

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

105
00:07:43,690 --> 00:07:49,990
De snelste algemene sorteren algoritmen n log n. Je kunt niet beter doen.

106
00:07:51,930 --> 00:07:55,130
>> Er zijn speciale gevallen, en als we tijd hebben vandaag - maar we zullen dat niet waarschijnlijk -

107
00:07:55,130 --> 00:07:59,330
we konden zien een die het beter doet dan n log n.

108
00:07:59,330 --> 00:08:04,050
Maar in het algemene geval, kun je niet beter doen dan n log n.

109
00:08:04,050 --> 00:08:09,680
En samenvoegen sorteren gebeurt er met degene die je moet weten voor deze cursus, dat is n log n.

110
00:08:09,680 --> 00:08:13,260
En dus zullen we daadwerkelijk uitvoering van dat vandaag de dag.

111
00:08:13,260 --> 00:08:18,070
En tenslotte, in niet meer dan drie zinnen, hoe werkt selectie sorteren werk?

112
00:08:18,070 --> 00:08:20,370
Heeft iemand wilt antwoorden, en Ik tel je zinnen

113
00:08:20,370 --> 00:08:22,390
want als je meer dan 3 -

114
00:08:25,530 --> 00:08:28,330
Heeft iemand herinner selectie sorteren?

115
00:08:31,280 --> 00:08:37,809
Selectie soort is meestal vrij gemakkelijk te onthouden alleen uit de naam.

116
00:08:37,809 --> 00:08:45,350
Je hoeft alleen itereren over de array, vinden wat de grootste waarde is of kleinste -

117
00:08:45,350 --> 00:08:47,290
welke volgorde u sorteren inch

118
00:08:47,290 --> 00:08:50,750
Dus laten we zeggen dat we het sorteren van klein naar groot.

119
00:08:50,750 --> 00:08:55,250
U itereren over de array, op zoek naar wat de minimale element is,

120
00:08:55,250 --> 00:08:59,750
selecteert u deze, en dan gewoon ruilen wat er in de eerste plaats.

121
00:08:59,750 --> 00:09:04,090
En vervolgens op de tweede doorgang over de array, nogmaals naar het minimum element,

122
00:09:04,090 --> 00:09:07,490
te selecteren, en dan ruilen met wat er in de tweede positie.

123
00:09:07,490 --> 00:09:10,650
Dus we zijn gewoon plukken en het kiezen van de minimumwaarden

124
00:09:10,650 --> 00:09:16,050
en ze te plaatsen in de voorkant van de array totdat het valt.

125
00:09:19,210 --> 00:09:21,560
Vragen over zeggen?

126
00:09:21,560 --> 00:09:25,710
>> Deze onvermijdelijk verschijnen in de formulieren die u moet invullen wanneer u het indienen van de PSET.

127
00:09:29,010 --> 00:09:32,360
Dat zijn in principe de antwoorden op deze.

128
00:09:32,360 --> 00:09:34,230
Oke, dus nu codering problemen.

129
00:09:34,230 --> 00:09:40,140
Ik heb al verstuurd via e-mail - Heeft iemand niet dat e-mail? Oke.

130
00:09:40,140 --> 00:09:46,630
Ik heb al verstuurd via e-mail de ruimte die we gaan gebruiken,

131
00:09:46,630 --> 00:09:52,120
en als je klikt op mijn naam - dus ik denk dat ik ga op de bodem

132
00:09:52,120 --> 00:09:57,170
als gevolg van de naar achteren r - maar als u klikt op mijn naam zie je 2 revisies.

133
00:09:57,170 --> 00:10:02,650
Revisie 1 gaat al I worden gekopieerd en geplakt van de code in Spaces

134
00:10:02,650 --> 00:10:06,900
voor het zoeken wat je gaat te hebben om uit te voeren.

135
00:10:06,900 --> 00:10:10,540
En Revisie 2 zal het soort ding dat wij implementeren na dat.

136
00:10:10,540 --> 00:10:15,770
Je kunt dus klik op mijn Herziening 1 en werk vanaf daar.

137
00:10:17,350 --> 00:10:22,060
En nu willen we binaire zoekopdracht uit te voeren.

138
00:10:22,060 --> 00:10:26,470
>> Wil iemand geef een pseudocode op hoog niveau uitleg

139
00:10:26,470 --> 00:10:31,440
van wat we zullen moeten doen voor zoeken? Ja.

140
00:10:31,440 --> 00:10:36,170
[Student] Je neemt gewoon het midden van de array en zien of wat je zoekt

141
00:10:36,170 --> 00:10:38,650
kleiner is dan of meer dan dat.

142
00:10:38,650 --> 00:10:41,080
En als het minder, ga je naar de helft die het minder,

143
00:10:41,080 --> 00:10:44,750
en als het meer is, ga je naar de helft die meer en u dat herhalen totdat u gewoon een ding.

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

145
00:10:46,570 --> 00:10:51,320
Merk op dat onze array numbers al gesorteerd,

146
00:10:51,320 --> 00:10:57,190
en dus dat betekent dat we kunnen profiteren van dat en we konden eerst controleren,

147
00:10:57,190 --> 00:11:00,390
oke, ik ben op zoek naar het nummer 50.

148
00:11:00,390 --> 00:11:03,720
Dus ik kan gaan in het midden.

149
00:11:03,720 --> 00:11:07,380
Midden is moeilijk te definiëren als het een even aantal dingen,

150
00:11:07,380 --> 00:11:10,820
maar laten we gewoon zeggen dat we altijd afkappen tot het midden.

151
00:11:10,820 --> 00:11:14,420
Hier hebben we dus 8 dingen, zodat het midden zou zijn 16.

152
00:11:14,420 --> 00:11:17,330
Ik zoek 50, dus 50 groter is dan 16.

153
00:11:17,330 --> 00:11:21,310
Dus nu kan ik mijn array in principe te behandelen als deze elementen.

154
00:11:21,310 --> 00:11:23,450
Ik kan weggooien alles van 16 over.

155
00:11:23,450 --> 00:11:27,440
Nu is mijn array is alleen deze 4 elementen, en ik herhaal.

156
00:11:27,440 --> 00:11:31,910
Dus dan wil ik naar het midden terug te vinden, is die zal worden 42.

157
00:11:31,910 --> 00:11:34,730
42 is minder dan 50, dus ik kan weggooien deze twee elementen.

158
00:11:34,730 --> 00:11:36,890
Dit is mijn resterende array.

159
00:11:36,890 --> 00:11:38,430
Ik ga naar het midden terug te vinden.

160
00:11:38,430 --> 00:11:42,100
Ik denk dat 50 was een slecht voorbeeld, want ik was altijd weg te gooien dingen naar links,

161
00:11:42,100 --> 00:11:48,280
maar door dezelfde maatregel, als ik ben op zoek naar iets

162
00:11:48,280 --> 00:11:52,100
en het is minder dan het element Ik ben momenteel op zoek naar,

163
00:11:52,100 --> 00:11:55,080
dan ga ik weg te gooien alles naar rechts.

164
00:11:55,080 --> 00:11:58,150
Dus nu moeten we dat implementeren.

165
00:11:58,150 --> 00:12:02,310
Merk op dat we moeten gaan in grootte.

166
00:12:02,310 --> 00:12:06,730
We kunnen ook niet nodig om hard-code grootte.

167
00:12:06,730 --> 00:12:11,640
Dus als we te ontdoen van die # define -

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

169
00:12:21,430 --> 00:12:27,180
Hoe kan ik mooi erachter te komen wat de grootte van de array numbers op dit moment is?

170
00:12:27,180 --> 00:12:30,950
>> Hoeveel elementen zijn in de aantallen array?

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

172
00:12:33,630 --> 00:12:36,600
[Bowden] Dat bestaat niet in C.

173
00:12:36,600 --> 00:12:38,580
Nodig hebben. Lengte.

174
00:12:38,580 --> 00:12:42,010
Arrays niet eigenschappen hebben, dus er is geen eigenschap length van arrays

175
00:12:42,010 --> 00:12:45,650
die net geeft je hoe lang het ook mag zijn.

176
00:12:48,180 --> 00:12:51,620
[Student] Zie hoeveel geheugen het heeft en delen door hoeveel - >> Ja.

177
00:12:51,620 --> 00:12:55,810
Dus hoe kunnen we zien hoeveel geheugen het heeft? >> [Student] sizeof. >> Ja, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof is de exploitant dat gaat om de grootte van de array numbers terug te keren.

179
00:13:01,680 --> 00:13:10,060
En dat gaat worden hoeveel getallen er zijn momenten van de grootte van een geheel getal

180
00:13:10,060 --> 00:13:14,050
want dat is hoeveel geheugen het eigenlijk neemt op.

181
00:13:14,050 --> 00:13:17,630
Dus als ik het aantal dingen in de array wilt,

182
00:13:17,630 --> 00:13:20,560
dan ga ik te willen delen door de grootte van een geheel getal.

183
00:13:22,820 --> 00:13:26,010
Oke. Dus dat laat me hier voorbij in grootte.

184
00:13:26,010 --> 00:13:29,430
Waarom moet ik gaan in grootte op alle?

185
00:13:29,430 --> 00:13:38,570
Waarom kan ik niet gewoon doen hier int size = sizeof (hooiberg) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Waarom werkt dit niet?

187
00:13:41,490 --> 00:13:44,470
[Student] Het is niet een globale variabele.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Hooiberg bestaat en we passeren in aantallen als hooiberg,

189
00:13:51,540 --> 00:13:54,700
en dit is een soort van een voorafschaduwing van wat komen gaat. Ja.

190
00:13:54,700 --> 00:14:00,170
[Student] Hooiberg is alleen de verwijzing naar het, dus het zou terugkeren hoe groot die verwijzing.

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

192
00:14:02,150 --> 00:14:09,000
Ik betwijfel in collegezaal dat u de stapel nog niet gezien echt, toch?

193
00:14:09,000 --> 00:14:11,270
We hebben net gesproken over het.

194
00:14:11,270 --> 00:14:16,090
Zodat de stapel waar al de variabelen zullen worden opgeslagen.

195
00:14:16,090 --> 00:14:19,960
>> Elk geheugen dat is toegewezen voor lokale variabelen gaat in de stapel,

196
00:14:19,960 --> 00:14:24,790
en elke functie krijgt zijn eigen ruimte op de stack, zijn eigen stack frame is hoe het heet.

197
00:14:24,790 --> 00:14:31,590
Dus de belangrijkste heeft zijn stack frame, en de binnenkant van het gaat om deze array numbers bestaan,

198
00:14:31,590 --> 00:14:34,270
en het gaat om de omvang van sizeof (nummers).

199
00:14:34,270 --> 00:14:38,180
Het gaat om de grootte van getallen gedeeld door grootte van de elementen,

200
00:14:38,180 --> 00:14:42,010
maar dat alle levens binnen stack belangrijkste frame van.

201
00:14:42,010 --> 00:14:45,190
Als we een zoekmachine noemen, zoeken krijgt zijn eigen stack frame,

202
00:14:45,190 --> 00:14:48,840
een eigen ruimte om al zijn lokale variabelen op te slaan.

203
00:14:48,840 --> 00:14:56,420
Maar deze argumenten - dus hooiberg is geen kopie van deze hele array.

204
00:14:56,420 --> 00:15:00,990
Wij geven in het gehele array als een kopie in zoeken.

205
00:15:00,990 --> 00:15:04,030
Het gaat gewoon een verwijzing naar die array.

206
00:15:04,030 --> 00:15:11,470
Dus zoek gaat naar deze nummers via deze referentie.

207
00:15:11,470 --> 00:15:17,100
Het is nog steeds de toegang tot de dingen die leven in de stack belangrijkste's frame,

208
00:15:17,100 --> 00:15:22,990
maar in principe, als we in pointers, die moet binnenkort,

209
00:15:22,990 --> 00:15:24,980
dit is wat pointers zijn.

210
00:15:24,980 --> 00:15:29,400
Pointers zijn gewoon verwijzingen naar dingen, en kunt u gebruik maken pointers om dingen te openen

211
00:15:29,400 --> 00:15:32,030
die in andere dingen 'stapelen frames.

212
00:15:32,030 --> 00:15:37,660
Dus ook al nummers zich lokaal op de belangrijkste, kunnen we nog steeds toegang tot het via deze pointer.

213
00:15:37,660 --> 00:15:41,770
Maar omdat het is gewoon een pointer en het is gewoon een referentie,

214
00:15:41,770 --> 00:15:45,040
sizeof (hooiberg) geeft alleen de grootte van de verwijzing zelf.

215
00:15:45,040 --> 00:15:47,950
Het maakt niet terug van de grootte van het ding het is te wijzen op.

216
00:15:47,950 --> 00:15:51,110
Het maakt niet terug de werkelijke grootte van de nummers.

217
00:15:51,110 --> 00:15:55,660
En dus dit is niet van plan om te werken als we willen dat het.

218
00:15:55,660 --> 00:15:57,320
>> Vragen over zeggen?

219
00:15:57,320 --> 00:16:03,250
Pointers zal worden ingegaan in significant meer bloederige details in de komende weken.

220
00:16:06,750 --> 00:16:13,740
En dit is de reden waarom veel van de dingen die je ziet, de meeste zoeken dingen of soort dingen,

221
00:16:13,740 --> 00:16:16,990
ze bijna allemaal gaat nodig hebben om de werkelijke grootte van de array te nemen,

222
00:16:16,990 --> 00:16:20,440
omdat in C, we hebben geen idee wat de grootte van de array is.

223
00:16:20,440 --> 00:16:22,720
U moet handmatig doorgeven inch

224
00:16:22,720 --> 00:16:27,190
En je kunt niet handmatig geschieden in het hele array omdat je op doorreis in de referentie-

225
00:16:27,190 --> 00:16:30,390
en het kan de grootte niet te krijgen van de referentie.

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

227
00:16:32,300 --> 00:16:38,160
Dus nu willen we voeren wat werd uitgelegd.

228
00:16:38,160 --> 00:16:41,530
Je kunt werken op het voor een minuut,

229
00:16:41,530 --> 00:16:45,250
en je hoeft geen zorgen te maken over het krijgen van alles perfect 100% werken.

230
00:16:45,250 --> 00:16:51,410
Schrijf gewoon de half pseudocode voor hoe je denkt dat het zou moeten werken.

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

232
00:16:53,630 --> 00:16:56,350
Geen behoefte om volledig gedaan met deze nog niet.

233
00:16:56,350 --> 00:17:02,380
Maar heeft iemand zich gerust voelen met wat ze hebben tot nu toe,

234
00:17:02,380 --> 00:17:05,599
als iets dat we kunnen werken met elkaar?

235
00:17:05,599 --> 00:17:09,690
Is er iemand die als vrijwilliger willen werken? Of ik zal willekeurig kiezen.

236
00:17:12,680 --> 00:17:18,599
Het hoeft niet gelijk te hebben door een maatregel, maar iets wat we kunnen veranderen in een werkende staat.

237
00:17:18,599 --> 00:17:20,720
[Student] Tuurlijk. >> Oke.

238
00:17:20,720 --> 00:17:27,220
Zo kunt u de herziening besparen door te klikken op het kleine pictogram Opslaan.

239
00:17:27,220 --> 00:17:29,950
Je hebt Ramya, toch? >> [Student] Ja. >> [Bowden] Oke.

240
00:17:29,950 --> 00:17:35,140
Dus nu kan ik bekijk uw revisie en iedereen kan trek de herziening.

241
00:17:35,140 --> 00:17:38,600
En hier hebben we - Oke.

242
00:17:38,600 --> 00:17:43,160
Dus Ramya ging met de recursieve oplossing, dat is zeker een geldige oplossing.

243
00:17:43,160 --> 00:17:44,970
Er zijn twee manieren waarop u kunt dit probleem te doen.

244
00:17:44,970 --> 00:17:48,060
U kunt dit doen iteratief of recursief.

245
00:17:48,060 --> 00:17:53,860
De meeste problemen die je tegenkomt die recursief kan worden gedaan kan ook iteratief worden gedaan.

246
00:17:53,860 --> 00:17:58,510
Dus hier hebben we het gedaan recursief.

247
00:17:58,510 --> 00:18:03,730
>> Heeft iemand wilt definiëren wat het betekent om een ​​functie recursief?

248
00:18:07,210 --> 00:18:08,920
[Student] Wanneer u een functie hebben noemen zich

249
00:18:08,920 --> 00:18:13,470
en dan noemen zichzelf totdat het uit met echte en ware. >> Ja.

250
00:18:13,470 --> 00:18:17,680
Een recursieve functie is gewoon een functie die zichzelf aanroept.

251
00:18:17,680 --> 00:18:24,140
Er zijn drie grote dingen die een recursieve functie moet hebben.

252
00:18:24,140 --> 00:18:27,310
De eerste is natuurlijk, het noemt zichzelf.

253
00:18:27,310 --> 00:18:29,650
De tweede is het nulalternatief.

254
00:18:29,650 --> 00:18:33,390
Dus op een gegeven moment de functie moet stoppen die zichzelf,

255
00:18:33,390 --> 00:18:35,610
en dat is wat het nulalternatief is voor.

256
00:18:35,610 --> 00:18:43,860
Dus hier zijn we weten dat we moeten stoppen, moeten we opgeven in onze zoektocht

257
00:18:43,860 --> 00:18:48,150
als de start-end is gelijk aan - en we zullen zien wat dat betekent.

258
00:18:48,150 --> 00:18:52,130
Maar uiteindelijk, het laatste ding dat belangrijk is voor recursieve functies:

259
00:18:52,130 --> 00:18:59,250
de functies moeten een of andere manier benaderen het nulalternatief.

260
00:18:59,250 --> 00:19:04,140
Net als je niet echt iets updaten wanneer u de tweede recursieve aanroep,

261
00:19:04,140 --> 00:19:07,880
als je letterlijk het aanroepen van de functie opnieuw met dezelfde argumenten

262
00:19:07,880 --> 00:19:10,130
en er geen globale variabelen zijn veranderd of wat dan ook,

263
00:19:10,130 --> 00:19:14,430
zul je nooit bereiken van de base case, in welk geval dat is slecht.

264
00:19:14,430 --> 00:19:17,950
Het zal een oneindige recursie en een stack overflow te zijn.

265
00:19:17,950 --> 00:19:24,330
Maar hier zien we dat de update is gebeurt omdat we een update start + end / 2,

266
00:19:24,330 --> 00:19:28,180
we updaten het einde argument hier, we het begin argument hier bijwerken.

267
00:19:28,180 --> 00:19:32,860
Dus in alle recursieve oproepen we updaten iets. Oke.

268
00:19:32,860 --> 00:19:38,110
Wilt u ons lopen door uw oplossing? >> Tuurlijk.

269
00:19:38,110 --> 00:19:44,270
Ik gebruik SearchHelp zodat elke keer als ik deze functie oproep

270
00:19:44,270 --> 00:19:47,910
Ik heb het begin van waar ik ben op zoek naar in de array en het einde

271
00:19:47,910 --> 00:19:49,380
van waar ik ben op zoek de array.

272
00:19:49,380 --> 00:19:55,330
>> Bij elke stap waar het zegt dat het is het midden element, dat begin + einde / 2,

273
00:19:55,330 --> 00:19:58,850
is dat gelijk aan wat we zoeken?

274
00:19:58,850 --> 00:20:04,650
En als het is, dan hebben we het gevonden, en ik denk dat dat wordt doorgegeven van de niveaus van recursie.

275
00:20:04,650 --> 00:20:12,540
En als dat niet waar is, dan kunnen we kijken of dat middelste waarde van de array is te groot,

276
00:20:12,540 --> 00:20:19,320
waarbij we kijken naar de linkerkant van de matrix door te gaan van start tot het midden index.

277
00:20:19,320 --> 00:20:22,710
En anders doen we het einde helft.

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

279
00:20:24,740 --> 00:20:27,730
Klinkt goed.

280
00:20:27,730 --> 00:20:36,640
Oke, dus een paar dingen, en eigenlijk is dit een zeer hoog niveau wat

281
00:20:36,640 --> 00:20:41,270
dat zul je nooit moet weten voor deze cursus, maar het is waar.

282
00:20:41,270 --> 00:20:46,080
Recursieve functies, hoort u altijd dat ze een slechte deal

283
00:20:46,080 --> 00:20:51,160
want als je recursief noemt jezelf te vaak, krijg je stack overflow

284
00:20:51,160 --> 00:20:54,990
omdat, zoals ik al eerder zei, elke functie krijgt zijn eigen stack frame.

285
00:20:54,990 --> 00:20:59,500
Dus elke oproep van de recursieve functie krijgt zijn eigen stack frame.

286
00:20:59,500 --> 00:21:04,140
Dus als je 1000 recursieve oproepen, krijg je 1.000 stack frames,

287
00:21:04,140 --> 00:21:08,390
en snel je leiden tot het hebben te veel stack frames en dingen die er gewoon breken.

288
00:21:08,390 --> 00:21:13,480
Dus dat is waarom recursieve functies zijn over het algemeen slecht.

289
00:21:13,480 --> 00:21:19,370
Maar er is een mooi deel van recursieve functies genoemd staart-recursieve functies,

290
00:21:19,370 --> 00:21:26,120
en dit gebeurt te zijn een voorbeeld van een waar als de compiler merkt dit

291
00:21:26,120 --> 00:21:29,920
en het zou moeten, denk ik - in Clang als je langs het de-O2 vlag

292
00:21:29,920 --> 00:21:33,250
dan zal het opvallen dat is staart recursieve en maken dingen goed.

293
00:21:33,250 --> 00:21:40,050
>> Het zal opnieuw dezelfde stack frame over en weer voor elke recursieve aanroep.

294
00:21:40,050 --> 00:21:47,010
En dus omdat je met dezelfde stack frame, hoeft u zich geen zorgen te maken over

295
00:21:47,010 --> 00:21:51,690
ever stapel overlopen, en tegelijkertijd, zoals je gezegd

296
00:21:51,690 --> 00:21:56,380
waar als je eenmaal true retourneren, dan heeft om terug te keren tot al deze stack frames

297
00:21:56,380 --> 00:22:01,740
en de 10e oproep SearchHelp moet terugkeren naar de 9 moet terugkeren naar de 8e.

298
00:22:01,740 --> 00:22:05,360
Dus dat hoeft niet te gebeuren wanneer functies zijn staart recursief.

299
00:22:05,360 --> 00:22:13,740
En dus wat maakt deze functie staart recursieve is bericht dat voor een bepaald gesprek naar searchHelp

300
00:22:13,740 --> 00:22:18,470
de recursieve aanroep die het maakt is wat het is terug te keren.

301
00:22:18,470 --> 00:22:25,290
Dus in de eerste oproep tot SearchHelp, we ofwel onmiddellijk return false,

302
00:22:25,290 --> 00:22:29,590
onmiddellijk terug true of we een recursieve aanroep van SearchHelp

303
00:22:29,590 --> 00:22:33,810
waar wat we terugkeren is wat dat gesprek is terug te keren.

304
00:22:33,810 --> 00:22:51,560
En we konden dit niet doen als we dat iets als int x = SearchHelp, return x * 2,

305
00:22:51,560 --> 00:22:55,440
slechts enkele willekeurige verandering.

306
00:22:55,440 --> 00:23:01,470
>> Dus nu deze recursieve aanroep, dit int x = SearchHelp recursieve aanroep,

307
00:23:01,470 --> 00:23:05,740
is niet langer staart recursieve omdat het eigenlijk hoeft om terug te keren

308
00:23:05,740 --> 00:23:10,400
terug naar een vorige stack frame zodat dat eerdere aanroep van de functie

309
00:23:10,400 --> 00:23:13,040
kan dan iets doen met de return waarde.

310
00:23:13,040 --> 00:23:22,190
Dit is dus niet de staart recursieve, maar wat we hadden voordat is mooi staart recursief. Ja.

311
00:23:22,190 --> 00:23:27,000
[Student] Moet het tweede honk geval eerst worden gecontroleerd

312
00:23:27,000 --> 00:23:30,640
want er kan een situatie zijn waar wanneer u doorgeven het argument

313
00:23:30,640 --> 00:23:35,770
je hebt start = einde, maar ze zijn de naald waarde.

314
00:23:35,770 --> 00:23:47,310
De vraag werd kunnen we niet lopen in het geval dat einde is de naald waarde

315
00:23:47,310 --> 00:23:52,000
of start = einde, op de juiste wijze, start = einde

316
00:23:52,000 --> 00:23:59,480
en je hebt niet echt gecontroleerd of bepaalde waarde nog niet,

317
00:23:59,480 --> 00:24:03,910
dan beginnen + einde / 2 is gewoon op dezelfde waarde zijn.

318
00:24:03,910 --> 00:24:07,890
Maar we hebben al weer vals, en we nooit echt gecontroleerd de waarde.

319
00:24:07,890 --> 00:24:14,240
Dus op zijn minst in de eerste oproep, als de grootte gelijk is aan 0, dan willen we return false.

320
00:24:14,240 --> 00:24:17,710
Maar als grootte is 1, dan start is niet van plan om gelijk einde,

321
00:24:17,710 --> 00:24:19,820
en we zullen in ieder geval controleer dan de een element.

322
00:24:19,820 --> 00:24:26,750
Maar ik denk dat je gelijk hebt in dat we kunnen eindigen in een geval waar te beginnen + einde / 2,

323
00:24:26,750 --> 00:24:31,190
start eindigt als dezelfde als de beginpositie + einde / 2,

324
00:24:31,190 --> 00:24:35,350
maar we hebben nooit echt gecontroleerd dat element.

325
00:24:35,350 --> 00:24:44,740
>> Dus als we eerst het middelste element van de waarde die we zoeken,

326
00:24:44,740 --> 00:24:47,110
dan kunnen we onmiddellijk terug waar.

327
00:24:47,110 --> 00:24:50,740
Anders als ze gelijk zijn, dan is er geen enkel punt in voortdurende

328
00:24:50,740 --> 00:24:58,440
omdat we gaan gewoon om te updaten naar een zaak waar we zijn op een single-element array.

329
00:24:58,440 --> 00:25:01,110
Als dat enkel element is niet degene die we zoeken,

330
00:25:01,110 --> 00:25:03,530
dan is alles verkeerd. Ja.

331
00:25:03,530 --> 00:25:08,900
[Student] Het is dat aangezien maat is eigenlijk groter dan het aantal elementen in de array,

332
00:25:08,900 --> 00:25:13,070
Er is al een offset - >> Zo zal size -

333
00:25:13,070 --> 00:25:19,380
[Student] Zeg als de array was maat 0, dan is de SearchHelp ook daadwerkelijk controleren hooiberg van 0

334
00:25:19,380 --> 00:25:21,490
op het eerste gesprek.

335
00:25:21,490 --> 00:25:25,300
De array heeft grootte 0, dus de 0 is - >> Ja.

336
00:25:25,300 --> 00:25:30,750
Er is nog een ding dat - het zou goed zijn. Laten we denken.

337
00:25:30,750 --> 00:25:40,120
Dus als de array heeft 10 elementen en de middelste we gaan om te controleren is index 5,

338
00:25:40,120 --> 00:25:45,700
dus we zijn het controleren van 5, en laten we zeggen dat de waarde lager is.

339
00:25:45,700 --> 00:25:50,720
Dus we gooien alles uit de buurt van 5 verder.

340
00:25:50,720 --> 00:25:54,030
Dus begin + einde / 2 gaat onze nieuwe einde zijn,

341
00:25:54,030 --> 00:25:57,450
dus ja, het is altijd gaan om te verblijven na het einde van de array.

342
00:25:57,450 --> 00:26:03,570
Als het een geval als het even of oneven, dan zouden we controleren, zegt, 4,

343
00:26:03,570 --> 00:26:05,770
maar we zijn nog steeds weg te gooien -

344
00:26:05,770 --> 00:26:13,500
Dus ja, is uiteindelijk altijd zal zijn dan het werkelijke einde van de array.

345
00:26:13,500 --> 00:26:18,350
Dus de elementen richten we ons op, wordt uiteindelijk altijd naar de een na dat.

346
00:26:18,350 --> 00:26:24,270
En dus als start doet ooit gelijk einde, we zijn in een array van grootte 0.

347
00:26:24,270 --> 00:26:35,600
>> Het andere wat ik zat te denken is dat we beginnen met het bijwerken te starten + einde / 2,

348
00:26:35,600 --> 00:26:44,020
dus dit is het geval dat ik heb problemen met, in voorkomend start + end / 2

349
00:26:44,020 --> 00:26:46,820
is het element dat we het controleren.

350
00:26:46,820 --> 00:26:58,150
Laten we zeggen dat we hadden deze 10-element array. Het zal wel.

351
00:26:58,150 --> 00:27:03,250
Dus begin + einde / 2 gaat iets als dit een zijn,

352
00:27:03,250 --> 00:27:07,060
en als dat niet de waarde, zeggen dat we willen werken.

353
00:27:07,060 --> 00:27:10,060
De waarde is groter, dus we kijken naar deze helft van de array.

354
00:27:10,060 --> 00:27:15,910
Dus hoe we beginnen met updaten, we updaten start nu dit element.

355
00:27:15,910 --> 00:27:23,790
Maar dit kan nog steeds werken, of op zijn minst, wat je kunt doen begin + einde / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Student] Je hoeft niet te + einde te beginnen [onverstaanbaar] >> Ja.

357
00:27:27,850 --> 00:27:33,240
We hebben al gekeken dit element en weet dat het niet degene die we zoeken.

358
00:27:33,240 --> 00:27:36,800
Dus we hoeven niet te beginnen bij te werken om dit element te zijn.

359
00:27:36,800 --> 00:27:39,560
We kunnen gewoon overslaan en bij te werken beginnen om dit element te zijn.

360
00:27:39,560 --> 00:27:46,060
En is er ooit een geval, laten we zeggen, dat dit zou eindigen,

361
00:27:46,060 --> 00:27:53,140
dus dan beginnen zou dit, start + end / 2 zou zijn dit,

362
00:27:53,140 --> 00:28:00,580
begin + einde - Ja, ik denk dat het kan eindigen in oneindige recursie.

363
00:28:00,580 --> 00:28:12,690
Laten we zeggen dat het is gewoon een array van grootte 2 of een array van grootte 1. Ik denk dat dit zal werken.

364
00:28:12,690 --> 00:28:19,490
Dus op dit moment, begin is dat element en het einde is 1 daarbuiten.

365
00:28:19,490 --> 00:28:24,110
Dus het element dat we gaan om te controleren is deze,

366
00:28:24,110 --> 00:28:29,400
en toen we begin te werken, werken we beginnen te zijn 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
die gaat ons uiteindelijk terug met start wordt dit element.

368
00:28:33,160 --> 00:28:36,210
>> Dus we controleren hetzelfde element over en weer.

369
00:28:36,210 --> 00:28:43,310
Dus dit is het geval wanneer elke recursieve aanroep moet daadwerkelijk bij te werken iets.

370
00:28:43,310 --> 00:28:48,370
Dus moeten we begin + einde / 2 + 1, of anders te doen is er een geval

371
00:28:48,370 --> 00:28:50,710
waar we eigenlijk niet updaten start.

372
00:28:50,710 --> 00:28:53,820
Iedereen ziet dat?

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

374
00:28:56,310 --> 00:29:03,860
Heeft iemand vragen over deze oplossing of een ander commentaar?

375
00:29:05,220 --> 00:29:10,280
Oke. Heeft iemand een hebben iteratieve oplossing die we allemaal kunnen kijken?

376
00:29:17,400 --> 00:29:20,940
Hebben we allemaal recursief doen?

377
00:29:20,940 --> 00:29:25,950
Of ook ik denk dat als je geopend van haar, dan kun je misschien overschreven hebt je vorige.

378
00:29:25,950 --> 00:29:28,810
Is het automatisch opslaan? Ik ben niet positief.

379
00:29:35,090 --> 00:29:39,130
Heeft iemand hebben iteratieve?

380
00:29:39,130 --> 00:29:42,430
We kunnen samen wandelen door het zo niet.

381
00:29:46,080 --> 00:29:48,100
Het idee zal hetzelfde.

382
00:30:00,260 --> 00:30:02,830
Iteratieve oplossing.

383
00:30:02,830 --> 00:30:07,140
We gaan willen in principe doen hetzelfde idee

384
00:30:07,140 --> 00:30:16,530
waar we willen muziekstuk van de nieuwe einde van de array en de nieuwe start van de array te houden

385
00:30:16,530 --> 00:30:18,510
en dat doen over en voorbij.

386
00:30:18,510 --> 00:30:22,430
En als wat we het bijhouden van als het begin en het einde ooit kruisen,

387
00:30:22,430 --> 00:30:29,020
dan hebben we het niet vinden en we kunnen terugkeren vals.

388
00:30:29,020 --> 00:30:37,540
Dus hoe doe ik dat? Iedereen heeft suggesties of code voor mij op te trekken?

389
00:30:42,190 --> 00:30:47,450
[Student] Doe een while-lus. >> Ja.

390
00:30:47,450 --> 00:30:49,450
Je gaat te willen om een ​​lus te doen.

391
00:30:49,450 --> 00:30:51,830
>> Had je code die ik kon trekken, of wat was je van plan om te suggereren?

392
00:30:51,830 --> 00:30:56,340
[Student] Ik denk het wel. >> Oke. Dit maakt het makkelijker. Wat was je naam?

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

394
00:31:00,140 --> 00:31:04,190
Herziening 1. Oke.

395
00:31:04,190 --> 00:31:13,200
Low is wat wij genoemd starten voor.

396
00:31:13,200 --> 00:31:17,080
Up is niet helemaal wat we noemden einde voor.

397
00:31:17,080 --> 00:31:22,750
Eigenlijk einde nu in de array. Het is een element dat we moeten overwegen.

398
00:31:22,750 --> 00:31:26,890
Zo laag is 0, tot de grootte van de matrix - 1,

399
00:31:26,890 --> 00:31:34,780
en nu zijn we een lus, en we controleren -

400
00:31:34,780 --> 00:31:37,340
Ik denk dat je kunt er doorheen.

401
00:31:37,340 --> 00:31:41,420
Wat was je denken door dit? Loop met ons op via uw code.

402
00:31:41,420 --> 00:31:49,940
[Student] Tuurlijk. Kijk naar de hooiberg waarde in het midden en vergelijk het met de naald.

403
00:31:49,940 --> 00:31:58,520
Dus als het groter is dan de naald, dan wil je - oh, eigenlijk, dat moet naar achteren zijn.

404
00:31:58,520 --> 00:32:05,180
Je gaat te willen om weg te gooien de rechter helft, en zo ja, dat moet het zo zijn.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Dus dit moet minder zijn? Is dat wat je zei? >> [Student] Ja.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Oke. Minder.

407
00:32:10,390 --> 00:32:15,700
Dus als wat we zoeken naar kleiner is dan wat we willen,

408
00:32:15,700 --> 00:32:19,410
dan ja, we willen om weg te gooien de linker helft,

409
00:32:19,410 --> 00:32:22,210
wat betekent dat we zijn alles wat we overwegen het bijwerken

410
00:32:22,210 --> 00:32:26,610
door het bewegen van laag naar rechts van de array.

411
00:32:26,610 --> 00:32:30,130
Dit ziet er goed uit.

412
00:32:30,130 --> 00:32:34,550
Ik denk dat het hetzelfde probleem dat we al op de vorige,

413
00:32:34,550 --> 00:32:49,760
waar als laag is 0 en up is 1, dan lage + omhoog / 2 gaat opzetten om hetzelfde weer.

414
00:32:49,760 --> 00:32:53,860
>> En zelfs als dat niet het geval is nog efficiënter althans

415
00:32:53,860 --> 00:32:57,630
om gewoon weg te gooien het element dat we keek alleen maar naar waar we weten dat het verkeerd is.

416
00:32:57,630 --> 00:33:03,240
Dus lage + omhoog / 2 + 1 - >> [student] Dat moet de andere kant op te zijn.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Of dit moet - 1 en de andere moet + 1.

418
00:33:05,900 --> 00:33:09,580
[Student] En er moet een dubbel is-teken. >> [Bowden] Ja.

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

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

421
00:33:15,910 --> 00:33:21,280
En tot slot, nu hebben we dit + 1 - 1 ding,

422
00:33:21,280 --> 00:33:31,520
is het - het is misschien niet - is het ooit mogelijk voor lage om te eindigen met een waarde groter dan op?

423
00:33:35,710 --> 00:33:40,320
Ik denk dat de enige manier waarop dat kan gebeuren - Is het mogelijk? >> [Student] Ik weet het niet.

424
00:33:40,320 --> 00:33:45,220
Maar als het wordt afgekapt en dan krijgt minus die 1 en vervolgens - >> Ja.

425
00:33:45,220 --> 00:33:47,480
[Student] Het zou eventueel krijgen messed up.

426
00:33:49,700 --> 00:33:53,940
Ik denk dat het zou goed moeten zijn maar omdat

427
00:33:53,940 --> 00:33:58,800
voor het naar uiteindelijk lager zouden ze gelijk zijn, denk ik.

428
00:33:58,800 --> 00:34:03,070
Maar als ze gelijk zijn, dan zouden we niet hebben gedaan de while-lus om te beginnen met

429
00:34:03,070 --> 00:34:06,670
en we zouden zijn teruggekeerd van de waarde. Dus ik denk dat we nu goed.

430
00:34:06,670 --> 00:34:11,530
Merk op dat hoewel dit probleem niet langer recursief,

431
00:34:11,530 --> 00:34:17,400
het zelfde soort ideeën toe te passen, waar we kunnen zien hoe dit zo gemakkelijk leent zich

432
00:34:17,400 --> 00:34:23,659
een recursieve oplossing door het feit dat we nog maar net de indexen updaten over en weer,

433
00:34:23,659 --> 00:34:29,960
we maken het probleem kleiner en kleiner, we focussen op een deel van de array.

434
00:34:29,960 --> 00:34:40,860
[Student] Als laag is 0 en up 1 is, zouden zij beide 0 + 1/2, die naar 0,

435
00:34:40,860 --> 00:34:44,429
en men zou + 1, zou men - 1.

436
00:34:47,000 --> 00:34:50,870
[Student] Waar gaan we controleren gelijkheid?

437
00:34:50,870 --> 00:34:55,100
Net als de middelste eigenlijk naald?

438
00:34:55,100 --> 00:34:58,590
We zijn op dit moment niet om dat te doen? Oh!

439
00:35:00,610 --> 00:35:02,460
Als het is -

440
00:35:05,340 --> 00:35:13,740
Ja. We kunnen niet gewoon de test hier beneden, want laten we zeggen dat de eerste midden -

441
00:35:13,740 --> 00:35:16,430
[Student] Het is eigenlijk net als niet weggooien het gebonden.

442
00:35:16,430 --> 00:35:20,220
Dus als je weggooien gebonden, je moet het eerst controleren of wat dan ook.

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

444
00:35:23,350 --> 00:35:29,650
Dus nu hebben we weggegooid degene die we op dit moment gekeken naar,

445
00:35:29,650 --> 00:35:33,260
wat betekent dat we nu moeten ook

446
00:35:33,260 --> 00:35:44,810
if (hooiberg [(laag + up) / 2] == naald), dan kunnen we return true.

447
00:35:44,810 --> 00:35:52,070
En of ik anders of gewoon als, het betekent letterlijk hetzelfde

448
00:35:52,070 --> 00:35:57,110
omdat dit zou zijn teruggekeerd waar.

449
00:35:57,110 --> 00:36:01,450
Dus ik zal anders gezet of, maar het maakt niet uit.

450
00:36:01,450 --> 00:36:10,440
>> Dus anders als dit, anders deze, en dit is een veel voorkomende wat ik doe

451
00:36:10,440 --> 00:36:14,340
waar zelfs indien dit het geval is waar alles is hier goed,

452
00:36:14,340 --> 00:36:22,780
zoals lage kan nooit groter zijn dan op, het is niet de moeite waard redenering over de vraag of dat waar is.

453
00:36:22,780 --> 00:36:28,010
Dus je kan net zo goed zeggen, terwijl een lage kleiner is dan of gelijk is aan

454
00:36:28,010 --> 00:36:30,720
of terwijl laag kleiner is dan

455
00:36:30,720 --> 00:36:35,300
dus als ze ooit gelijk of lage gebeurt om te laten liggen,

456
00:36:35,300 --> 00:36:40,130
dan kunnen we doorbreken van deze lus.

457
00:36:41,410 --> 00:36:44,630
Vragen, zorgen, opmerkingen?

458
00:36:47,080 --> 00:36:49,270
Oke. Dit ziet er goed uit.

459
00:36:49,270 --> 00:36:52,230
Nu willen we sorteren doen.

460
00:36:52,230 --> 00:37:04,030
Als we naar mijn tweede herziening, zien we deze zelfde nummers,

461
00:37:04,030 --> 00:37:07,550
maar nu zijn ze niet meer in gesorteerde volgorde.

462
00:37:07,550 --> 00:37:12,840
En we willen sorteren implementeren met behulp van een algoritme in O n log n.

463
00:37:12,840 --> 00:37:17,240
Dus welke algoritme denk je dat we hier moeten voeren? >> [Student] Merge soort.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Ja. Samenvoegen soort is O (n log n), dus dat is wat we gaan doen.

465
00:37:23,810 --> 00:37:26,680
En het probleem zal zijn redelijk vergelijkbaar,

466
00:37:26,680 --> 00:37:31,920
wanneer leent zich gemakkelijk een recursieve oplossing.

467
00:37:31,920 --> 00:37:35,580
We kunnen ook komen met een iteratieve oplossing als we willen,

468
00:37:35,580 --> 00:37:42,540
maar recursie zal gemakkelijker zijn hier en we moeten doen recursie.

469
00:37:45,120 --> 00:37:49,530
Ik denk dat we eerst lopen door merge sort,

470
00:37:49,530 --> 00:37:54,280
hoewel er is een mooie video op merge sort reeds. [Gelach]

471
00:37:54,280 --> 00:37:59,780
Dus samenvoegen soort zijn er - ik ben het verspillen van zoveel van deze paper.

472
00:37:59,780 --> 00:38:02,080
Oh, er is maar een over.

473
00:38:02,080 --> 00:38:03,630
Dus samen te voegen.

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

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

476
00:38:29,910 --> 00:38:33,460
Merge neemt twee afzonderlijke arrays.

477
00:38:33,460 --> 00:38:36,780
Individueel deze twee arrays beide gesorteerd.

478
00:38:36,780 --> 00:38:40,970
Dus array, 1, 3, 5, gesorteerd. Deze array, 0, 2, 4, gesorteerd.

479
00:38:40,970 --> 00:38:46,710
Nu, wat samenvoegen moet doen is deze combineren in een enkele array die zelf gesorteerd.

480
00:38:46,710 --> 00:38:57,130
Dus we willen een array van maat 6 dat gaat deze elementen hebben de binnenkant van het

481
00:38:57,130 --> 00:38:59,390
in gesorteerde volgorde.

482
00:38:59,390 --> 00:39:03,390
>> En dus kunnen we profiteren van het feit dat deze twee arrays zijn gesorteerd

483
00:39:03,390 --> 00:39:06,800
om dit te doen in de lineaire tijd,

484
00:39:06,800 --> 00:39:13,510
lineaire tijd betekenis als deze array is een maat XS en dit is maat y,

485
00:39:13,510 --> 00:39:20,970
dan is de totale algoritme moet O (x + y). Oke.

486
00:39:20,970 --> 00:39:23,150
Dus suggesties.

487
00:39:23,150 --> 00:39:26,030
[Student] Kunnen we beginnen van links?

488
00:39:26,030 --> 00:39:30,150
Dus je zet de 0 naar beneden en vervolgens de 1 en vervolgens hier ben je op de 2.

489
00:39:30,150 --> 00:39:33,320
Dus het is een soort heb je een tabblad dat beweegt naar rechts. >> [Bowden] Ja.

490
00:39:33,320 --> 00:39:41,070
Voor beide arrays als we gewoon focussen op de meest linkse element.

491
00:39:41,070 --> 00:39:43,530
Omdat beide arrays worden gesorteerd, weten we dat deze 2 elementen

492
00:39:43,530 --> 00:39:46,920
de kleinste elementen in beide array.

493
00:39:46,920 --> 00:39:53,500
Dus dat betekent dat 1 van deze 2 elementen moeten het kleinste element in onze samengevoegde array.

494
00:39:53,500 --> 00:39:58,190
Het is gewoon zo gebeurt het dat de kleinste is de een aan de rechter deze keer.

495
00:39:58,190 --> 00:40:02,580
Dus we nemen 0, plaatst u deze op de linker omdat 0 kleiner is dan 1,

496
00:40:02,580 --> 00:40:08,210
dus neem 0, plaatst u deze in de eerste plaats, en dan gaan we updaten

497
00:40:08,210 --> 00:40:12,070
tot nu concentreren op het eerste element.

498
00:40:12,070 --> 00:40:14,570
En nu zijn we herhalen.

499
00:40:14,570 --> 00:40:20,670
Dus nu vergelijken we 2 en 1. 1 kleiner is, dus we zullen plaatsen 1.

500
00:40:20,670 --> 00:40:25,300
We updaten deze pointer om te wijzen op deze kerel.

501
00:40:25,300 --> 00:40:33,160
Nu gaan we het weer doen, dus 2. Dit zal werken, vergelijk deze 2, 3.

502
00:40:33,160 --> 00:40:37,770
Deze updates, vervolgens 4 en 5.

503
00:40:37,770 --> 00:40:42,110
Dus dat is merge.

504
00:40:42,110 --> 00:40:49,010
>> Het moet vrij duidelijk dat het lineaire tijd geleden dat we maar een keer naar de overkant van elk element.

505
00:40:49,010 --> 00:40:55,980
En dat is de grootste stap voor de uitvoering merge sort dit doet.

506
00:40:55,980 --> 00:40:59,330
En het is niet zo moeilijk.

507
00:40:59,330 --> 00:41:15,020
Een paar dingen zorgen te maken over is laten we zeggen dat we 1, 2, 3, 4, 5, 6 samenvoegen.

508
00:41:15,020 --> 00:41:30,930
In dit geval eindigen in het scenario waarin deze zal kleiner,

509
00:41:30,930 --> 00:41:36,160
dan kunnen we deze pointer updaten, deze gaat worden kleiner, updaten,

510
00:41:36,160 --> 00:41:41,280
Deze is kleiner, en nu heb je te herkennen

511
00:41:41,280 --> 00:41:44,220
als je daadwerkelijk hebt opraken van de elementen te vergelijken met.

512
00:41:44,220 --> 00:41:49,400
Omdat we al gebruik gemaakt van deze hele array,

513
00:41:49,400 --> 00:41:55,190
alles in deze reeks wordt nu gewoon ingevoegd in hier.

514
00:41:55,190 --> 00:42:02,040
Dus als we ooit in het punt waar een van onze arrays volledig is al samengevoegd,

515
00:42:02,040 --> 00:42:06,510
dan kunnen we gewoon alle elementen van de andere array en steek ze in het einde van de array.

516
00:42:06,510 --> 00:42:13,630
Dus we kunnen gewoon plaats 4, 5, 6. Oke.

517
00:42:13,630 --> 00:42:18,070
Dat is een ding om op te letten.

518
00:42:22,080 --> 00:42:26,120
Uitvoering van dat moet stap 1 zijn.

519
00:42:26,120 --> 00:42:32,600
Samenvoegen vervolgens sorteren op basis van dat, het is 2 stappen, 2 domme stappen.

520
00:42:38,800 --> 00:42:42,090
Laten we geven deze array.

521
00:42:57,920 --> 00:43:05,680
Dus samenvoegen sorteren, stap 1 is om de array recursief te breken in twee helften.

522
00:43:05,680 --> 00:43:09,350
Dus splitsen deze array in twee helften.

523
00:43:09,350 --> 00:43:22,920
We hebben nu 4, 15, 16, 50 en 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
En nu doen we het weer en we splitsen deze in twee helften.

525
00:43:25,800 --> 00:43:27,530
Ik doe het gewoon aan deze kant.

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

527
00:43:34,790 --> 00:43:37,440
Wij zouden hetzelfde doen hier.

528
00:43:37,440 --> 00:43:40,340
En nu hebben we splitsen in twee helften weer.

529
00:43:40,340 --> 00:43:51,080
En we hebben 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Dus dat is ons basisscenario.

531
00:43:53,170 --> 00:44:00,540
Zodra de arrays zijn van maat 1, dan stoppen we met de splitsing in twee helften.

532
00:44:00,540 --> 00:44:03,190
>> Nu wat doen we hiermee?

533
00:44:03,190 --> 00:44:15,730
We uiteindelijk zal dit ook worden onderverdeeld in 8, 23, 42 en 108.

534
00:44:15,730 --> 00:44:24,000
Dus nu dat we op dit punt, nu stap twee van merge sort is gewoon paren samen te voegen aan de lijsten.

535
00:44:24,000 --> 00:44:27,610
Dus willen we deze samen te voegen. We noemen samen te voegen.

536
00:44:27,610 --> 00:44:31,410
We weten merge zullen deze terugkeren in gesorteerde volgorde.

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

538
00:44:33,920 --> 00:44:41,440
Nu willen we deze samenvoegen, en dat zal een lijst terug met die in gesorteerde volgorde,

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

540
00:44:44,160 --> 00:44:57,380
We samenvoegen die - ik kan niet schrijven - 8, 23 en 42, 108.

541
00:44:57,380 --> 00:45:02,890
Dus we hebben samengevoegd paren een keer.

542
00:45:02,890 --> 00:45:05,140
Nu zijn we gewoon weer samen te voegen.

543
00:45:05,140 --> 00:45:10,130
Merk op dat elk van deze lijsten gesorteerd op zichzelf

544
00:45:10,130 --> 00:45:15,220
en dan kunnen we gewoon samenvoegen deze lijsten om een ​​lijst van grootte 4, die wordt gesorteerd te krijgen

545
00:45:15,220 --> 00:45:19,990
en samenvoegen van deze twee lijsten om een ​​lijst met maat 4 dat wordt gesorteerd te krijgen.

546
00:45:19,990 --> 00:45:25,710
En tot slot, kunnen we samenvoegen die twee lijsten van grootte 4 om een ​​lijst met maat 8 die wordt gesorteerd te krijgen.

547
00:45:25,710 --> 00:45:34,030
Dus om te zien dat dit is over het algemeen n log n, zagen we al dat samenvoegen lineair is,

548
00:45:34,030 --> 00:45:40,390
dus als we te maken hebben met het samenvoegen van deze, dus als de totale kosten van de fusie

549
00:45:40,390 --> 00:45:43,410
voor deze twee lijsten is slechts 2 omdat -

550
00:45:43,410 --> 00:45:49,610
Of wel, het is o van n, maar n is vaak precies deze 2 elementen, dus het is 2.

551
00:45:49,610 --> 00:45:52,850
En deze 2 zal 2 en deze 2 zal 2 en deze 2 een 2,

552
00:45:52,850 --> 00:45:58,820
dus in alle van de samenvoegingen die we moeten doen, we uiteindelijk doen n.

553
00:45:58,820 --> 00:46:03,210
Zoals 2 + 2 + 2 + 2 8, dat n,

554
00:46:03,210 --> 00:46:08,060
zodat de kosten van het samenvoegen van in deze set is n.

555
00:46:08,060 --> 00:46:10,810
En dan is het hetzelfde hier.

556
00:46:10,810 --> 00:46:16,980
We zullen samenvoegen van deze 2, dan zijn deze 2, en individueel deze samenvoeging zal vier operaties,

557
00:46:16,980 --> 00:46:23,610
deze samenvoeging zal vier operaties, maar nogmaals, tussen al deze,

558
00:46:23,610 --> 00:46:29,030
we uiteindelijk samen te voegen n totaal dingen, en dus deze stap neemt n.

559
00:46:29,030 --> 00:46:33,670
En zo elk level duurt n elementen worden samengevoegd.

560
00:46:33,670 --> 00:46:36,110
>> En hoeveel levels zijn er?

561
00:46:36,110 --> 00:46:40,160
Op elk niveau, ons aanbod groeit met maat 2.

562
00:46:40,160 --> 00:46:44,590
Hier onze arrays zijn van maat 1, hier zijn ze van grootte 2, hier zijn ze van maat 4,

563
00:46:44,590 --> 00:46:46,470
en tot slot, ze zijn van maat 8.

564
00:46:46,470 --> 00:46:56,450
Dus aangezien verdubbelt, er zullen in totaal n log van deze niveaus.

565
00:46:56,450 --> 00:47:02,090
Dus met log n niveaus, elk individueel niveau rekening n totale bedrijfsactiviteiten,

566
00:47:02,090 --> 00:47:05,720
krijgen we een n log n algoritme.

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

568
00:47:08,940 --> 00:47:13,320
Al mensen hebben vooruitgang geboekt over hoe dit te implementeren?

569
00:47:13,320 --> 00:47:18,260
Is er iemand al in een staat waar ik kan gewoon omhoog trekken hun code?

570
00:47:20,320 --> 00:47:22,260
Ik kan een minuut.

571
00:47:24,770 --> 00:47:27,470
Deze gaat langer.

572
00:47:27,470 --> 00:47:28,730
I highly recommend terugkomen -

573
00:47:28,730 --> 00:47:30,510
Je hoeft niet te recursie doen voor samenvoegen

574
00:47:30,510 --> 00:47:33,750
want om recursie voor samenvoegen doen, je gaat te hebben om een ​​aantal verschillende maten passeren.

575
00:47:33,750 --> 00:47:37,150
Dat kan, maar het is vervelend.

576
00:47:37,150 --> 00:47:43,720
Maar recursie voor soort zelf is vrij eenvoudig.

577
00:47:43,720 --> 00:47:49,190
Je hoeft alleen letterlijk belt sorteren op de linker helft, sorteren op rechter helft. Oke.

578
00:47:51,770 --> 00:47:54,860
Iedereen heeft iets wat ik kan nog omhoog te trekken?

579
00:47:54,860 --> 00:47:57,540
Of anders geef ik een minuut.

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

581
00:47:59,900 --> 00:48:02,970
Iedereen heeft iets dat we kunnen samenwerken?

582
00:48:05,450 --> 00:48:09,680
Of we zullen gewoon werken met deze uit en vouw vervolgens vanaf daar.

583
00:48:09,680 --> 00:48:14,050
>> Iedereen heeft meer dan dit dat ik kan trekken?

584
00:48:14,050 --> 00:48:17,770
[Student] Ja. U kunt trekken mijne. >> Oke.

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

586
00:48:22,170 --> 00:48:25,280
[Student] Er waren een heleboel voorwaarden. >> Oh, schieten. Kunt u -

587
00:48:25,280 --> 00:48:28,110
[Student] Ik heb het op te slaan. >> Ja.

588
00:48:32,420 --> 00:48:35,730
Dus we hebben afzonderlijk doen de samenvoeging.

589
00:48:35,730 --> 00:48:38,570
Oh, maar het is niet zo slecht.

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

591
00:48:41,650 --> 00:48:47,080
Dus soort is zelf alleen maar bellen mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Leg ons uit wat mergeSortHelp doet.

593
00:48:49,530 --> 00:48:55,700
[Student] MergeSortHelp vrij doet veel van de twee belangrijke stappen:

594
00:48:55,700 --> 00:49:01,270
die elk de helft van de array vervolgens sorteren en beide samenvoegen.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Oke, dus geef me een seconde.

596
00:49:10,850 --> 00:49:13,210
Ik denk dat dit - >> [student] Ik moet -

597
00:49:17,100 --> 00:49:19,400
Ja. Ik mis iets.

598
00:49:19,400 --> 00:49:23,100
In samenvoegen, realiseer ik me dat ik nodig om een ​​nieuwe array te maken

599
00:49:23,100 --> 00:49:26,530
want ik kon het niet op zijn plaats. >> Ja. Dat kan niet. Te corrigeren.

600
00:49:26,530 --> 00:49:28,170
[Student] Dus ik maak een nieuwe array.

601
00:49:28,170 --> 00:49:31,510
Ik vergat aan het einde van samenvoegen om opnieuw te veranderen.

602
00:49:31,510 --> 00:49:34,490
Oke. We hebben een nieuwe array.

603
00:49:34,490 --> 00:49:41,000
In merge sort, is dit bijna altijd het geval.

604
00:49:41,000 --> 00:49:44,340
Deel van de kosten van een beter algoritme qua tijd

605
00:49:44,340 --> 00:49:47,310
is bijna altijd om een ​​beetje meer geheugen te gebruiken.

606
00:49:47,310 --> 00:49:51,570
Dus hier, maakt niet uit hoe je het doet samenvoegen sorteren,

607
00:49:51,570 --> 00:49:54,780
je zou onvermijdelijk moet u een aantal extra geheugen te gebruiken.

608
00:49:54,780 --> 00:49:58,240
Hij of zij een nieuwe array.

609
00:49:58,240 --> 00:50:03,400
En dan zeg je aan het eind we hoeven alleen maar nieuwe array te kopiëren naar de oorspronkelijke array.

610
00:50:03,400 --> 00:50:04,830
[Student] Ik denk het wel, ja.

611
00:50:04,830 --> 00:50:08,210
Ik weet niet of dat werkt op het gebied van het tellen door middel van verwijzing of wat dan ook -

612
00:50:08,210 --> 00:50:11,650
Ja, dan werkt het. >> [Student] Oke.

613
00:50:20,620 --> 00:50:24,480
Heb je geprobeerd het uitvoeren van deze? >> [Student] Nee, nog niet. >> Oke.

614
00:50:24,480 --> 00:50:28,880
Probeer het dan, en dan zal ik over te praten voor een tweede.

615
00:50:28,880 --> 00:50:35,200
[Student] Ik moet al de functie prototypes en alles hebben, toch?

616
00:50:37,640 --> 00:50:40,840
De functie prototypes. Oh, je bedoelt zoals - Ja.

617
00:50:40,840 --> 00:50:43,040
Sorteer roept mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Dus om te sorteren mergeSortHelp bellen, moet mergeSortHelp ofwel reeds zijn gedefinieerd

619
00:50:47,390 --> 00:50:56,370
voordat sorteren of hoeven we alleen maar het prototype. Kopieer en plak deze.

620
00:50:56,370 --> 00:50:59,490
En evenzo is mergeSortHelp roept samen te voegen,

621
00:50:59,490 --> 00:51:03,830
maar samenvoegen is nog niet gedefinieerd, dus we kunnen gewoon laten mergeSortHelp weten

622
00:51:03,830 --> 00:51:08,700
dat dat is wat samen te voegen gaat uitzien, en dat is dat.

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

624
00:51:22,770 --> 00:51:32,660
We hebben een probleem hier, waar we geen base case.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp recursieve is, dus elke recursieve functie

626
00:51:38,110 --> 00:51:42,610
gaat een soort van base case moet weten wanneer te stoppen recursief die zichzelf.

627
00:51:42,610 --> 00:51:45,590
Wat is ons basisscenario gaan worden hier? Ja.

628
00:51:45,590 --> 00:51:49,110
[Student] Als het formaat is 1? >> [Bowden] Ja.

629
00:51:49,110 --> 00:51:56,220
Dus, zoals we zagen daar, stopten we splitsen arrays

630
00:51:56,220 --> 00:52:01,850
toen we eenmaal in arrays van maat 1, die onvermijdelijk zijn gesorteerd zelf.

631
00:52:01,850 --> 00:52:09,530
Dus als de grootte gelijk is aan 1, we weten dat de array al gesorteerd,

632
00:52:09,530 --> 00:52:12,970
dus we kunnen gewoon terug.

633
00:52:12,970 --> 00:52:16,880
>> Merk op dat is leegte, zodat we niet terug niets bijzonder, we zijn net terug.

634
00:52:16,880 --> 00:52:19,580
Oke. Dus dat is ons basisscenario.

635
00:52:19,580 --> 00:52:27,440
Ik denk dat ons basisscenario kan ook als we toevallig samengaan van een array van grootte 0,

636
00:52:27,440 --> 00:52:30,030
we waarschijnlijk willen stoppen op een bepaald punt,

637
00:52:30,030 --> 00:52:33,610
zodat we zeggen van minder dan 2 of minder dan of gelijk aan 1

638
00:52:33,610 --> 00:52:37,150
zodat dit nu voor welke array.

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

640
00:52:38,870 --> 00:52:42,740
Dus dat is ons basisscenario.

641
00:52:42,740 --> 00:52:45,950
Nu wil je ons lopen door merge?

642
00:52:45,950 --> 00:52:49,140
Wat betekenen al deze gevallen betekenen?

643
00:52:49,140 --> 00:52:54,480
Hier boven, we gewoon doen hetzelfde idee, de -

644
00:52:56,970 --> 00:53:02,470
[Student] Ik moet passeren grootte met alle mergeSortHelp oproepen.

645
00:53:02,470 --> 00:53:10,080
Ik voegde formaat als een bijkomende primaire en het is er niet, zoals grootte / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, de grootte / 2, size / 2. >> [Student] Ja, en ook in de bovenstaande functie.

647
00:53:16,210 --> 00:53:21,320
[Bowden] hier? >> [Student] op het juiste formaat. >> [Bowden] Oh. Maat, maat? >> [Student] Ja.

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

649
00:53:23,010 --> 00:53:26,580
Laat me denken voor een tweede.

650
00:53:26,580 --> 00:53:28,780
Hebben we tegenkomen een probleem?

651
00:53:28,780 --> 00:53:33,690
We zijn altijd op de behandeling van de linker als 0. >> [Student] Nee.

652
00:53:33,690 --> 00:53:36,340
Dat is verkeerd ook. Sorry. Het moet start. Ja.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Oke. Ik vind dat beter.

654
00:53:39,230 --> 00:53:43,880
En einde. Oke.

655
00:53:43,880 --> 00:53:47,200
Dus nu wil je ons lopen door merge? >> [Student] Oke.

656
00:53:47,200 --> 00:53:52,150
Ik ben gewoon wandelen door deze nieuwe array die ik heb gemaakt.

657
00:53:52,150 --> 00:53:57,420
Het is de grootte van het deel van de array die we willen worden gesorteerd

658
00:53:57,420 --> 00:54:03,460
en proberen om het element en die ik moet in de nieuwe array stap vinden.

659
00:54:03,460 --> 00:54:10,140
Dus om dat te doen, eerst ben ik controleren of de linkerhelft van de array blijft nog meer elementen,

660
00:54:10,140 --> 00:54:14,260
en als het niet zo is, dan moet je naar beneden naar die andere voorwaarde, die gewoon zegt

661
00:54:14,260 --> 00:54:20,180
oke, moet het in de juiste array, en we zullen dat zet in de huidige index van newArray.

662
00:54:20,180 --> 00:54:27,620
>> En anders ik controleren of de rechterzijde van de array wordt ook beëindigd,

663
00:54:27,620 --> 00:54:30,630
in welk geval ik net in de linker.

664
00:54:30,630 --> 00:54:34,180
Dat zou eigenlijk nodig. Ik weet het niet zeker.

665
00:54:34,180 --> 00:54:40,970
Maar goed, de andere twee controle welke van de twee zijn kleiner in de linker-of de rechterkant.

666
00:54:40,970 --> 00:54:49,770
En ook in elk geval, ik ben het verhogen afhankelijk van welke tijdelijke aanduiding I verhogen.

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

668
00:54:52,040 --> 00:54:53,840
Dat ziet er goed uit.

669
00:54:53,840 --> 00:54:58,800
Heeft iemand opmerkingen of vragen hebt of vragen?

670
00:55:00,660 --> 00:55:07,720
Dus de vier gevallen die we hebben om dingen te brengen alleen maar - of het lijkt op vijf -

671
00:55:07,720 --> 00:55:13,100
maar we moeten overwegen of de linker-array leeg is van dingen die we nodig hebben om te fuseren,

672
00:55:13,100 --> 00:55:16,390
de vraag of de rechter array leeg is van dingen die we nodig hebben om te fuseren -

673
00:55:16,390 --> 00:55:18,400
Ik wees naar niets.

674
00:55:18,400 --> 00:55:21,730
Dus of de linker-array op is van de dingen of de rechter array leeg is van de dingen.

675
00:55:21,730 --> 00:55:24,320
Dat zijn twee gevallen.

676
00:55:24,320 --> 00:55:30,920
We moeten ook de triviale geval van de vraag of de linker ding is kleiner dan het juiste ding.

677
00:55:30,920 --> 00:55:33,910
Dan willen we aan de linkerkant iets te kiezen.

678
00:55:33,910 --> 00:55:37,630
Dat zijn de gevallen.

679
00:55:37,630 --> 00:55:40,990
Dus dit was goed, dus dat is dat.

680
00:55:40,990 --> 00:55:46,760
Array vertrokken. Het is 1, 2, 3. Oke. Dus ja, dat zijn de vier dingen die we zouden willen doen.

681
00:55:50,350 --> 00:55:54,510
En we zullen niet gaan over een iteratieve oplossing.

682
00:55:54,510 --> 00:55:55,980
Ik zou niet aanraden -

683
00:55:55,980 --> 00:56:03,070
Merge sort is een voorbeeld van een functie die zowel niet staart recursieve,

684
00:56:03,070 --> 00:56:07,040
het is niet gemakkelijk om het staart recursieve,

685
00:56:07,040 --> 00:56:13,450
maar ook het is niet erg makkelijk te maken iteratieve.

686
00:56:13,450 --> 00:56:16,910
Dit is erg gemakkelijk.

687
00:56:16,910 --> 00:56:19,170
Deze implementatie van merge sort,

688
00:56:19,170 --> 00:56:22,140
samenvoegen, maakt niet uit wat je doet, je gaat samenvoegen bouwen.

689
00:56:22,140 --> 00:56:29,170
>> Dus samenvoegen sorteren gebouwd op de top van de merge recursief is gewoon deze drie lijnen.

690
00:56:29,170 --> 00:56:34,700
Iteratief, het is meer vervelend en moeilijker om na te denken over.

691
00:56:34,700 --> 00:56:41,860
Maar let erop dat het niet de staart recursieve sinds mergeSortHelp - wanneer het noemt zichzelf -

692
00:56:41,860 --> 00:56:46,590
Het moet nog dingen te doen na deze recursieve aanroep terug.

693
00:56:46,590 --> 00:56:50,830
Dus dit stack frame moet blijven bestaan, zelfs na het aanroepen van deze.

694
00:56:50,830 --> 00:56:54,170
En dan, als je dit noemen, moet de stack frame blijven bestaan

695
00:56:54,170 --> 00:56:57,780
want zelfs na dat gesprek, we moeten nog steeds om te fuseren.

696
00:56:57,780 --> 00:57:01,920
En het is niet-triviaal om deze staart recursieve.

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

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

699
00:57:09,860 --> 00:57:13,400
Dus terug te gaan naar sorteren - oh, er zijn twee dingen die ik wil laten zien. Oke.

700
00:57:13,400 --> 00:57:17,840
Terug te gaan naar soort, zullen we dit snel doen.

701
00:57:17,840 --> 00:57:21,030
Of zoek. Sorteer? Sorteren. Ja.

702
00:57:21,030 --> 00:57:22,730
Terug te gaan naar het begin van de soort.

703
00:57:22,730 --> 00:57:29,870
We willen een algoritme dat sorteert de array met behulp van een algoritme te creëren

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

705
00:57:33,660 --> 00:57:40,860
Dus hoe is dit mogelijk? Heeft iemand enig soort van -

706
00:57:40,860 --> 00:57:44,300
Ik zinspeelde eerder bij -

707
00:57:44,300 --> 00:57:48,300
Als we op het punt om te verbeteren van n log n N en O van n,

708
00:57:48,300 --> 00:57:51,450
we hebben ons algoritme qua tijd,

709
00:57:51,450 --> 00:57:55,250
wat betekent dat wat gaan we moeten doen om goed te maken dat?

710
00:57:55,250 --> 00:57:59,520
[Student] Space. >> Ja. We gaan gebruik maken van meer ruimte.

711
00:57:59,520 --> 00:58:04,490
En zelfs niet alleen meer ruimte, het is exponentieel meer ruimte.

712
00:58:04,490 --> 00:58:14,320
Dus ik denk dat dit soort algoritme is pseudo iets, pseudo polynoom -

713
00:58:14,320 --> 00:58:18,980
pseudo - Ik kan me niet herinneren. Pseudo iets.

714
00:58:18,980 --> 00:58:22,210
Maar het is, want we moeten zo veel ruimte te gebruiken

715
00:58:22,210 --> 00:58:28,610
dat dit haalbaar is, maar niet realistisch.

716
00:58:28,610 --> 00:58:31,220
>> En hoe gaan we dat bereiken?

717
00:58:31,220 --> 00:58:36,810
We kunnen bereiken als we garantie dat een bepaald element in de array

718
00:58:36,810 --> 00:58:39,600
lager is dan een bepaalde grootte.

719
00:58:42,070 --> 00:58:44,500
Dus laten we gewoon zeggen dat de grootte is 200,

720
00:58:44,500 --> 00:58:48,130
elk element in een array is dan maat 200.

721
00:58:48,130 --> 00:58:51,080
En dit is eigenlijk heel realistisch.

722
00:58:51,080 --> 00:58:58,660
U kunt heel gemakkelijk een array die u alles te weten in het

723
00:58:58,660 --> 00:59:00,570
zal minder dan een getal.

724
00:59:00,570 --> 00:59:07,400
Net als je wat echt enorm vector of iets

725
00:59:07,400 --> 00:59:11,810
maar je weet dat alles zal worden tussen 0 en 5,

726
00:59:11,810 --> 00:59:14,790
dan is het gaat worden aanzienlijk sneller om dit te doen.

727
00:59:14,790 --> 00:59:17,930
En de gebonden op een van de elementen 5,

728
00:59:17,930 --> 00:59:21,980
dus dit gebonden, dat is hoeveel geheugen je gaat gebruiken.

729
00:59:21,980 --> 00:59:26,300
Dus het gebonden is 200.

730
00:59:26,300 --> 00:59:32,960
In theorie is er altijd een gebonden omdat een integer kan alleen tot 4 miljard

731
00:59:32,960 --> 00:59:40,600
maar dat is niet realistisch sindsdien zouden we gebruik van de ruimte

732
00:59:40,600 --> 00:59:44,400
in de orde van 4 miljard. Dus dat is niet realistisch.

733
00:59:44,400 --> 00:59:47,060
Maar hier zullen we zeggen dat onze gebonden is 200.

734
00:59:47,060 --> 00:59:59,570
De truc om het te doen in O van n is maken we nog een array met de naam tellingen van grootte GEBONDEN.

735
00:59:59,570 --> 01:00:10,470
Dus eigenlijk is dit een snelkoppeling voor - ik eigenlijk weet niet of Clang dit doet.

736
01:00:11,150 --> 01:00:15,330
Maar in GCC op zijn minst - Ik ben ervan uitgaande dat Clang doet het ook -

737
01:00:15,330 --> 01:00:18,180
Dit zal alleen initialiseren van de hele array te 0s.

738
01:00:18,180 --> 01:00:25,320
Dus als ik niet wil om dat te doen, dan kon ik apart doen for (int i = 0;

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

740
01:00:31,500 --> 01:00:35,260
Dus nu alles wordt geïnitialiseerd op 0.

741
01:00:35,260 --> 01:00:39,570
Ik itereren over mijn array,

742
01:00:39,570 --> 01:00:51,920
en wat ik doe is dat ik het nummer van elk tellen - Laten we hier naar beneden gaan.

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

744
01:00:55,480 --> 01:01:00,010
Wat ik reken is het aantal keren dat elk van deze elementen.

745
01:01:00,010 --> 01:01:03,470
Laten we eigenlijk nog een paar toe te voegen in hier met een aantal herhalingen.

746
01:01:03,470 --> 01:01:11,070
Dus de waarde die we hier hebben, wordt de waarde van die zal worden array [i].

747
01:01:11,070 --> 01:01:14,850
Dus val zou kunnen zijn 4 of 8 of wat dan ook.

748
01:01:14,850 --> 01:01:18,870
En nu ben ik te tellen hoeveel van die waarde die ik heb gezien,

749
01:01:18,870 --> 01:01:21,230
dus telt [val] + +;

750
01:01:21,230 --> 01:01:29,430
Nadat dit is gedaan, wordt tellingen gaat iets eruit 0001.

751
01:01:29,430 --> 01:01:42,190
Laten we het doen telt [val] - GEBONDEN + 1.

752
01:01:42,190 --> 01:01:48,230
>> Nu dat is gewoon om te corrigeren voor het feit dat we vanaf 0.

753
01:01:48,230 --> 01:01:50,850
Dus als 200 gaat onze grootste getal zijn,

754
01:01:50,850 --> 01:01:54,720
dan 0 tot 200 is 201 dingen.

755
01:01:54,720 --> 01:02:01,540
Dus telt, zal het lijken 00001, omdat we een 4.

756
01:02:01,540 --> 01:02:10,210
Dan hebben we 0001 waar we een 1 hebben in de 8e index van tellen.

757
01:02:10,210 --> 01:02:14,560
We hebben een 2 in de 23e index van tellen.

758
01:02:14,560 --> 01:02:17,630
We hebben een 2 in de 42e index van tellen.

759
01:02:17,630 --> 01:02:21,670
Dus we kunnen gebruiken tellen.

760
01:02:34,270 --> 01:02:44,920
Dus num_of_item = telt [i].

761
01:02:44,920 --> 01:02:52,540
En dus als num_of_item 2 is, betekent dat we willen 2 te plaatsen van het getal i

762
01:02:52,540 --> 01:02:55,290
in onze gesorteerde array.

763
01:02:55,290 --> 01:03:02,000
Dus we moeten om bij te houden hoe ver we zijn in de array.

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

765
01:03:05,470 --> 01:03:09,910
Array - Ik zal gewoon schrijven.

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

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

768
01:03:28,580 --> 01:03:32,490
Is dat wat ik wil? Ik denk dat dat is wat ik wil.

769
01:03:35,100 --> 01:03:38,290
Ja, dit ziet er goed uit. Oke.

770
01:03:38,290 --> 01:03:43,050
Dus heeft iedereen begrijpt wat het doel van mijn tellingen array is?

771
01:03:43,050 --> 01:03:48,140
Het tellen van het aantal keren dat elk van deze nummers.

772
01:03:48,140 --> 01:03:51,780
Dan ben ik itereren over dat telt array,

773
01:03:51,780 --> 01:03:57,190
en het ide positie in de matrix telt

774
01:03:57,190 --> 01:04:01,930
is het aantal i's dat moet worden weergegeven in mijn gesorteerde array.

775
01:04:01,930 --> 01:04:06,840
Daarom telt van 4 gaat op 1

776
01:04:06,840 --> 01:04:11,840
en tellingen van 8 gaat worden 1 wordt tellingen van 23 zal worden 2.

777
01:04:11,840 --> 01:04:16,900
Dus dat is hoe velen van hen wil ik invoegen in mijn gesorteerde array.

778
01:04:16,900 --> 01:04:19,200
Tot slot heb ik dat doen.

779
01:04:19,200 --> 01:04:28,960
Ik ben het invoegen van num_of_item i's in mijn gesorteerde array.

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

781
01:04:32,460 --> 01:04:43,100
En dus nogmaals, dit is lineaire tijd geleden dat we zijn gewoon itereren over deze ene keer,

782
01:04:43,100 --> 01:04:47,470
maar het is ook lineair in wat dit nummer zich bevindt,

783
01:04:47,470 --> 01:04:50,730
en dus het hangt sterk af van wat je gebonden is.

784
01:04:50,730 --> 01:04:53,290
Met een gebonden van 200, dat is niet zo erg.

785
01:04:53,290 --> 01:04:58,330
Als je gebonden gaat worden 10.000, dan is dat een beetje erger,

786
01:04:58,330 --> 01:05:01,360
maar als je gebonden gaat worden 4 miljard, dat is volkomen onrealistisch

787
01:05:01,360 --> 01:05:07,720
en deze array zal moeten worden van maat 4 miljard, hetgeen niet realistisch is.

788
01:05:07,720 --> 01:05:10,860
Dus dat is dat. Vragen?

789
01:05:10,860 --> 01:05:13,270
[Onverstaanbaar student reactie] >> Oke.

790
01:05:13,270 --> 01:05:15,710
Ik realiseerde me een ander ding toen we gaan door.

791
01:05:17,980 --> 01:05:23,720
Ik denk dat het probleem was in Lucas en waarschijnlijk een ieder die we hebben gezien.

792
01:05:23,720 --> 01:05:26,330
Ik ben het helemaal vergeten.

793
01:05:26,330 --> 01:05:31,040
Het enige wat ik wilde commentaar geven op is dat wanneer je te maken hebt met dingen als indices,

794
01:05:31,040 --> 01:05:38,320
je nooit echt zien als je aan het schrijven bent een for-lus,

795
01:05:38,320 --> 01:05:41,120
maar technisch, wanneer je te maken hebt met deze indices,

796
01:05:41,120 --> 01:05:45,950
moet u vrijwel altijd te gaan met gehele getallen zonder teken.

797
01:05:45,950 --> 01:05:53,850
De reden hiervoor is als je te maken hebt met ondertekend integers,

798
01:05:53,850 --> 01:05:56,090
dus als je 2 getekend gehele getallen en voegt u ze samen

799
01:05:56,090 --> 01:06:00,640
en ze uiteindelijk te groot, dan eindig je met een negatief getal.

800
01:06:00,640 --> 01:06:03,410
Dus dat is wat integer overflow is.

801
01:06:03,410 --> 01:06:10,500
>> Als ik voeg 2 miljard en 1 miljard, ik eindigen met een negatieve 1 miljard.

802
01:06:10,500 --> 01:06:15,480
Dat is hoe integers werken op computers.

803
01:06:15,480 --> 01:06:17,510
Het probleem met het gebruik -

804
01:06:17,510 --> 01:06:23,500
Dat is goed, behalve als lage toevallig 2 miljard en tot toevallig 1 miljard,

805
01:06:23,500 --> 01:06:27,120
dan gaat dit als negatief 1 miljard en dan gaan we delen door 2

806
01:06:27,120 --> 01:06:29,730
en eindigen met een negatieve 500 miljoen.

807
01:06:29,730 --> 01:06:33,760
Dus dit is alleen een probleem als je toevallig op zoek door middel van een reeks

808
01:06:33,760 --> 01:06:38,070
van miljarden dingen.

809
01:06:38,070 --> 01:06:44,050
Maar als lage + tot overkomt overloop, dan is dat een probleem.

810
01:06:44,050 --> 01:06:47,750
Zodra we ze niet ondertekend, dan 2 miljard plus 1 miljard 3 miljard.

811
01:06:47,750 --> 01:06:51,960
3 miljard gedeeld door 2 is 1,5 miljard.

812
01:06:51,960 --> 01:06:55,670
Dus zodra ze unsigned zijn, alles is perfect.

813
01:06:55,670 --> 01:06:59,900
En dat is dus ook een probleem als je het schrijven van uw voor loops,

814
01:06:59,900 --> 01:07:03,940
en eigenlijk, het doet waarschijnlijk automatisch.

815
01:07:09,130 --> 01:07:12,330
Het zal eigenlijk alleen maar schreeuwen naar je.

816
01:07:12,330 --> 01:07:21,610
Dus als dit aantal is te groot om in slechts een geheel getal, maar het zou passen in een geheel getal zonder teken,

817
01:07:21,610 --> 01:07:24,970
het zal schreeuwen tegen je, dus dat is waarom je nooit echt lopen in de kwestie.

818
01:07:29,150 --> 01:07:34,820
Je kunt zien dat een index nooit gaat worden negatief,

819
01:07:34,820 --> 01:07:39,220
en dus als je itereren over een array,

820
01:07:39,220 --> 01:07:43,970
je kunt bijna altijd zeggen unsigned int i, maar je hoeft niet echt.

821
01:07:43,970 --> 01:07:47,110
Dingen gaan vrij veel werken net zo goed.

822
01:07:48,740 --> 01:07:50,090
Oke. [Fluistert] Hoe laat is het?

823
01:07:50,090 --> 01:07:54,020
Het laatste wat ik wilde laten zien - en ik zal het gewoon doen echt snel.

824
01:07:54,020 --> 01:08:03,190
Je weet hoe we # hebben gedefinieerd, zodat we kunnen # MAX definiëren als 5 of zo?

825
01:08:03,190 --> 01:08:05,940
Laten we niet doen MAX. # Define gebonden als 200. Dat is wat we eerder deden.

826
01:08:05,940 --> 01:08:10,380
Dat definieert een constante, die net zal worden gekopieerd en geplakt

827
01:08:10,380 --> 01:08:13,010
waar we toevallig schrijven GEBONDEN.

828
01:08:13,010 --> 01:08:18,189
>> Dus we kunnen eigenlijk meer doen met # definieert.

829
01:08:18,189 --> 01:08:21,170
We kunnen # define functies.

830
01:08:21,170 --> 01:08:23,410
Ze zijn niet echt functies, maar we zullen noemen ze functies.

831
01:08:23,410 --> 01:08:36,000
Een voorbeeld zou zoiets MAX (x, y) worden gedefinieerd als (x <y y: x). Oke.

832
01:08:36,000 --> 01:08:40,660
Dus je moet wennen aan ternaire operator syntax,

833
01:08:40,660 --> 01:08:49,029
maar is x kleiner dan y? Terug y, of teruggaan x.

834
01:08:49,029 --> 01:08:54,390
Zodat u kunt zien kunt u deze een aparte functie maken,

835
01:08:54,390 --> 01:09:01,399
en de functie zou kunnen uitzien bool MAX duurt 2 argumenten, terugsturen.

836
01:09:01,399 --> 01:09:08,340
Dit is een van de meest voorkomende die ik zie gebeuren als deze. We noemen ze macro's.

837
01:09:08,340 --> 01:09:11,790
Dit is een macro.

838
01:09:11,790 --> 01:09:15,859
Dit is gewoon de syntax voor.

839
01:09:15,859 --> 01:09:18,740
U kunt een macro om te doen wat je wilt.

840
01:09:18,740 --> 01:09:22,649
Je vaak ziet macro's voor het debuggen printfs en dat soort dingen.

841
01:09:22,649 --> 01:09:29,410
Dus een soort van printf, zijn er speciale constanten in C als underscore LINE onderstrepen,

842
01:09:29,410 --> 01:09:31,710
2 onderstreept underscore LINE,

843
01:09:31,710 --> 01:09:37,550
en er is ook denk ik 2 FUNC onderstrepingstekens. Dat zou het zijn. Zoiets.

844
01:09:37,550 --> 01:09:40,880
Die dingen worden vervangen door de naam van de functie

845
01:09:40,880 --> 01:09:42,930
of het nummer van de lijn die je op.

846
01:09:42,930 --> 01:09:48,630
Vaak, schrijf je debuggen printfs dat hier beneden ik toen kon gewoon schrijven

847
01:09:48,630 --> 01:09:54,260
DEBUG en het zal het regelnummer en de functie die ik toevallig in af te drukken

848
01:09:54,260 --> 01:09:57,020
dat het dat DEBUG statement ondervonden.

849
01:09:57,020 --> 01:09:59,550
En u kunt ook afdrukken andere dingen.

850
01:09:59,550 --> 01:10:05,990
Dus een ding dat je moet oppassen voor is als ik toevallig # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
als iets als 2 * y en 2 * x.

852
01:10:11,380 --> 01:10:14,310
Dus voor welke reden dan ook, je toevallig te doen dat veel.

853
01:10:14,310 --> 01:10:16,650
Dus maak er een macro.

854
01:10:16,650 --> 01:10:18,680
Dit is eigenlijk gebroken.

855
01:10:18,680 --> 01:10:23,050
Ik zou het door het doen van iets als DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Dus wat moet worden geretourneerd?

857
01:10:28,840 --> 01:10:30,580
[Student] 12.

858
01:10:30,580 --> 01:10:34,800
Ja, moet 12 worden geretourneerd, en 12 wordt geretourneerd.

859
01:10:34,800 --> 01:10:43,350
3 wordt vervangen voor x, wordt 6 vervangen voor y, en keren we terug 2 * 6, dat is 12.

860
01:10:43,350 --> 01:10:47,710
Nu hoe zit dit? Wat moet worden geretourneerd?

861
01:10:47,710 --> 01:10:50,330
[Student] 14. >> Idealiter 14.

862
01:10:50,330 --> 01:10:55,290
Het probleem is dat de manier waarop hash definieert werk, bedenk het is een letterlijke kopiëren en plakken

863
01:10:55,290 --> 01:11:00,160
van vrijwel alles, dus wat dit gaat worden geïnterpreteerd als

864
01:11:00,160 --> 01:11:11,270
is 3 minder dan 1 plus 6, 2 keer 1 plus 6, 2 keer 3.

865
01:11:11,270 --> 01:11:19,780
>> Dus om deze reden je bijna altijd wikkel alles tussen haakjes.

866
01:11:22,180 --> 01:11:25,050
Elke variabele die u bijna altijd wikkelen tussen haakjes.

867
01:11:25,050 --> 01:11:29,570
Er zijn gevallen waarin u niet hoeft te, zoals ik weet dat ik niet hoef te doen hier, dat

868
01:11:29,570 --> 01:11:32,110
omdat er minder dan vrijwel altijd gewoon naar het werk gaan,

869
01:11:32,110 --> 01:11:34,330
hoewel dat misschien niet eens waar.

870
01:11:34,330 --> 01:11:41,870
Als er iets is belachelijk als DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
dan dat gaat om te vervangen door 3 minder dan 1 gelijk is gelijk aan 2,

872
01:11:49,760 --> 01:11:53,460
en dus dan het gaat doen 3 kleiner dan 1, betekent dat gelijk aan 2,

873
01:11:53,460 --> 01:11:55,620
dat is niet wat we willen.

874
01:11:55,620 --> 01:12:00,730
Dus om elke exploitant voorrang problemen te voorkomen,

875
01:12:00,730 --> 01:12:02,870
altijd wikkel tussen haakjes.

876
01:12:03,290 --> 01:12:07,700
Oke. En dat is het, 5:30.

877
01:12:08,140 --> 01:12:12,470
Als u nog vragen heeft over het PSET, laat het ons weten.

878
01:12:12,470 --> 01:12:18,010
Het moet leuk zijn, en de hacker editie is ook veel realistischer

879
01:12:18,010 --> 01:12:22,980
dan de hacker editie van vorig jaar, dus we hopen dat veel van jullie het te proberen.

880
01:12:22,980 --> 01:12:26,460
Vorig jaar was erg overweldigend.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]