1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Artikel 3 - meer gemaklik]

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

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

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

5
00:00:12,700 --> 00:00:17,480
GDB kan jy "debug" 'n program, maar, meer spesifiek, wat beteken dit laat jy doen?

6
00:00:17,480 --> 00:00:22,590
Ek sal antwoord dat 'n mens, en ek weet nie wat presies verwag,

7
00:00:22,590 --> 00:00:27,910
so ek vermoed dit is iets langs die lyne van dit kan jou stap vir stap

8
00:00:27,910 --> 00:00:31,540
wandel deur die program, met dit, verandering veranderlikes, al hierdie dinge doen -

9
00:00:31,540 --> 00:00:34,270
basies heeltemal beheer oor die uitvoering van 'n program

10
00:00:34,270 --> 00:00:38,410
en inspekteer enige gegewe deel van die uitvoering van die program.

11
00:00:38,410 --> 00:00:43,030
So daardie funksies laat jy ontfout dinge.

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

13
00:00:44,830 --> 00:00:50,520
Waarom binêre soek vereis dat 'n skikking gesorteer word?

14
00:00:50,520 --> 00:00:53,360
Wie wil om te beantwoord?

15
00:00:56,120 --> 00:01:00,070
[Student] Omdat dit nie werk as dit nie gesorteer. >> Ja. [Lag]

16
00:01:00,070 --> 00:01:04,910
As dit nie gesorteer, dan is dit onmoontlik om dit te verdeel in die helfte

17
00:01:04,910 --> 00:01:07,850
en weet dat alles aan die linkerkant is minder en alles aan die regterkant

18
00:01:07,850 --> 00:01:10,490
is groter as die middelste waarde.

19
00:01:10,490 --> 00:01:12,790
So dit moet gesorteer.

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

21
00:01:14,170 --> 00:01:17,570
Hoekom is borrel soort in die O van n kwadraat?

22
00:01:17,570 --> 00:01:23,230
Is daar iemand wil eers 'n baie vinnige hoë-vlak oorsig te gee van wat borrel soort is?

23
00:01:25,950 --> 00:01:33,020
[Student] Jy het basies gaan deur elke element en jy kyk na die eerste paar elemente.

24
00:01:33,020 --> 00:01:37,150
As hulle uit waar jy ruil, dan moet jy gaan die volgende paar elemente en so aan.

25
00:01:37,150 --> 00:01:40,770
Wanneer jy aan die einde, dan weet jy dat die grootste element is aan die einde geplaas,

26
00:01:40,770 --> 00:01:42,750
sodat jy ignoreer dat 'n mens dan hou jy gaan deur,

27
00:01:42,750 --> 00:01:48,490
en elke keer as jy het een minder element om seker te maak totdat jy geen veranderinge maak. >> Ja.

28
00:01:48,490 --> 00:01:58,470
Dit is genoem borrel soort, want as jy draai die reeks op sy kant so dit is op en af, vertikale,

29
00:01:58,470 --> 00:02:03,100
dan is die groot waardes sal sink na die bodem en die klein waardes sal borrel op die top.

30
00:02:03,100 --> 00:02:05,210
Dit is hoe dit sy naam gekry het.

31
00:02:05,210 --> 00:02:08,220
En ja, jy gaan net deur.

32
00:02:08,220 --> 00:02:11,190
Jy hou gaan deur middel van die skikking, die uitruiling van die groter waarde

33
00:02:11,190 --> 00:02:14,040
die grootste waardes te kry aan die onderkant.

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

35
00:02:18,690 --> 00:02:24,620
Eerstens, nie almal wil om te sê waarom dit is O van n kwadraat?

36
00:02:24,620 --> 00:02:28,760
[Student] Omdat dit gaan vir elke lopie n keer.

37
00:02:28,760 --> 00:02:32,100
Jy kan net seker wees dat jy die grootste element al die pad af,

38
00:02:32,100 --> 00:02:35,230
dan het jy om dit te herhaal soveel elemente. >> Ja.

39
00:02:35,230 --> 00:02:41,800
So in gedagte hou wat die groot O beteken en watter groot Omega beteken.

40
00:02:41,800 --> 00:02:50,560
Die Big O is soos die bogrens op hoe stadig dit kan eintlik loop.

41
00:02:50,560 --> 00:02:58,990
Dus, deur te sê dit is O van n kwadraat, dit is nie O van n of anders dit sal in staat wees om uit te voer

42
00:02:58,990 --> 00:03:02,640
in lineêre tyd, maar dit is O van n blokkies gesny

43
00:03:02,640 --> 00:03:06,390
want dit word begrens deur O van n blokkies gesny.

44
00:03:06,390 --> 00:03:12,300
As dit begrens deur O van n kwadraat, dan is dit is ook begrens deur n blokkies gesny.

45
00:03:12,300 --> 00:03:20,280
So is dit N vierkantig en in die absolute ergste geval kan dit nie beter doen as n kwadraat,

46
00:03:20,280 --> 00:03:22,830
wat is die rede waarom dit is O N kwadraat.

47
00:03:22,830 --> 00:03:31,200
So effense wiskunde te sien hoe dit kom uit n-kwadraat,

48
00:03:31,200 --> 00:03:40,530
as ons vyf dinge in ons lys vir die eerste keer hoeveel swaps ons kan potensieel nodig het om te maak

49
00:03:40,530 --> 00:03:47,170
om dit te kry? Kom ons eintlik net -

50
00:03:47,170 --> 00:03:52,040
Hoeveel swaps gaan ons te maak in die eerste lopie van die soort van borrel deur die skikking?

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

52
00:03:53,540 --> 00:03:58,340
>> As daar is 5 elemente, gaan ons 'n te maak - 1.

53
00:03:58,340 --> 00:04:01,100
Dan op die tweede een hoeveel swaps gaan ons maak?

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

55
00:04:03,440 --> 00:04:11,640
En die derde is gaan 'n - 3, en dan vir die gerief Ek sal die laaste twee

56
00:04:11,640 --> 00:04:15,270
as dan gaan ons moet 2 swaps en 1 swap te maak.

57
00:04:15,270 --> 00:04:19,899
Ek dink die laaste een mag of mag eintlik nie nodig het om te gebeur.

58
00:04:19,899 --> 00:04:22,820
Is dit 'n ruil? Ek weet nie.

59
00:04:22,820 --> 00:04:26,490
So dit is die totale bedrae van swaps of ten minste vergelykings wat jy moet maak.

60
00:04:26,490 --> 00:04:29,910
Selfs as jy nie ruil nie, jy nog steeds nodig om die waardes te vergelyk.

61
00:04:29,910 --> 00:04:33,910
So daar is n - 1 vergelykings in die eerste lopie deur die skikking.

62
00:04:33,910 --> 00:04:42,050
As jy hierdie dinge herrangskik, laat ons eintlik maak dit ses dinge so dinge stapels mooi,

63
00:04:42,050 --> 00:04:44,790
en dan sal ek doen 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Dus net herrangskikking van hierdie somme, ons wil om te sien hoeveel vergelykings maak ons

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

66
00:04:52,700 --> 00:04:56,550
So as ons bring hierdie ouens hier,

67
00:04:56,550 --> 00:05:07,470
dan is ons net nog n opsomming egter baie vergelykings daar was.

68
00:05:07,470 --> 00:05:13,280
Maar as ons som hierdie en ons som hierdie en ons som hierdie,

69
00:05:13,280 --> 00:05:18,130
dit is nog steeds dieselfde probleem. Ons het net som daardie bepaalde groepe.

70
00:05:18,130 --> 00:05:22,400
>> So nou het ons n opsomming 3 n. Dit is nie net 3 n.

71
00:05:22,400 --> 00:05:27,650
Dit is altyd gaan wees n / 2 n.

72
00:05:27,650 --> 00:05:29,430
So hier is ons gebeur het 6.

73
00:05:29,430 --> 00:05:34,830
As ons 10 dinge, dan kan ons hierdie groepering vir 5 verskillende pare van dinge doen

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

75
00:05:37,180 --> 00:05:45,840
Sodat jy altyd gaan n / 2 n te kry, en so dit sal ons skryf dit uit na n kwadraat / 2.

76
00:05:45,840 --> 00:05:48,890
En so selfs al is dit die faktor van 1/2, wat gebeur om in te kom

77
00:05:48,890 --> 00:05:54,190
as gevolg van die feit dat ons deur middel van elke iterasie oor die skikking vergelyk 1 minder

78
00:05:54,190 --> 00:05:58,040
so dit is hoe kry ons die meer as 2, maar dit is nog steeds N kwadraat.

79
00:05:58,040 --> 00:06:01,650
Ons gee nie om oor die konstante faktor van 'n half.

80
00:06:01,650 --> 00:06:07,760
So het 'n baie van die groot O stuff soos hierdie is afhanklik van net soort van doen hierdie soort van wiskunde,

81
00:06:07,760 --> 00:06:12,260
rekenkundige somme en meetkundige reeks dinge te doen,

82
00:06:12,260 --> 00:06:17,750
maar die meeste van hulle in hierdie kursus is redelik eenvoudig.

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

84
00:06:19,290 --> 00:06:24,430
Hoekom is invoeging soort in die Omega van n? Wat beteken omega beteken?

85
00:06:24,430 --> 00:06:27,730
[Twee studente praat in 'n keer - onverstaanbaar] >> Ja.

86
00:06:27,730 --> 00:06:30,630
Omega jy kan dink as die ondergrens.

87
00:06:30,630 --> 00:06:36,550
>> So maak nie saak hoe doeltreffend jou invoeging soort algoritme is,

88
00:06:36,550 --> 00:06:41,810
ongeag van die lys wat in geslaag is, het dit altyd ten minste N dinge te vergelyk

89
00:06:41,810 --> 00:06:44,620
of dit 'om oor n dinge te itereer.

90
00:06:44,620 --> 00:06:47,280
Hoekom is dit?

91
00:06:47,280 --> 00:06:51,190
[Student] Want as die lys is reeds gesorteer is, dan deur die eerste iterasie

92
00:06:51,190 --> 00:06:54,080
jy kan net waarborg dat die heel eerste element is die minste,

93
00:06:54,080 --> 00:06:56,490
en die tweede iterasie jy kan net waarborg die eerste twee

94
00:06:56,490 --> 00:07:00,010
want jy weet nie wat die res van die lys is gesorteer. >> Ja.

95
00:07:00,010 --> 00:07:08,910
As jy slaag in 'n heeltemal gesorteerde lys, op die heel minste wat jy het om te gaan oor al die elemente

96
00:07:08,910 --> 00:07:12,180
om te sien dat niks rondgeskuif moet word.

97
00:07:12,180 --> 00:07:14,720
So wat oor die lys en sê: O, dit is reeds gesorteer,

98
00:07:14,720 --> 00:07:18,240
dit is onmoontlik om te weet dit is gesorteer totdat jy kyk elke element

99
00:07:18,240 --> 00:07:20,660
om te sien dat hulle in gesorteer einde.

100
00:07:20,660 --> 00:07:25,290
So het die laer gebind op die invoeging soort is Omega van n.

101
00:07:25,290 --> 00:07:28,210
Wat is die ergste geval loop die tyd van merge soort,

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

103
00:07:31,390 --> 00:07:37,660
Dus, in die ergste geval scenario, hoe merge soort loop?

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

105
00:07:43,690 --> 00:07:49,990
Die vinnigste algemene sorteer-algoritmes is n log n. Jy kan nie beter doen.

106
00:07:51,930 --> 00:07:55,130
>> Daar is spesiale gevalle, en as ons vandag tyd - maar ons waarskynlik won't -

107
00:07:55,130 --> 00:07:59,330
ons kon sien die een wat nie beter is as n log n.

108
00:07:59,330 --> 00:08:04,050
Maar in die algemene geval, kan jy nie beter doen as n log n.

109
00:08:04,050 --> 00:08:09,680
En voeg soort gebeur met die een wat jy moet weet vir hierdie kursus is n log n.

110
00:08:09,680 --> 00:08:13,260
En so sal ons eintlik die uitvoering van dit vandag.

111
00:08:13,260 --> 00:08:18,070
En ten slotte, in nie meer as drie sinne, hoe werk seleksie soort?

112
00:08:18,070 --> 00:08:20,370
Iemand wil om te antwoord, en ek sal jou sinne tel

113
00:08:20,370 --> 00:08:22,390
want as jy gaan oor 3 -

114
00:08:25,530 --> 00:08:28,330
Nie almal onthou seleksie soort?

115
00:08:31,280 --> 00:08:37,809
Seleksie soort is gewoonlik redelik maklik om te onthou net van die naam.

116
00:08:37,809 --> 00:08:45,350
Jy moet net itereer oor die skikking, wat ook al die grootste waarde is of die kleinste -

117
00:08:45,350 --> 00:08:47,290
watter volgorde jy sorteer.

118
00:08:47,290 --> 00:08:50,750
So laat ons sê ons sorteer van die kleinste tot die grootste.

119
00:08:50,750 --> 00:08:55,250
Jy itereer oor die skikking, soek vir alles wat die minimum element is,

120
00:08:55,250 --> 00:08:59,750
kies dit, en dan net ruil dit alles is in die eerste plek.

121
00:08:59,750 --> 00:09:04,090
En dan op die tweede verby die skikking, kyk weer vir die minimum element,

122
00:09:04,090 --> 00:09:07,490
kies, en dan ruil dit met wat in die tweede posisie is.

123
00:09:07,490 --> 00:09:10,650
So ons is net pluk en die keuse van die minimum waardes

124
00:09:10,650 --> 00:09:16,050
en die invoeging van hulle in die voorkant van die skikking totdat dit gesorteer is.

125
00:09:19,210 --> 00:09:21,560
Vrae oor wat?

126
00:09:21,560 --> 00:09:25,710
>> Hierdie onvermydelik verskyn in die vorms wat jy hoef in te vul wanneer jy die indiening van die pset.

127
00:09:29,010 --> 00:09:32,360
Dit is basies die antwoorde op hierdie.

128
00:09:32,360 --> 00:09:34,230
Okay, so nou kodering probleme.

129
00:09:34,230 --> 00:09:40,140
Ek het reeds uitgestuur via e-pos - Het iemand nie die e-pos kry nie? Okay.

130
00:09:40,140 --> 00:09:46,630
Ek het reeds uitgestuur via e-pos die ruimte wat ons gaan gebruik,

131
00:09:46,630 --> 00:09:52,120
en as jy kliek op my naam - so ek dink ek gaan om aan die onderkant te wees

132
00:09:52,120 --> 00:09:57,170
as gevolg van die agteruit r - maar as jy kliek op my naam wat jy sal sien 2 hersienings.

133
00:09:57,170 --> 00:10:02,650
Hersiening 1 gaan ek reeds die kode in Ruimtes gekopieer en geplak

134
00:10:02,650 --> 00:10:06,900
vir die soektog ding wat jy gaan hê om te implementeer.

135
00:10:06,900 --> 00:10:10,540
En Hersiening 2 die soort ding wat ons implementeer daarna sal wees.

136
00:10:10,540 --> 00:10:15,770
So kan jy kliek op my Hersiening 1 en werk van daar af.

137
00:10:17,350 --> 00:10:22,060
En nou wil ons binêre soektog te implementeer.

138
00:10:22,060 --> 00:10:26,470
>> Is daar iemand wil net 'n pseudokode hoë-vlak verduideliking gee

139
00:10:26,470 --> 00:10:31,440
van wat ons gaan hê om te doen vir die soektog? Ja.

140
00:10:31,440 --> 00:10:36,170
[Student] Jy moet net die middel van die skikking en sien as wat jy op soek na

141
00:10:36,170 --> 00:10:38,650
is minder as of meer as dit.

142
00:10:38,650 --> 00:10:41,080
En as dit is minder, gaan jy na die helfte minder,

143
00:10:41,080 --> 00:10:44,750
en as dit meer is, jy gaan aan die helfte van wat meer en jy dit asseblief herhaal totdat jy net een ding.

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

145
00:10:46,570 --> 00:10:51,320
Let daarop dat ons getalle skikking reeds gesorteer,

146
00:10:51,320 --> 00:10:57,190
en so dit beteken dat ons voordeel kan neem van daardie en ons kon eers,

147
00:10:57,190 --> 00:11:00,390
okay, ek is op soek vir die nommer 50.

148
00:11:00,390 --> 00:11:03,720
Sodat ek kan gaan in die middel.

149
00:11:03,720 --> 00:11:07,380
Middel is moeilik om te definieer wanneer dit is 'n ewe getal van die dinge,

150
00:11:07,380 --> 00:11:10,820
maar laat ons net sê ons altyd sal afgeknot na die middel.

151
00:11:10,820 --> 00:11:14,420
So hier is ons het 8 dinge, sodat die middel sou wees 16.

152
00:11:14,420 --> 00:11:17,330
Ek is op soek na 50, so 50 is groter as 16.

153
00:11:17,330 --> 00:11:21,310
So nou kan ek basies my array behandel as hierdie elemente.

154
00:11:21,310 --> 00:11:23,450
Ek kan weggooi alles vanaf 16 oor.

155
00:11:23,450 --> 00:11:27,440
Nou is my array net hierdie 4 elemente, en ek herhaal.

156
00:11:27,440 --> 00:11:31,910
So dan wil ek die middel weer te vind, wat sal wees 42.

157
00:11:31,910 --> 00:11:34,730
42 is minder as 50, so ek kan weggooi hierdie twee elemente.

158
00:11:34,730 --> 00:11:36,890
Dit is my oorblywende verskeidenheid.

159
00:11:36,890 --> 00:11:38,430
Ek gaan om die middel te weer te vind.

160
00:11:38,430 --> 00:11:42,100
Ek dink 50 was 'n slegte voorbeeld, want ek was altyd weg te gooi dinge aan die linkerkant,

161
00:11:42,100 --> 00:11:48,280
maar deur die dieselfde mate as ek is op soek na iets

162
00:11:48,280 --> 00:11:52,100
en dit is minder as die element ek op die oomblik is op soek na,

163
00:11:52,100 --> 00:11:55,080
dan gaan ek alles weg te gooi na regs.

164
00:11:55,080 --> 00:11:58,150
So nou het ons nodig het om te implementeer.

165
00:11:58,150 --> 00:12:02,310
Let daarop dat ons nodig het om te slaag in grootte.

166
00:12:02,310 --> 00:12:06,730
Ons kan ook nie hoef te hard-kode grootte.

167
00:12:06,730 --> 00:12:11,640
So as ons ontslae raak van daardie # define -

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

169
00:12:21,430 --> 00:12:27,180
Hoe kan ek mooi uit te vind wat die grootte van die getalle verskeidenheid tans?

170
00:12:27,180 --> 00:12:30,950
>> Hoeveel elemente in die getalle verskeidenheid?

171
00:12:30,950 --> 00:12:33,630
[Student] Getalle, tussen hakies, lengte?

172
00:12:33,630 --> 00:12:36,600
[Bowden] Dit beteken nie bestaan ​​in C.

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

174
00:12:38,580 --> 00:12:42,010
Skikkings nie het eienskappe, so daar is geen lengte eiendom van skikkings

175
00:12:42,010 --> 00:12:45,650
wat gee jou net hoe lank dit gebeur om te wees.

176
00:12:48,180 --> 00:12:51,620
[Student] Kyk hoeveel geheue het en verdeel deur hoeveel >> Ja.

177
00:12:51,620 --> 00:12:55,810
So hoe kan ons sien hoeveel geheue het dit? >> [Student] sizeof. >> Ja, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof is die operateur wat gaan om terug te keer die grootte van die getalle skikking.

179
00:13:01,680 --> 00:13:10,060
En wat gaan egter baie heelgetalle is daar keer die grootte van 'n heelgetal

180
00:13:10,060 --> 00:13:14,050
want dit is hoeveel geheue wat dit werklik neem.

181
00:13:14,050 --> 00:13:17,630
So as ek wil hê dat die aantal van die dinge wat in die skikking,

182
00:13:17,630 --> 00:13:20,560
dan gaan ek wil te verdeel deur die grootte van 'n heelgetal.

183
00:13:22,820 --> 00:13:26,010
Okay. So dit laat my in grootte hier.

184
00:13:26,010 --> 00:13:29,430
Hoekom het ek nodig om te slaag in grootte op alle?

185
00:13:29,430 --> 00:13:38,570
Hoekom kan ek nie doen net hier int grootte = sizeof (hooiberg) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Waarom dit nie werk nie?

187
00:13:41,490 --> 00:13:44,470
[Student] Dit is nie 'n globale veranderlike.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Hooi bestaan ​​en ons is wat in getalle as hooiberg,

189
00:13:51,540 --> 00:13:54,700
en dit is 'n soort van 'n voorafskaduwing van wat om te kom. Ja.

190
00:13:54,700 --> 00:14:00,170
[Student] Hooi net is die verwysing na dit, so dit sou terugkeer hoe groot die verwysing is.

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

192
00:14:02,150 --> 00:14:09,000
Ek twyfel in die lesing dat jy die stapel het gesien het nie regtig nie, reg?

193
00:14:09,000 --> 00:14:11,270
Ons het nou net gepraat oor dit.

194
00:14:11,270 --> 00:14:16,090
So die stapel is waar al jou veranderlikes gaan word gestoor.

195
00:14:16,090 --> 00:14:19,960
>> Enige geheue wat vir plaaslike veranderlikes toegeken gaan in die stapel,

196
00:14:19,960 --> 00:14:24,790
en elke funksie kry sy eie ruimte op die stapel, sy eie stapel raam is wat dit genoem word.

197
00:14:24,790 --> 00:14:31,590
So hoof het sy stapel raam, en die binnekant van dit gaan hierdie getalle skikking te bestaan,

198
00:14:31,590 --> 00:14:34,270
en dit gaan van grootte sizeof (getalle) te wees.

199
00:14:34,270 --> 00:14:38,180
Dit gaan om die grootte van getalle gedeel deur die grootte van die elemente te hê,

200
00:14:38,180 --> 00:14:42,010
maar dat alle lewe binne hoof se stapel raam.

201
00:14:42,010 --> 00:14:45,190
Wanneer ons 'n beroep soek, soek kry sy eie stapel raam,

202
00:14:45,190 --> 00:14:48,840
sy eie ruimte al van sy plaaslike veranderlikes te stoor.

203
00:14:48,840 --> 00:14:56,420
Maar hierdie argumente - so hooiberg is nie 'n afskrif van hierdie hele skikking.

204
00:14:56,420 --> 00:15:00,990
Ons slaag nie in die hele verskeidenheid as 'n afskrif in die soektog.

205
00:15:00,990 --> 00:15:04,030
Dit gaan net 'n verwysing na daardie skikking.

206
00:15:04,030 --> 00:15:11,470
So soek kan toegang tot hierdie getalle deur middel van hierdie verwysing.

207
00:15:11,470 --> 00:15:17,100
Dit is nog steeds toegang tot die dinge wat leef binnekant van die hoof se stapel raam,

208
00:15:17,100 --> 00:15:22,990
maar basies, wanneer kry ons verwysings, moet wat binnekort,

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

210
00:15:24,980 --> 00:15:29,400
Pointers is slegs verwysings na dinge, en jy kan gebruik wenke om dinge om toegang te verkry tot

211
00:15:29,400 --> 00:15:32,030
wat in ander dinge stapel rame.

212
00:15:32,030 --> 00:15:37,660
So selfs al getalle plaaslike to main, ons kan nog steeds toegang tot dit deur middel van hierdie wyser.

213
00:15:37,660 --> 00:15:41,770
Maar aangesien dit is net 'n wyser en dit is net 'n verwysing,

214
00:15:41,770 --> 00:15:45,040
sizeof (hooiberg) terugkeer net die grootte van die verwysing self.

215
00:15:45,040 --> 00:15:47,950
Dit kom nie terug nie die grootte van die ding wat dit verwys na.

216
00:15:47,950 --> 00:15:51,110
Dit kom nie terug nie die werklike grootte van getalle.

217
00:15:51,110 --> 00:15:55,660
En so het dit is nie van plan om te werk as ons dit wil.

218
00:15:55,660 --> 00:15:57,320
>> Vrae oor wat?

219
00:15:57,320 --> 00:16:03,250
Pointers gegaan sal word in aansienlik meer gorie detail in die weke om te kom.

220
00:16:06,750 --> 00:16:13,740
En dit is die rede waarom 'n baie van die dinge wat jy sien, die meeste soek dinge of soort dinge,

221
00:16:13,740 --> 00:16:16,990
hulle byna almal nodig om die werklike grootte van die skikking te neem,

222
00:16:16,990 --> 00:16:20,440
want in C, ons het geen idee wat die grootte van die skikking is.

223
00:16:20,440 --> 00:16:22,720
Jy moet met die hand te slaag.

224
00:16:22,720 --> 00:16:27,190
En jy kan met die hand nie slaag in die hele skikking omdat jy net wat in die verwysing

225
00:16:27,190 --> 00:16:30,390
en dit kan nie die grootte van die verwysing.

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

227
00:16:32,300 --> 00:16:38,160
So nou het ons wil uit te voer wat voorheen verduidelik.

228
00:16:38,160 --> 00:16:41,530
Jy kan werk op dit vir 'n minuut,

229
00:16:41,530 --> 00:16:45,250
en jy hoef nie te bekommer oor om alles perfek 100% werk.

230
00:16:45,250 --> 00:16:51,410
Net te skryf aan die helfte pseudokode vir hoe jy dink dit moet werk.

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

232
00:16:53,630 --> 00:16:56,350
Nie nodig om heeltemal klaar is met hierdie nog.

233
00:16:56,350 --> 00:17:02,380
Maar nie almal voel gemaklik met wat hulle het so ver,

234
00:17:02,380 --> 00:17:05,599
soos iets wat ons kan werk met mekaar?

235
00:17:05,599 --> 00:17:09,690
Is daar iemand wil vrywillige werk doen? Of ek sal lukraak kies.

236
00:17:12,680 --> 00:17:18,599
Dit hoef nie te wees reg deur enige maatreël, maar iets wat ons kan verander in 'n werkende toestand.

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

238
00:17:20,720 --> 00:17:27,220
So kan jy die hersiening red deur te kliek op die klein ikoon Stoor.

239
00:17:27,220 --> 00:17:29,950
Jy Ramya, reg? >> [Student] Ja. >> [Bowden] Goed.

240
00:17:29,950 --> 00:17:35,140
So nou kan ek jou hersiening sien en almal kan trek die hersiening.

241
00:17:35,140 --> 00:17:38,600
En hier het ons - Okay.

242
00:17:38,600 --> 00:17:43,160
So Ramya het met die rekursiewe oplossing, en dit is beslis 'n geldige oplossing.

243
00:17:43,160 --> 00:17:44,970
Daar is twee maniere waarop jy hierdie probleem kan doen.

244
00:17:44,970 --> 00:17:48,060
Jy kan dit doen iteratief of rekursief.

245
00:17:48,060 --> 00:17:53,860
Die meeste probleme wat jy teëkom wat kan rekursief gedoen word, kan ook iteratief gedoen word.

246
00:17:53,860 --> 00:17:58,510
So hier is ons het dit gedoen rekursief.

247
00:17:58,510 --> 00:18:03,730
>> Iemand wil te definieer wat dit beteken om 'n funksie te maak rekursiewe?

248
00:18:07,210 --> 00:18:08,920
[Student] Wanneer jy 'n funksie noem homself

249
00:18:08,920 --> 00:18:13,470
en dan bel self totdat dit kom uit met ware en ware. >> Ja.

250
00:18:13,470 --> 00:18:17,680
'N rekursiewe funksie is net 'n funksie wat self noem.

251
00:18:17,680 --> 00:18:24,140
Daar is drie groot dinge wat 'n rekursiewe funksie moet.

252
00:18:24,140 --> 00:18:27,310
Die eerste is natuurlik, dit self noem.

253
00:18:27,310 --> 00:18:29,650
Die tweede is die basis-geval.

254
00:18:29,650 --> 00:18:33,390
So op 'n sekere punt van die funksie moet om te stop roeping self,

255
00:18:33,390 --> 00:18:35,610
en dit is wat die basis-geval is.

256
00:18:35,610 --> 00:18:43,860
So hier is ons weet dat ons moet ophou, moet ons in ons soektog

257
00:18:43,860 --> 00:18:48,150
wanneer begin gelyk aan einde en ons sal gaan oor wat dit beteken.

258
00:18:48,150 --> 00:18:52,130
Maar uiteindelik, die laaste ding wat belangrik is vir rekursiewe funksies:

259
00:18:52,130 --> 00:18:59,250
die funksies moet op een of ander manier benader die basis-geval.

260
00:18:59,250 --> 00:19:04,140
Hou as jy eintlik nie enigiets afhangende van wanneer jy die tweede rekursiewe oproep,

261
00:19:04,140 --> 00:19:07,880
as jy net letterlik die roeping van die funksie weer met dieselfde argumente

262
00:19:07,880 --> 00:19:10,130
en geen globale veranderlikes het verander of enigiets nie,

263
00:19:10,130 --> 00:19:14,430
jy sal nooit die basis bereik geval, in welke geval dit is erg.

264
00:19:14,430 --> 00:19:17,950
Dit sal 'n oneindige rekursie en 'n stack overflow wees.

265
00:19:17,950 --> 00:19:24,330
Maar hier sien ons dat die update gebeur aangesien ons opdatering + einde / 2 begin,

266
00:19:24,330 --> 00:19:28,180
ons die opdatering van die einde argument hier, ons begin argument opdatering hier.

267
00:19:28,180 --> 00:19:32,860
So ons in alle rekursiewe oproepe word opgedateer iets. Okay.

268
00:19:32,860 --> 00:19:38,110
Wil jy ons om te loop deur jou oplossing? >> Sure.

269
00:19:38,110 --> 00:19:44,270
Ek gebruik SearchHelp so dat elke keer as ek maak hierdie funksie oproep

270
00:19:44,270 --> 00:19:47,910
Ek het die begin van waar ek kyk in die skikking en die einde

271
00:19:47,910 --> 00:19:49,380
van waar ek is op soek na die skikking.

272
00:19:49,380 --> 00:19:55,330
>> By elke stap waar dit sê dit is die middelste element, wat die einde van die begin + / 2,

273
00:19:55,330 --> 00:19:58,850
is dit gelyk aan die wat ons soek?

274
00:19:58,850 --> 00:20:04,650
En as dit is, dan het ons gevind dat dit, en ek dink dit kry geslaag om die vlakke van rekursie.

275
00:20:04,650 --> 00:20:12,540
En as dit is nie waar nie, dan moet ons kyk of daardie middelste waarde van die skikking is te groot,

276
00:20:12,540 --> 00:20:19,320
in welke geval ons kyk na die linker helfte van die skikking deur te gaan van die begin tot die middel-indeks.

277
00:20:19,320 --> 00:20:22,710
En anders kan ons doen die einde 1/2.

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

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

280
00:20:27,730 --> 00:20:36,640
Okay, so 'n paar dinge, en dit is eintlik 'n baie hoë vlak ding

281
00:20:36,640 --> 00:20:41,270
dat jy sal nooit nodig om vir hierdie kursus te weet, maar dit is waar.

282
00:20:41,270 --> 00:20:46,080
Rekursiewe funksies, jy hoor altyd dat hulle 'n slegte deal

283
00:20:46,080 --> 00:20:51,160
want as jy rekursief noem jouself te veel keer, kry jy stack overflow

284
00:20:51,160 --> 00:20:54,990
want soos ek gesê het, elke funksie kry sy eie stapel raam.

285
00:20:54,990 --> 00:20:59,500
So elke oproep van die rekursiewe funksie kry sy eie stapel raam.

286
00:20:59,500 --> 00:21:04,140
So as jy 1000 rekursiewe oproepe maak, kry jy 1000 stapel rame,

287
00:21:04,140 --> 00:21:08,390
en vinnig lei tot te veel stapel rame en dinge net breek.

288
00:21:08,390 --> 00:21:13,480
So dit is waarom rekursiewe funksies is oor die algemeen sleg.

289
00:21:13,480 --> 00:21:19,370
Maar daar is 'n mooi subset van rekursiewe funksies genoem stert-rekursiewe funksies,

290
00:21:19,370 --> 00:21:26,120
en dit gebeur met 'n voorbeeld van een waar as die samesteller kennisgewings

291
00:21:26,120 --> 00:21:29,920
en dit sal, dink ek - kletteren as jy slaag die O2 vlag

292
00:21:29,920 --> 00:21:33,250
dan sal dit sien dit is 'n stert rekursiewe en maak goeie dinge.

293
00:21:33,250 --> 00:21:40,050
>> Dit sal hergebruik in dieselfde stapel raam oor en oor weer vir elke rekursiewe oproep.

294
00:21:40,050 --> 00:21:47,010
En so aangesien jy met behulp van dieselfde stapel raam, het jy nie hoef te bekommer oor

295
00:21:47,010 --> 00:21:51,690
ooit stapel oorloop, en op dieselfde tyd, soos jy sê,

296
00:21:51,690 --> 00:21:56,380
waar wanneer jy terugkeer waar is, dan is dit om terug te keer al van hierdie stapel rame

297
00:21:56,380 --> 00:22:01,740
en die 10de oproep tot SearchHelp het om terug te keer na die 9de, het om terug te keer na die 8ste.

298
00:22:01,740 --> 00:22:05,360
Sodat nie nodig om te gebeur wanneer funksies stert rekursiewe.

299
00:22:05,360 --> 00:22:13,740
En wat maak hierdie funksie stert rekursiewe kennis dat vir enige gegewe oproep tot searchHelp

300
00:22:13,740 --> 00:22:18,470
die rekursiewe oproep wat dit maak wat dit terugkeer.

301
00:22:18,470 --> 00:22:25,290
So in die eerste oproep te SearchHelp ons óf onmiddellik return false,

302
00:22:25,290 --> 00:22:29,590
onmiddellik return true, of ons maak 'n rekursiewe oproep SearchHelp

303
00:22:29,590 --> 00:22:33,810
waar wat ons terugkeer, is wat dit oproep terugkeer.

304
00:22:33,810 --> 00:22:51,560
En ons kan dit nie doen as ons iets gedoen het soos int x = SearchHelp, terugkeer x * 2,

305
00:22:51,560 --> 00:22:55,440
net 'n paar random verandering.

306
00:22:55,440 --> 00:23:01,470
>> So nou hierdie rekursiewe oproep, hierdie int x = SearchHelp rekursiewe oproep,

307
00:23:01,470 --> 00:23:05,740
is nie langer stert rekursiewe omdat dit eintlik nie om terug te keer

308
00:23:05,740 --> 00:23:10,400
terug na 'n vorige stapel raam so dat vorige oproep na die funksie

309
00:23:10,400 --> 00:23:13,040
kan dan iets te doen met die terugkeer waarde.

310
00:23:13,040 --> 00:23:22,190
Dit is dus nie stert rekursiewe, maar wat ons gehad het voordat mooi stert rekursiewe. Ja.

311
00:23:22,190 --> 00:23:27,000
[Student] Moet nie die tweede basis geval eerste nagegaan word

312
00:23:27,000 --> 00:23:30,640
want daar kan 'n situasie wees waar wanneer jy dit die argument

313
00:23:30,640 --> 00:23:35,770
jy begin = einde, maar dit is die naald waarde.

314
00:23:35,770 --> 00:23:47,310
Die vraag is wat ons kan nie uitgevoer word nie in die geval waar die einde is die naald waarde

315
00:23:47,310 --> 00:23:52,000
of = einde begin, toepaslik, begin = einde

316
00:23:52,000 --> 00:23:59,480
en jy het eintlik nie daardie spesifieke waarde nagegaan nie,

317
00:23:59,480 --> 00:24:03,910
+ einde / 2 begin is net gaan om dieselfde waarde te wees.

318
00:24:03,910 --> 00:24:07,890
Maar ons het reeds teruggekeer vals en ons nooit werklik die waarde nagegaan.

319
00:24:07,890 --> 00:24:14,240
Dus, op die heel minste, in die eerste oproep, indien grootte is 0, dan het ons wil om terug te keer vals.

320
00:24:14,240 --> 00:24:17,710
Maar as die grootte is 1, dan begin is nie van plan om op gelyke einde,

321
00:24:17,710 --> 00:24:19,820
en ons sal ten minste check die een element.

322
00:24:19,820 --> 00:24:26,750
Maar ek dink jy is reg in die sin dat ons kan eindig in 'n geval waar + einde / 2 begin,

323
00:24:26,750 --> 00:24:31,190
begin eindig die dieselfde as die einde van die begin + / 2,

324
00:24:31,190 --> 00:24:35,350
maar ons het nooit eintlik daardie element nagegaan.

325
00:24:35,350 --> 00:24:44,740
>> So as ons eers die middelste element die waarde wat ons is op soek na,

326
00:24:44,740 --> 00:24:47,110
dan kan ons dadelik terug waar.

327
00:24:47,110 --> 00:24:50,740
Anders as hulle gelyk is, dan is daar geen punt in die voortsetting van

328
00:24:50,740 --> 00:24:58,440
aangesien ons net gaan om te werk aan 'n geval waar ons is op 'n enkel-element skikking.

329
00:24:58,440 --> 00:25:01,110
As dit enkele element is nie die een wat ons soek,

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

331
00:25:03,530 --> 00:25:08,900
[Student] Die ding is dat sedert die grootte is eintlik groter is as die aantal elemente in die skikking,

332
00:25:08,900 --> 00:25:13,070
daar is reeds 'n offset - >> So sal grootte -

333
00:25:13,070 --> 00:25:19,380
[Student] Sê indien die skikking was grootte 0, dan sal die SearchHelp eintlik gaan hooiberg van 0

334
00:25:19,380 --> 00:25:21,490
op die eerste oproep.

335
00:25:21,490 --> 00:25:25,300
Die skikking het grootte 0, sodat die 0 - >> Ja.

336
00:25:25,300 --> 00:25:30,750
Daar is 'n ander ding wat dit dalk goed wees. Kom ons dink.

337
00:25:30,750 --> 00:25:40,120
So as die skikking het 10 elemente en die middelste een wat ons gaan om te kyk indeks 5,

338
00:25:40,120 --> 00:25:45,700
sodat ons nagaan 5, en laat ons sê dat die waarde is minder.

339
00:25:45,700 --> 00:25:50,720
So ons gooi alles weg van 5 af.

340
00:25:50,720 --> 00:25:54,030
So begin + einde / 2 gaan ons nuwe einde wees nie,

341
00:25:54,030 --> 00:25:57,450
so ja, dit is altyd gaan om te bly buite die einde van die skikking.

342
00:25:57,450 --> 00:26:03,570
As dit is 'n geval as dit was ewe of onewe is, dan sal ons gaan, sê, 4,

343
00:26:03,570 --> 00:26:05,770
maar ons is nog steeds weg te gooi -

344
00:26:05,770 --> 00:26:13,500
So ja, die einde is altyd iets te wees as die werklike einde van die skikking.

345
00:26:13,500 --> 00:26:18,350
Sodat die elemente wat ons fokus op die einde is altyd iets aan die een na.

346
00:26:18,350 --> 00:26:24,270
En so, as begin doen ooit gelyke einde, ons is in 'n verskeidenheid van grootte 0.

347
00:26:24,270 --> 00:26:35,600
>> Die ander ding wat ek kon dink is dat ons begin word opgedateer word begin + einde / 2,

348
00:26:35,600 --> 00:26:44,020
so is dit die geval dat ek die moeilikheid is met, waar begin + einde / 2

349
00:26:44,020 --> 00:26:46,820
is die element wat ons nagaan.

350
00:26:46,820 --> 00:26:58,150
Kom ons sê ons het hierdie 10-element array. Wat ook al.

351
00:26:58,150 --> 00:27:03,250
So begin + einde / 2 gaan om iets soos hierdie een te wees,

352
00:27:03,250 --> 00:27:07,060
en as dit nie is die waarde, sê ons wil werk.

353
00:27:07,060 --> 00:27:10,060
Die waarde is groter, so ons wil om te kyk na die helfte van die skikking.

354
00:27:10,060 --> 00:27:15,910
So, hoe ons begin jy die opdatering van ons opdatering van begin tot nou toe word hierdie element.

355
00:27:15,910 --> 00:27:23,790
Maar dit kan nog steeds werk, of op die heel minste, kan jy doen begin + einde / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Student] Jy hoef nie te wees nie + einde begin [onhoorbaar] >> Ja.

357
00:27:27,850 --> 00:27:33,240
Ons het reeds hierdie element nagegaan en weet dit is nie die een wat ons soek.

358
00:27:33,240 --> 00:27:36,800
So ons hoef nie begin te werk om hierdie element te wees.

359
00:27:36,800 --> 00:27:39,560
Ons kan nie net slaan dit en werk begin om hierdie element te wees.

360
00:27:39,560 --> 00:27:46,060
En is daar ooit 'n geval, laat ons sê, dat hierdie einde,

361
00:27:46,060 --> 00:27:53,140
so dan begin sou wees, begin + einde / 2 sou wees,

362
00:27:53,140 --> 00:28:00,580
+ einde begin - Ja, ek dink dit kan eindig in oneindige rekursie.

363
00:28:00,580 --> 00:28:12,690
Kom ons sê dit is net 'n verskeidenheid van grootte 2 of 'n verskeidenheid van grootte 1. Ek dink dit sal werk.

364
00:28:12,690 --> 00:28:19,490
So op die oomblik, begin is dat die element en die einde is 1 verder as dit.

365
00:28:19,490 --> 00:28:24,110
So is die element dat ons gaan om te kyk, is hierdie een,

366
00:28:24,110 --> 00:28:29,400
en dan wanneer ons begin werk, is ons opdatering van begin tot 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
wat gaan ons weer begin om hierdie element te beëindig.

368
00:28:33,160 --> 00:28:36,210
>> So ons is die kontrolering van dieselfde element oor en oor weer.

369
00:28:36,210 --> 00:28:43,310
So, dit is die geval waar elke rekursiewe oproep moet eintlik iets werk.

370
00:28:43,310 --> 00:28:48,370
So moet ons die einde van die begin + / 2 + 1, of anders om te doen, daar is 'n saak

371
00:28:48,370 --> 00:28:50,710
waar ons eintlik nie die opdatering begin.

372
00:28:50,710 --> 00:28:53,820
Almal sien dat?

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

374
00:28:56,310 --> 00:29:03,860
Is daar iemand vrae oor hierdie oplossing of meer kommentaar?

375
00:29:05,220 --> 00:29:10,280
Okay. Is daar iemand 'n het iteratiewe oplossing wat ons almal kan kyk?

376
00:29:17,400 --> 00:29:20,940
Het ons almal dit doen rekursief?

377
00:29:20,940 --> 00:29:25,950
Of ek ook dink as jy oopgemaak hare, dan is jy dalk oorskryf jou vorige een.

378
00:29:25,950 --> 00:29:28,810
Is dit outomaties te stoor? Ek is nie positief nie.

379
00:29:35,090 --> 00:29:39,130
Is daar iemand iteratiewe het?

380
00:29:39,130 --> 00:29:42,430
Ons kan wandel deur dit saam indien nie.

381
00:29:46,080 --> 00:29:48,100
Die idee is om dieselfde te wees.

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

383
00:30:02,830 --> 00:30:07,140
Ons gaan om te wil basies dieselfde idee

384
00:30:07,140 --> 00:30:16,530
waar ons wil die spoor van die die nuwe einde van die skikking en die nuwe begin van die skikking te hou

385
00:30:16,530 --> 00:30:18,510
en doen dit oor en oor.

386
00:30:18,510 --> 00:30:22,430
En as wat ons dop as die begin en die einde ooit sny,

387
00:30:22,430 --> 00:30:29,020
dan het ons nie dit vind en ons kan terugkeer vals.

388
00:30:29,020 --> 00:30:37,540
So, hoe doen ek dit? Enigeen het voorstelle of-kode vir my om te trek?

389
00:30:42,190 --> 00:30:47,450
[Student] Doen 'n while lus. >> Ja.

390
00:30:47,450 --> 00:30:49,450
Jy gaan om te wil 'n lus om te doen.

391
00:30:49,450 --> 00:30:51,830
>> Het jy 'n kode wat ek kon trek, of wat is jy gaan om voor te stel?

392
00:30:51,830 --> 00:30:56,340
[Student] Ek dink nie so nie. >> Alle regte. Dit maak dinge makliker. Wat is jou naam?

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

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

395
00:31:04,190 --> 00:31:13,200
Laag is wat ons geroep het begin voor.

396
00:31:13,200 --> 00:31:17,080
UP is nie heeltemal wat ons geroep einde voor.

397
00:31:17,080 --> 00:31:22,750
Eintlik, die einde is nou in die skikking. Dit is 'n element wat ons in ag moet neem.

398
00:31:22,750 --> 00:31:26,890
So laag is 0, is die grootte van die skikking - 1,

399
00:31:26,890 --> 00:31:34,780
en nou is ons herhaling, en ons monitor -

400
00:31:34,780 --> 00:31:37,340
Ek dink jy kan wandel deur dit.

401
00:31:37,340 --> 00:31:41,420
Wat was jou denke deur middel van hierdie? Loop ons deur jou kode.

402
00:31:41,420 --> 00:31:49,940
[Student] Sure. Kyk na die hooiberg waarde in die middel en dit vergelyk met die naald.

403
00:31:49,940 --> 00:31:58,520
So as dit is groter as die naald, dan is jy om - oh, eintlik, wat agteruit wees.

404
00:31:58,520 --> 00:32:05,180
Jy gaan wil die regter helfte weg te gooi, en so ja, wat die pad moet wees.

405
00:32:05,180 --> 00:32:08,830
[Bowden] So dit moet minder wees? Is dit wat jy sê? >> [Student] Ja.

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

407
00:32:10,390 --> 00:32:15,700
So as wat ons is op soek na is kleiner as wat ons wil hê,

408
00:32:15,700 --> 00:32:19,410
dan ja, ons wil die linker helfte weg te gooi,

409
00:32:19,410 --> 00:32:22,210
wat beteken dat ons alles wat ons oorweeg word opgedateer

410
00:32:22,210 --> 00:32:26,610
deur die beweging van laag na die reg van die skikking.

411
00:32:26,610 --> 00:32:30,130
Dit lyk goed.

412
00:32:30,130 --> 00:32:34,550
Ek dink dit het dieselfde probleem wat ons het op die vorige een,

413
00:32:34,550 --> 00:32:49,760
waar as laag is 0 en is 1, dan lae + up / 2 gaan te stel om dieselfde ding weer.

414
00:32:49,760 --> 00:32:53,860
>> En selfs as dit nie die geval is nie, is dit steeds meer doeltreffende op die heel minste

415
00:32:53,860 --> 00:32:57,630
om net weggooi die element wat ons net kyk wat ons weet verkeerd is.

416
00:32:57,630 --> 00:33:03,240
So laag + up / 2 + 1 - >> [student] Dit moet die ander kant wees.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Of moet wees - 1 en die ander een moet wees + 1.

418
00:33:05,900 --> 00:33:09,580
[Student] En daar moet 'n dubbel gelykaanteken. >> [Bowden] Ja.

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

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

421
00:33:15,910 --> 00:33:21,280
En ten slotte, nou dat ons hierdie + 1 - 1 ding,

422
00:33:21,280 --> 00:33:31,520
is dit - is dit dalk nie - is dit ooit moontlik vir lae om te eindig met 'n waarde groter as up?

423
00:33:35,710 --> 00:33:40,320
Ek dink die enigste manier wat kan gebeur - is dit moontlik? >> [Student] Ek weet nie.

424
00:33:40,320 --> 00:33:45,220
Maar as dit afgeknotte en dan kry minus 1 en dan - >> Ja.

425
00:33:45,220 --> 00:33:47,480
[Student] Dit sou moontlik deurmekaar raak.

426
00:33:49,700 --> 00:33:53,940
Ek dink dit moet goed wees net omdat

427
00:33:53,940 --> 00:33:58,800
want dit laer aan die einde wat hulle wil hê om gelyk te wees, dink ek.

428
00:33:58,800 --> 00:34:03,070
Maar as hulle gelyk is, dan sou ons nie gedoen het die while lus om te begin met

429
00:34:03,070 --> 00:34:06,670
en ons sou net teruggekeer het om die waarde. So ek dink ons ​​is nou goed.

430
00:34:06,670 --> 00:34:11,530
Let daarop dat selfs al is hierdie probleem is nie langer rekursiewe,

431
00:34:11,530 --> 00:34:17,400
dieselfde soort idees is van toepassing waar ons kan sien hoe dit so maklik leen hom

432
00:34:17,400 --> 00:34:23,659
tot 'n rekursiewe oplossing deur die feit dat ons net die opdatering van die indekse oor en oor weer,

433
00:34:23,659 --> 00:34:29,960
maak ons ​​die probleem kleiner en kleiner, is ons fokus op 'n subset van die skikking.

434
00:34:29,960 --> 00:34:40,860
[Student] As laag is 0 en 1 is, sou hulle albei 0 + 1/2, wat sal gaan na 0,

435
00:34:40,860 --> 00:34:44,429
en dan sou 'n mens + 1, sou 'n mens te wees - 1.

436
00:34:47,000 --> 00:34:50,870
[Student] Waar is ons nagaan gelykheid?

437
00:34:50,870 --> 00:34:55,100
Graag as die middelste een is eintlik naald?

438
00:34:55,100 --> 00:34:58,590
Ons ervaar tans nie om dit te doen? Oh!

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

440
00:35:05,340 --> 00:35:13,740
Ja. Ons kan nie net doen die toets hier onder omdat laat ons sê die eerste middel -

441
00:35:13,740 --> 00:35:16,430
[Student] Dit is eintlik nie weggooi nie die gebonde.

442
00:35:16,430 --> 00:35:20,220
So as jy weggooi gebonde, moet jy dit die eerste of wat ookal gaan.

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

444
00:35:23,350 --> 00:35:29,650
So nou het ons die een wat ons tans kyk na weggegooi,

445
00:35:29,650 --> 00:35:33,260
wat beteken dat ons moet nou ook

446
00:35:33,260 --> 00:35:44,810
if (hooiberg [(lae + up) / 2] == naald), dan kan ons terug waar.

447
00:35:44,810 --> 00:35:52,070
En of ek anders of net as dit beteken letterlik die dieselfde ding

448
00:35:52,070 --> 00:35:57,110
want dit sou teruggekeer het waar.

449
00:35:57,110 --> 00:36:01,450
So ek sal anders sit as nie, maar dit maak nie saak.

450
00:36:01,450 --> 00:36:10,440
>> So anders as hierdie, anders, en dit is 'n algemene ding wat ek doen

451
00:36:10,440 --> 00:36:14,340
waar selfs al is dit die geval waar alles is goed hier,

452
00:36:14,340 --> 00:36:22,780
soos lae kan nooit groter wees as op, dit is nie die moeite werd redenasie oor die vraag of dit waar is.

453
00:36:22,780 --> 00:36:28,010
So jy kan net sowel sê terwyl lae is minder as of gelyk aan

454
00:36:28,010 --> 00:36:30,720
of terwyl lae is minder as

455
00:36:30,720 --> 00:36:35,300
so as wat hulle ooit gelyk of lae gebeur om te slaag,

456
00:36:35,300 --> 00:36:40,130
dan kan ons breek uit van die lus.

457
00:36:41,410 --> 00:36:44,630
Vrae, kommentaar?

458
00:36:47,080 --> 00:36:49,270
Okay. Dit lyk goed.

459
00:36:49,270 --> 00:36:52,230
Nou wil ons soort te doen.

460
00:36:52,230 --> 00:37:04,030
As ons gaan na my tweede hersiening, sien ons hierdie getalle,

461
00:37:04,030 --> 00:37:07,550
maar nou is hulle nie meer in gesorteer einde.

462
00:37:07,550 --> 00:37:12,840
En ons wil soort uit te voer met behulp van 'n algoritme in O van n log n.

463
00:37:12,840 --> 00:37:17,240
So watter algoritme dink jy moet ons hier te implementeer? >> [Student] Merge soort.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Ja. Merge soort is O (n log n), so dit is wat ons gaan doen.

465
00:37:23,810 --> 00:37:26,680
En die probleem is redelik soortgelyk gaan wees,

466
00:37:26,680 --> 00:37:31,920
waar dit leen homself maklik tot 'n rekursiewe oplossing.

467
00:37:31,920 --> 00:37:35,580
Ons kan ook kom met 'n iteratiewe oplossing as ons wil,

468
00:37:35,580 --> 00:37:42,540
maar rekursie sal makliker wees om hier en ons moet doen rekursie.

469
00:37:45,120 --> 00:37:49,530
Ek dink ons ​​sal wandel deur merge soort,

470
00:37:49,530 --> 00:37:54,280
alhoewel daar 'n pragtige video op merge soort reeds. [Lag]

471
00:37:54,280 --> 00:37:59,780
So saamsmelt soort daar is - ek mors so baie van hierdie vraestel.

472
00:37:59,780 --> 00:38:02,080
O, daar is net een links.

473
00:38:02,080 --> 00:38:03,630
So saam te smelt.

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

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

476
00:38:29,910 --> 00:38:33,460
Merge neem twee afsonderlike skikkings.

477
00:38:33,460 --> 00:38:36,780
Individueel dié twee skikkings is albei gesorteer.

478
00:38:36,780 --> 00:38:40,970
So hierdie skikking, 1, 3, 5, gesorteer. Hierdie skikking, 0, 2, 4, gesorteer.

479
00:38:40,970 --> 00:38:46,710
Nou wat merge moet doen is kombineer hulle in 'n skikking wat op sigself gesorteer.

480
00:38:46,710 --> 00:38:57,130
Daarom wil ons 'n verskeidenheid van grootte 6 wat gaan om hierdie elemente te binnekant van dit

481
00:38:57,130 --> 00:38:59,390
gesorteer einde.

482
00:38:59,390 --> 00:39:03,390
>> En so sal ons kan neem voordeel van die feit dat hierdie twee skikkings word gesorteer

483
00:39:03,390 --> 00:39:06,800
om dit te doen in lineêre tyd,

484
00:39:06,800 --> 00:39:13,510
lineêre tyd betekenis as hierdie verskeidenheid is grootte x en hierdie grootte y,

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

486
00:39:20,970 --> 00:39:23,150
So voorstelle.

487
00:39:23,150 --> 00:39:26,030
[Student] Kan ons begin van die linkerkant?

488
00:39:26,030 --> 00:39:30,150
Sodat jy die 0 eers sit en dan die 1 sit en dan is jy hier by die 2.

489
00:39:30,150 --> 00:39:33,320
So dit is soort van soos jy het 'n blad wat na regs beweeg. >> [Bowden] Ja.

490
00:39:33,320 --> 00:39:41,070
Vir beide van hierdie skikkings as ons net fokus op die linker element.

491
00:39:41,070 --> 00:39:43,530
Omdat beide skikkings word gesorteer, ons weet dat hierdie 2 elemente

492
00:39:43,530 --> 00:39:46,920
is die kleinste elemente in óf skikking.

493
00:39:46,920 --> 00:39:53,500
So dit beteken dat 1 van die 2 elemente moet die kleinste element in ons saamgesmelte skikking.

494
00:39:53,500 --> 00:39:58,190
Dit gebeur net so dat die kleinste is die een aan die regterkant van hierdie tyd.

495
00:39:58,190 --> 00:40:02,580
So neem ons 0, plaas dit op die linkerkant, want 0 is minder as 1,

496
00:40:02,580 --> 00:40:08,210
so neem 0, plaas dit in ons eerste posisie, en dan ons hierdie

497
00:40:08,210 --> 00:40:12,070
nou fokus op die eerste element.

498
00:40:12,070 --> 00:40:14,570
En nou is ons herhaal.

499
00:40:14,570 --> 00:40:20,670
So nou het ons vergelyk 2 en 1. 1 is kleiner, dus sal ons voeg 1.

500
00:40:20,670 --> 00:40:25,300
Ons werk hierdie wyser om te verwys na hierdie man.

501
00:40:25,300 --> 00:40:33,160
Nou het ons dit weer doen, so 2. Dit sal werk, vergelyk hierdie 2, 3.

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

503
00:40:37,770 --> 00:40:42,110
So dit is merge.

504
00:40:42,110 --> 00:40:49,010
>> Dit moet redelik voor die hand liggend dat dit is 'n lineêre tyd want ons gaan net weer oor elke element.

505
00:40:49,010 --> 00:40:55,980
En dit is die grootste stap na die implementering van merge soort dit doen.

506
00:40:55,980 --> 00:40:59,330
En dit is nie so moeilik nie.

507
00:40:59,330 --> 00:41:15,020
'N paar dinge om oor bekommerd te wees nie, is Kom ons sê ons 1, 2, 3, 4, 5, 6 is die samesmelting.

508
00:41:15,020 --> 00:41:30,930
In hierdie geval het ons beland in die scenario waar hierdie een gaan kleiner wees,

509
00:41:30,930 --> 00:41:36,160
dan werk ons ​​hierdie pointer, hierdie een gaan om kleiner te wees, werk,

510
00:41:36,160 --> 00:41:41,280
hierdie een is kleiner, en nou het jy om te erken

511
00:41:41,280 --> 00:41:44,220
wanneer jy eintlik het hardloop uit van die elemente met mekaar te vergelyk.

512
00:41:44,220 --> 00:41:49,400
Aangesien ons reeds gebruik om hierdie hele skikking,

513
00:41:49,400 --> 00:41:55,190
alles in die skikking is nou net hier ingevoeg in.

514
00:41:55,190 --> 00:42:02,040
So as ons ooit hardloop in die punt waar een van ons skikkings reeds heeltemal saamgesmelt,

515
00:42:02,040 --> 00:42:06,510
dan het ons net al die elemente van die ander skikking en plaas dit in die einde van die skikking.

516
00:42:06,510 --> 00:42:13,630
Sodat ons kan voeg net 4, 5, 6. Okay.

517
00:42:13,630 --> 00:42:18,070
Dit is een ding om te kyk uit vir.

518
00:42:22,080 --> 00:42:26,120
Die uitvoering van die stap 1 moet wees.

519
00:42:26,120 --> 00:42:32,600
Merge dan sorteer gebaseer op die, dit is 2 stappe, 2 dom stappe.

520
00:42:38,800 --> 00:42:42,090
Kom ons gee hierdie verskeidenheid.

521
00:42:57,920 --> 00:43:05,680
So saamsmelt soort, stap 1 is om die skikking te rekursief te breek in twee helftes.

522
00:43:05,680 --> 00:43:09,350
Hierdie skikking so verdeel in twee helftes.

523
00:43:09,350 --> 00:43:22,920
Ons het nou 4, 15, 16, 50 en 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
En nou het ons doen dit weer en ons verdeel in twee helftes.

525
00:43:25,800 --> 00:43:27,530
Ek sal doen dit net op hierdie kant.

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

527
00:43:34,790 --> 00:43:37,440
Ons sal dieselfde ding doen hier.

528
00:43:37,440 --> 00:43:40,340
En nou het ons verdeel dit weer in die helfte.

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

530
00:43:51,080 --> 00:43:53,170
So dit is ons basis geval.

531
00:43:53,170 --> 00:44:00,540
Sodra die skikkings van grootte 1, dan moet ons ophou met die splitsing in twee helftes.

532
00:44:00,540 --> 00:44:03,190
>> Wat doen ons nou met hierdie?

533
00:44:03,190 --> 00:44:15,730
Ons eindig dit ook in 8, 23, 42, en 108 sal breek.

534
00:44:15,730 --> 00:44:24,000
So nou dat ons op hierdie punt, nou stap twee van merge soort net samesmelting pare aan die lyste.

535
00:44:24,000 --> 00:44:27,610
So ons wil dit om saam te smelt. Ons roep saam te smelt.

536
00:44:27,610 --> 00:44:31,410
Ons weet merge hierdie in gesorteer orde sal terugkeer.

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

538
00:44:33,920 --> 00:44:41,440
Nou wil ons dit om saam te smelt, en dit sal 'n lys met dié in gesorteer orde terugkeer,

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

540
00:44:44,160 --> 00:44:57,380
Ons saamsmelt diegene - Ek kan nie skryf nie - 8, 23 en 42, 108.

541
00:44:57,380 --> 00:45:02,890
So ons het saamgesmelte pare weer.

542
00:45:02,890 --> 00:45:05,140
Nou het ons net weer saam te smelt.

543
00:45:05,140 --> 00:45:10,130
Let daarop dat elk van hierdie lyste word gesorteer op sigself,

544
00:45:10,130 --> 00:45:15,220
en dan kan ons net saamsmelt hierdie lyste om 'n lys te kry van grootte 4 wat is gesorteer

545
00:45:15,220 --> 00:45:19,990
en hierdie twee lyste saam te smelt om 'n lys te kry van grootte 4 wat is gesorteer.

546
00:45:19,990 --> 00:45:25,710
En laastens, kan ons saam te smelt die twee lyste van grootte 4 'n lys te kry van grootte 8 wat is gesorteer.

547
00:45:25,710 --> 00:45:34,030
So om te sien dat dit is 'n algehele n log n, het ons reeds gesien dat merge is lineêre,

548
00:45:34,030 --> 00:45:40,390
sodat wanneer ons te doen het met die samesmelting hierdie, so soos die totale koste van die merge

549
00:45:40,390 --> 00:45:43,410
vir hierdie twee lyste is net 2 omdat -

550
00:45:43,410 --> 00:45:49,610
Of goed, dit is O van n, maar n hier is net hierdie 2 elemente, so dit is 2.

551
00:45:49,610 --> 00:45:52,850
En dit 2 sal wees 2 en die 2 sal wees 2 en die 2 sal wees 2,

552
00:45:52,850 --> 00:45:58,820
so oor al die smelt wat ons nodig het om te doen, het ons uiteindelik doen n.

553
00:45:58,820 --> 00:46:03,210
Soos 2 + 2 + 2 + 2 is 8, wat 'n

554
00:46:03,210 --> 00:46:08,060
sodat die koste van die samesmelting in hierdie stel is n.

555
00:46:08,060 --> 00:46:10,810
En dan dieselfde ding hier.

556
00:46:10,810 --> 00:46:16,980
Ons sal hulle saamsmelt 2, dan is hierdie 2 en individueel hierdie kombinering sal vier operasies,

557
00:46:16,980 --> 00:46:23,610
hierdie merge sal vier operasies, maar weer, tussen al hierdie,

558
00:46:23,610 --> 00:46:29,030
ons uiteindelik samesmelting n totale dinge, en so hierdie stap neem n.

559
00:46:29,030 --> 00:46:33,670
En so elke vlak neem n elemente saamgevoeg.

560
00:46:33,670 --> 00:46:36,110
>> En hoeveel vlakke is daar?

561
00:46:36,110 --> 00:46:40,160
Op elke vlak, ons verskeidenheid groei deur die grootte 2.

562
00:46:40,160 --> 00:46:44,590
Hier om ons skikkings van grootte 1, hier is hulle van grootte 2, hulle is hier van grootte 4,

563
00:46:44,590 --> 00:46:46,470
en uiteindelik, hulle is van grootte 8.

564
00:46:46,470 --> 00:46:56,450
So aangesien dit verdubbel, is daar 'n totaal van log n van hierdie vlakke gaan wees.

565
00:46:56,450 --> 00:47:02,090
So met die log n vlakke, elke individuele vlak wat 'n totale bedrywighede,

566
00:47:02,090 --> 00:47:05,720
ons kry 'n log n algoritme.

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

568
00:47:08,940 --> 00:47:13,320
Het mense reeds vordering gemaak oor hoe om dit te implementeer?

569
00:47:13,320 --> 00:47:18,260
Is iemand reeds in 'n staat waar ek kan net trek hulle kode?

570
00:47:20,320 --> 00:47:22,260
Ek kan gee 'n minuut.

571
00:47:24,770 --> 00:47:27,470
Hierdie een gaan meer.

572
00:47:27,470 --> 00:47:28,730
Ek raai terugkeer -

573
00:47:28,730 --> 00:47:30,510
Jy hoef nie rekursie te doen vir merge

574
00:47:30,510 --> 00:47:33,750
omdat rekursie vir merge te doen, jy gaan te hê om 'n klomp van verskillende groottes te slaag.

575
00:47:33,750 --> 00:47:37,150
Jy kan, maar dit is irriterende.

576
00:47:37,150 --> 00:47:43,720
Maar rekursie vir soort self is redelik maklik.

577
00:47:43,720 --> 00:47:49,190
Jy moet net letterlik bel soort op die linker helfte, sorteer op die regter helfte. Okay.

578
00:47:51,770 --> 00:47:54,860
Enigiemand enigiets wat ek nog kan trek?

579
00:47:54,860 --> 00:47:57,540
Of anders sal ek gee 'n minuut.

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

581
00:47:59,900 --> 00:48:02,970
Iemand het iets wat ons kan werk met?

582
00:48:05,450 --> 00:48:09,680
Of anders het ons sal net werk met hierdie en dan van daar af uit te brei.

583
00:48:09,680 --> 00:48:14,050
>> Iemand het meer as dit nie, dat ek kan trek?

584
00:48:14,050 --> 00:48:17,770
[Student] Ja. Jy kan trek op my. >> Alle regte.

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

586
00:48:22,170 --> 00:48:25,280
[Student] Daar was 'n baie voorwaardes. >> O, skiet. Kan jy -

587
00:48:25,280 --> 00:48:28,110
[Student] Ek het om dit te red. >> Ja.

588
00:48:32,420 --> 00:48:35,730
So ons het die kombinering doen afsonderlik.

589
00:48:35,730 --> 00:48:38,570
Ag, maar dit is nie so sleg nie.

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

591
00:48:41,650 --> 00:48:47,080
So soort is self bel net mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Verduidelik vir ons wat mergeSortHelp doen.

593
00:48:49,530 --> 00:48:55,700
[Studente] MergeSortHelp mooi nie veel die twee hoof stappe,

594
00:48:55,700 --> 00:49:01,270
wat elke helfte van die skikking te sorteer en dan albei van hulle om saam te smelt.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Okay, so gee my 'n tweede.

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

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

598
00:49:19,400 --> 00:49:23,100
In merge, ek besef dat ek nodig het om te skep 'n nuwe skikking

599
00:49:23,100 --> 00:49:26,530
want ek kon nie dit doen in die plek. >> Ja. Jy kan nie. Korrigeer.

600
00:49:26,530 --> 00:49:28,170
[Student] So het ek 'n nuwe skikking.

601
00:49:28,170 --> 00:49:31,510
Ek het vergeet om by die einde van saamsmelt weer verander.

602
00:49:31,510 --> 00:49:34,490
Okay. Ons moet 'n nuwe skikking.

603
00:49:34,490 --> 00:49:41,000
In merge soort, dit is amper altyd waar nie.

604
00:49:41,000 --> 00:49:44,340
Deel van die koste van 'n beter algoritme tyd-wyse

605
00:49:44,340 --> 00:49:47,310
is byna altyd nodig om 'n bietjie meer geheue te gebruik.

606
00:49:47,310 --> 00:49:51,570
So hier is, maak nie saak hoe jy dit doen saamsmelt soort,

607
00:49:51,570 --> 00:49:54,780
jy sou onvermydelik 'n paar ekstra geheue te gebruik.

608
00:49:54,780 --> 00:49:58,240
Hy of sy het 'n nuwe skikking.

609
00:49:58,240 --> 00:50:03,400
En dan sê jy aan die einde moet ons net nuwe skikking in die oorspronklike skikking te kopieer.

610
00:50:03,400 --> 00:50:04,830
[Student] Ek dink so, ja.

611
00:50:04,830 --> 00:50:08,210
Ek weet nie of dit werk in terme van tel deur verwysing of wat ook al -

612
00:50:08,210 --> 00:50:11,650
Ja, sal dit werk. >> [Student] Goed.

613
00:50:20,620 --> 00:50:24,480
Het jy probeer om hierdie? >> [Student] Nee, nog nie. >> Goed.

614
00:50:24,480 --> 00:50:28,880
Probeer om dit, en dan sal ek praat oor dit vir 'n tweede.

615
00:50:28,880 --> 00:50:35,200
[Student] Ek nodig het om al die funksies wat prototipes en alles te hê, al is, reg?

616
00:50:37,640 --> 00:50:40,840
Die funksie prototipes. O, jy bedoel soos - Ja.

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

618
00:50:43,040 --> 00:50:47,390
>> So ten einde vir die soort mergeSortHelp te roep, moet óf mergeSortHelp gewees het gedefinieer

619
00:50:47,390 --> 00:50:56,370
voor soort of moet ons net die prototipe. Net kopieer en plak dat.

620
00:50:56,370 --> 00:50:59,490
En insgelyks, is mergeSortHelp roep saamsmelt,

621
00:50:59,490 --> 00:51:03,830
maar merge nie is nog nie gedefinieer, sodat ons kan net laat mergeSortHelp weet

622
00:51:03,830 --> 00:51:08,700
dat dit is wat saamsmelt gaan lyk, en dit is dit.

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

624
00:51:22,770 --> 00:51:32,660
Ons het 'n probleem hier waar ons het geen basis geval.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp rekursiewe, so 'n rekursiewe funksie

626
00:51:38,110 --> 00:51:42,610
gaan om 'n soort van die basis-geval nodig om te weet wanneer om te stop rekursief roep self.

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

628
00:51:45,590 --> 00:51:49,110
[Student] As die grootte is 1? >> [Bowden] Ja.

629
00:51:49,110 --> 00:51:56,220
Dus, net soos ons gesien het net daar, het ons gestop splitsing skikkings

630
00:51:56,220 --> 00:52:01,850
sodra ons het in skikkings van grootte 1, wat onvermydelik is gesorteer self.

631
00:52:01,850 --> 00:52:09,530
So as grootte is gelyk aan 1, weet ons die skikking reeds gesorteer is,

632
00:52:09,530 --> 00:52:12,970
sodat ons kan net terugkeer.

633
00:52:12,970 --> 00:52:16,880
>> Let daarop dat is nietig, sodat ons terugkeer nie iets besonder, het ons net terug te keer.

634
00:52:16,880 --> 00:52:19,580
Okay. So dit is ons basis geval.

635
00:52:19,580 --> 00:52:27,440
Ek dink ons ​​basis geval ook kan wees as ons gebeur word die samesmelting van 'n verskeidenheid van grootte 0,

636
00:52:27,440 --> 00:52:30,030
ons waarskynlik wil om te stop op 'n sekere punt,

637
00:52:30,030 --> 00:52:33,610
sodat ons kan net sê grootte minder as 2 of minder as of gelyk aan 1

638
00:52:33,610 --> 00:52:37,150
sodat dit sal werk vir enige skikking nou.

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

640
00:52:38,870 --> 00:52:42,740
So dit is ons basis geval.

641
00:52:42,740 --> 00:52:45,950
Nou wil jy ons om te wandel deur merge?

642
00:52:45,950 --> 00:52:49,140
Wat doen al hierdie gevalle beteken?

643
00:52:49,140 --> 00:52:54,480
Hier, ons is net doen dieselfde idee, die -

644
00:52:56,970 --> 00:53:02,470
[Student] Ek moet verby grootte met al die mergeSortHelp oproepe.

645
00:53:02,470 --> 00:53:10,080
Ek bygevoeg grootte as 'n addisionele primêre en dit is nie daar nie, soos grootte / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] O, grootte / 2, grootte / 2. >> [Student] Ja, en ook in die bogenoemde funksie sowel.

647
00:53:16,210 --> 00:53:21,320
[Bowden] hier? >> [Student] Net grootte. >> [Bowden] Oh. Grootte, grootte? >> [Student] Ja.

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

649
00:53:23,010 --> 00:53:26,580
Laat my dink vir 'n tweede.

650
00:53:26,580 --> 00:53:28,780
Loop ons nie in 'n probleem?

651
00:53:28,780 --> 00:53:33,690
Ons is altyd op die behandeling van die linkerkant as 0. >> [Student] No

652
00:53:33,690 --> 00:53:36,340
Wat verkeerd is. Jammer. Dit moet begin. Ja.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Goed. Ek hou van wat 'n beter.

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

655
00:53:43,880 --> 00:53:47,200
So nou wil jy ons om te wandel deur merge? >> [Student] Goed.

656
00:53:47,200 --> 00:53:52,150
Ek net loop deur hierdie nuwe skikking wat ek gemaak het.

657
00:53:52,150 --> 00:53:57,420
Sy grootte is die grootte van die gedeelte van die skikking wat ons wil word gesorteer

658
00:53:57,420 --> 00:54:03,460
en probeer om die element te vind dat ek moet sit in die nuwe skikking stap.

659
00:54:03,460 --> 00:54:10,140
So om dit te doen, in die eerste ek nagaan indien die linker helfte van die skikking steeds meer elemente te hê,

660
00:54:10,140 --> 00:54:14,260
en as dit nie, dan gaan jy af na wat anders toestand, wat net sê

661
00:54:14,260 --> 00:54:20,180
okay, moet dit in die regte array, en ons sal in die huidige indeks van newArray.

662
00:54:20,180 --> 00:54:27,620
>> En dan anders, ek nagaan of die regterkant van die skikking is ook klaar,

663
00:54:27,620 --> 00:54:30,630
in welke geval ek net sit aan die linkerkant.

664
00:54:30,630 --> 00:54:34,180
Dit kan eintlik nie nodig nie. Ek is nie seker nie.

665
00:54:34,180 --> 00:54:40,970
Maar in elk geval, die ander twee tjek watter een van die twee is kleiner in die linker-of die regterkant.

666
00:54:40,970 --> 00:54:49,770
En ook in elke geval, ek verhoog van wat ookal place holder Ek inkrementeer.

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

668
00:54:52,040 --> 00:54:53,840
Dit lyk goed.

669
00:54:53,840 --> 00:54:58,800
Is daar iemand het kommentaar of kommer of vrae?

670
00:55:00,660 --> 00:55:07,720
Toe is die vier gevalle dat ons dinge te bring in net '- of dit lyk soos vyf -

671
00:55:07,720 --> 00:55:13,100
maar ons het om te oorweeg of die linker-skikking het hardloop uit van die dinge wat ons nodig het om saam te smelt,

672
00:55:13,100 --> 00:55:16,390
of die regte skikking het hardloop uit van die dinge wat ons nodig het om saam te smelt -

673
00:55:16,390 --> 00:55:18,400
Ek wys niks.

674
00:55:18,400 --> 00:55:21,730
So of die linker-skikking van die dinge loop uit of die regte array het hardloop uit van die dinge.

675
00:55:21,730 --> 00:55:24,320
Dit is twee gevalle.

676
00:55:24,320 --> 00:55:30,920
Ons moet ook die triviale geval van of die linker ding is minder as die regte ding.

677
00:55:30,920 --> 00:55:33,910
Dan wil ons die linker ding om te kies.

678
00:55:33,910 --> 00:55:37,630
Dit is die gevalle.

679
00:55:37,630 --> 00:55:40,990
So dit was reg nie, maar dit is dit.

680
00:55:40,990 --> 00:55:46,760
Array verlaat. Dit is 1, 2, 3. Okay. So ja, wat is die vier dinge wat ons dalk wil om dit te doen.

681
00:55:50,350 --> 00:55:54,510
En ons sal nie gaan oor 'n iteratiewe oplossing.

682
00:55:54,510 --> 00:55:55,980
Ek sou nie aanbeveel -

683
00:55:55,980 --> 00:56:03,070
Merge soort is 'n voorbeeld van 'n funksie wat beide nie die stert rekursiewe,

684
00:56:03,070 --> 00:56:07,040
dit is nie maklik om te maak dit stert rekursiewe,

685
00:56:07,040 --> 00:56:13,450
maar ook dit is nie baie maklik om te maak dit iteratiewe.

686
00:56:13,450 --> 00:56:16,910
Dit is baie maklik.

687
00:56:16,910 --> 00:56:19,170
Hierdie implementering van merge soort,

688
00:56:19,170 --> 00:56:22,140
saam te smelt, maak nie saak wat jy doen nie, jy gaan saamsmelt te bou.

689
00:56:22,140 --> 00:56:29,170
>> So soort wat gebou is op die top van merge saamsmelt rekursief is net hierdie drie lyne.

690
00:56:29,170 --> 00:56:34,700
Iteratief, dit is meer irriterende en meer moeilik om oor na te dink.

691
00:56:34,700 --> 00:56:41,860
Maar let op dat dit nie stert rekursiewe sedert mergeSortHelp - wanneer dit oproepe self -

692
00:56:41,860 --> 00:56:46,590
dit moet nog dinge om te doen nadat hierdie rekursiewe oproep opbrengste.

693
00:56:46,590 --> 00:56:50,830
So hierdie stapel moet voortgaan om te bestaan, selfs nadat noem hierdie.

694
00:56:50,830 --> 00:56:54,170
En dan wanneer jy noem dit, moet die stapel raam voortgaan om te bestaan

695
00:56:54,170 --> 00:56:57,780
want selfs na daardie oproep, het ons nog nodig het om saam te smelt.

696
00:56:57,780 --> 00:57:01,920
En dit is triviaal hierdie stert rekursiewe te maak.

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

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

699
00:57:09,860 --> 00:57:13,400
So gaan terug om te sorteer - oh, daar is twee dinge wat ek wil om te wys. Okay.

700
00:57:13,400 --> 00:57:17,840
Terug te gaan na soort, sal ons doen dit vinnig.

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

702
00:57:21,030 --> 00:57:22,730
Terug te gaan na die begin van die soort.

703
00:57:22,730 --> 00:57:29,870
Ons wil 'n algoritme wat die skikking vorme met behulp van 'n algoritme te skep

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

705
00:57:33,660 --> 00:57:40,860
So, hoe is dit moontlik? Is daar iemand enige soort van -

706
00:57:40,860 --> 00:57:44,300
Ek terloops voor op -

707
00:57:44,300 --> 00:57:48,300
As ons oor te verbeter van n log n O van n,

708
00:57:48,300 --> 00:57:51,450
ons verbeter ons algoritme tyd-wyse,

709
00:57:51,450 --> 00:57:55,250
wat beteken wat gaan ons nodig het om te doen om te vergoed vir wat?

710
00:57:55,250 --> 00:57:59,520
[Student] Space. >> Ja. Ons gaan om te word deur gebruik te maak van meer ruimte.

711
00:57:59,520 --> 00:58:04,490
En selfs nie net meer ruimte, dit is eksponensieel meer ruimte.

712
00:58:04,490 --> 00:58:14,320
So ek dink hierdie tipe van die algoritme is pseudo iets pseudo polynom -

713
00:58:14,320 --> 00:58:18,980
pseudo - Ek kan nie onthou nie. Pseudo iets.

714
00:58:18,980 --> 00:58:22,210
Maar dit is omdat ons soveel ruimte nodig het om te gebruik

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

716
00:58:28,610 --> 00:58:31,220
>> En hoe kry ons dit?

717
00:58:31,220 --> 00:58:36,810
Ons dit kan bereik as ons waarborg dat 'n bepaalde element in die skikking

718
00:58:36,810 --> 00:58:39,600
is onder 'n sekere grootte.

719
00:58:42,070 --> 00:58:44,500
So laat ons net sê dat die grootte is 200,

720
00:58:44,500 --> 00:58:48,130
'n element in 'n skikking is onder grootte 200.

721
00:58:48,130 --> 00:58:51,080
En dit is eintlik baie realisties.

722
00:58:51,080 --> 00:58:58,660
Kan jy baie maklik 'n skikking wat jy weet alles wat daarin

723
00:58:58,660 --> 00:59:00,570
gaan minder wees as sommige nommer.

724
00:59:00,570 --> 00:59:07,400
Soos as jy het 'n paar absoluut massiewe vektor of iets

725
00:59:07,400 --> 00:59:11,810
maar jy weet alles gaan wees tussen 0 en 5,

726
00:59:11,810 --> 00:59:14,790
dan is dit gaan te wees beduidend vinniger om dit te doen.

727
00:59:14,790 --> 00:59:17,930
En die gebonde op enige van die elemente is 5,

728
00:59:17,930 --> 00:59:21,980
sodat dit gebonde, dit is hoeveel geheue wat jy gaan word met behulp van.

729
00:59:21,980 --> 00:59:26,300
Sodat die gebonde is 200.

730
00:59:26,300 --> 00:59:32,960
In teorie is daar altyd 'n gebonde sedert kan slegs 'n heelgetal wees tot 4 miljard,

731
00:59:32,960 --> 00:59:40,600
maar dit is onrealisties want dan sou ons gebruik word om ruimte

732
00:59:40,600 --> 00:59:44,400
op die einde van 4 miljard. So dit is onrealisties.

733
00:59:44,400 --> 00:59:47,060
Maar hier sal ons sê ons gebonde is 200.

734
00:59:47,060 --> 00:59:59,570
Die truuk om dit te doen in die O van n is dat ons nog 'n skikking met die naam tellings van grootte gebind.

735
00:59:59,570 --> 01:00:10,470
So dit is eintlik 'n kortpad vir - Ek weet eintlik nie of kletteren doen dit.

736
01:00:11,150 --> 01:00:15,330
Maar in die GCC op die heel minste, ek veronderstelling kletteren doen dit ook -

737
01:00:15,330 --> 01:00:18,180
dit sal net die hele verskeidenheid inisialiseer 0e te wees.

738
01:00:18,180 --> 01:00:25,320
So as ek nie wil hê om dit te doen, dan kon ek afsonderlik doen vir (int i = 0;

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

740
01:00:31,500 --> 01:00:35,260
So nou alles geïnisialiseer tot 0.

741
01:00:35,260 --> 01:00:39,570
Ek oor my array itereer

742
01:00:39,570 --> 01:00:51,920
en wat ek doen is ek die getal van elke is toe - Kom ons gaan hier neer.

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

744
01:00:55,480 --> 01:01:00,010
Wat ek toe, is die aantal voorkomste van elk van hierdie elemente.

745
01:01:00,010 --> 01:01:03,470
Kom ons eintlik nog 'n paar byvoeg hier met 'n paar herhalings.

746
01:01:03,470 --> 01:01:11,070
Dus is die waarde wat ons hier het, is die waarde van daardie gaan wees array [i].

747
01:01:11,070 --> 01:01:14,850
So val kan wees 4 of 8 of wat ook al.

748
01:01:14,850 --> 01:01:18,870
En nou is ek tel hoeveel van daardie waarde wat ek gesien het,

749
01:01:18,870 --> 01:01:21,230
so tel [val] + +;

750
01:01:21,230 --> 01:01:29,430
Nadat dit gedoen is, is tellings gaan om iets te lyk soos 0001.

751
01:01:29,430 --> 01:01:42,190
Kom ons doen tellings [val] - gebonde + 1.

752
01:01:42,190 --> 01:01:48,230
>> Nou is dit net vir die feit dat ons vanaf 0 tot verantwoording.

753
01:01:48,230 --> 01:01:50,850
So as 200 gaan ons grootste getal wees,

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

755
01:01:54,720 --> 01:02:01,540
So tel, sal dit lyk soos 00.001, want ons het 'n 4.

756
01:02:01,540 --> 01:02:10,210
Dan sal ons 0001 waar ons sal moet 'n 1 in die 8ste indeks van die telling.

757
01:02:10,210 --> 01:02:14,560
Ons sal 'n 2 in die 23ste indeks van die telling.

758
01:02:14,560 --> 01:02:17,630
Ons sal 'n 2 in die 42ste-indeks van die telling.

759
01:02:17,630 --> 01:02:21,670
Sodat ons kan reken.

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

761
01:02:44,920 --> 01:02:52,540
En so, as num_of_item is 2, wat beteken dat ons wil te voeg 2 van die aantal i

762
01:02:52,540 --> 01:02:55,290
in ons gesorteer skikking.

763
01:02:55,290 --> 01:03:02,000
Sodat ons nodig het om tred te hou van hoe ver ons is in die skikking.

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

765
01:03:05,470 --> 01:03:09,910
Array - ek sal net dit skryf.

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

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

768
01:03:28,580 --> 01:03:32,490
Is dit wat ek wil? Ek dink dit is wat ek wil hê.

769
01:03:35,100 --> 01:03:38,290
Ja, dit lyk goed. Okay.

770
01:03:38,290 --> 01:03:43,050
So het almal verstaan ​​wat die doel van my tel array is?

771
01:03:43,050 --> 01:03:48,140
Dit is die tel van die aantal voorkomste van elk van hierdie getalle.

772
01:03:48,140 --> 01:03:51,780
Dan is ek iterating oor wat tel skikking,

773
01:03:51,780 --> 01:03:57,190
en die met posisie in die tellings skikking

774
01:03:57,190 --> 01:04:01,930
is die aantal i is wat moet verskyn in my gesorteer array.

775
01:04:01,930 --> 01:04:06,840
Dit is die rede waarom aanklagte van 4 gaan wees 1

776
01:04:06,840 --> 01:04:11,840
en tellings van 8 gaan wees 1, tellings van 23 gaan wees 2.

777
01:04:11,840 --> 01:04:16,900
So dit is hoe baie van hulle ek wil in te voeg in my gesorteer skikking.

778
01:04:16,900 --> 01:04:19,200
Toe het ek net doen.

779
01:04:19,200 --> 01:04:28,960
Ek invoeging num_of_item i in my gesorteer verskeidenheid.

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

781
01:04:32,460 --> 01:04:43,100
En so weer, dit is lineêr tyd sedert ons is net iterating oor hierdie een keer,

782
01:04:43,100 --> 01:04:47,470
maar dit is ook lineêre in wat hierdie getal gebeur om te wees,

783
01:04:47,470 --> 01:04:50,730
en so is dit hang swaar op wat jou gebonde is.

784
01:04:50,730 --> 01:04:53,290
Met 'n gebonde 200, dit is nie so sleg nie.

785
01:04:53,290 --> 01:04:58,330
As jou gebonde gaan wees 10.000, dan is dit 'n bietjie erger,

786
01:04:58,330 --> 01:05:01,360
maar as jou gebonde gaan wees 4 miljard, wat is heeltemal onrealisties

787
01:05:01,360 --> 01:05:07,720
en hierdie skikking gaan hê om van grootte 4 miljard, wat is onrealisties.

788
01:05:07,720 --> 01:05:10,860
So dit is dit. Vrae?

789
01:05:10,860 --> 01:05:13,270
[Onhoorbaar student reaksie] >> Goed.

790
01:05:13,270 --> 01:05:15,710
Ek het besef 'n ander ding, wanneer ons gaan deur.

791
01:05:17,980 --> 01:05:23,720
Ek dink die probleem was in Lucas se en waarskynlik elke enkele een wat ons gesien het.

792
01:05:23,720 --> 01:05:26,330
Ek het heeltemal vergeet.

793
01:05:26,330 --> 01:05:31,040
Die enigste ding wat ek wou om kommentaar te lewer op, is dat wanneer jy te doen het met dinge soos indekse,

794
01:05:31,040 --> 01:05:38,320
jy nooit regtig sien dit wanneer jy die skryf van 'n for-lus,

795
01:05:38,320 --> 01:05:41,120
maar tegnies, wanneer jy te doen het met hierdie indekse,

796
01:05:41,120 --> 01:05:45,950
jy moet pretty much altyd hanteer unsigned heelgetalle.

797
01:05:45,950 --> 01:05:53,850
Die rede hiervoor is wanneer jy met onderteken heelgetalle,

798
01:05:53,850 --> 01:05:56,090
so as jy 2 onderteken heelgetalle en jy voeg hulle saam

799
01:05:56,090 --> 01:06:00,640
en hulle uiteindelik te groot is, dan beland jy met 'n negatiewe getal.

800
01:06:00,640 --> 01:06:03,410
So dit is wat integriteit overflow is.

801
01:06:03,410 --> 01:06:10,500
>> As ek voeg 2 miljard en 1 miljard, Ek eindig met 'n negatiewe 1 miljard.

802
01:06:10,500 --> 01:06:15,480
Dit is hoe heelgetalle werk op rekenaars.

803
01:06:15,480 --> 01:06:17,510
Dus is die probleem met die gebruik van -

804
01:06:17,510 --> 01:06:23,500
Dit is goed behalwe as lae gebeur met 2 miljard en gebeur met 1 miljard,

805
01:06:23,500 --> 01:06:27,120
dan is dit gaan om negatief te wees 1 miljard en dan gaan ons te verdeel deur 2

806
01:06:27,120 --> 01:06:29,730
en eindig met 'n negatiewe 500 miljoen.

807
01:06:29,730 --> 01:06:33,760
So dit is net 'n probleem as jy toevallig op soek deur middel van 'n skikking

808
01:06:33,760 --> 01:06:38,070
van miljarde van dinge.

809
01:06:38,070 --> 01:06:44,050
Maar as lae + up laat aanstroom het gebeur, dan is dit 'n probleem.

810
01:06:44,050 --> 01:06:47,750
So gou as wat ons maak hulle unsigned, dan 2 miljard plus 1 miljard is 3 miljard.

811
01:06:47,750 --> 01:06:51,960
3 miljard gedeel deur 2 is 1,5 miljard.

812
01:06:51,960 --> 01:06:55,670
So gou as wat hulle is unsigned, alles is perfek.

813
01:06:55,670 --> 01:06:59,900
En so het dit is ook 'n probleem wanneer jy skryf jou vir loops,

814
01:06:59,900 --> 01:07:03,940
en eintlik is dit nie waarskynlik is dit outomaties.

815
01:07:09,130 --> 01:07:12,330
Dit sal net eintlik skreeu op jou.

816
01:07:12,330 --> 01:07:21,610
So as hierdie nommer is te groot om in net 'n heelgetal, maar dit sou pas in 'n ongetekende heelgetal,

817
01:07:21,610 --> 01:07:24,970
dit sal gil op jou, so dis hoekom jy nooit werklik loop in die kwessie.

818
01:07:29,150 --> 01:07:34,820
Jy kan sien dat 'n indeks nooit gaan om negatief te wees,

819
01:07:34,820 --> 01:07:39,220
en so wanneer jy iterating oor 'n skikking,

820
01:07:39,220 --> 01:07:43,970
kan jy byna altyd sê unsigned int i, maar jy het nie regtig aan.

821
01:07:43,970 --> 01:07:47,110
Dinge gaan pretty much werk net so goed.

822
01:07:48,740 --> 01:07:50,090
Okay. [Fluister] Hoe laat is dit?

823
01:07:50,090 --> 01:07:54,020
Die laaste ding wat ek wou om te wys - en ek sal doen dit net regtig vinnig.

824
01:07:54,020 --> 01:08:03,190
Jy weet hoe ons # definieer sodat ons kan # MAX definieer as 5 of iets?

825
01:08:03,190 --> 01:08:05,940
Laat ons nie doen MAX. # Define gebind as 200. Dit is wat ons gedoen het voor.

826
01:08:05,940 --> 01:08:10,380
Wat definieer 'n konstante, wat net gaan om te gekopieer en geplak word

827
01:08:10,380 --> 01:08:13,010
waar ons gebeur te skryf GEBONDE.

828
01:08:13,010 --> 01:08:18,189
>> Sodat ons kan eintlik meer doen met # definieer.

829
01:08:18,189 --> 01:08:21,170
Ons kan definieer # funksies.

830
01:08:21,170 --> 01:08:23,410
Hulle is nie regtig funksies, maar ons sal hulle noem funksies.

831
01:08:23,410 --> 01:08:36,000
'N voorbeeld sou wees iets soos MAX (x, y) word gedefinieer as (x <y y: x). Okay.

832
01:08:36,000 --> 01:08:40,660
So jy moet gewoond raak aan drieledige operateur sintaksis,

833
01:08:40,660 --> 01:08:49,029
maar is x minder as y? Terug y, anders x terugkeer.

834
01:08:49,029 --> 01:08:54,390
Sodat jy kan sien jy kan hierdie 'n aparte funksie,

835
01:08:54,390 --> 01:09:01,399
en die funksie kan wees soos Bool MAX 2 argumente, terugkeer.

836
01:09:01,399 --> 01:09:08,340
Dit is een van die mees algemene wat ek sien soos hierdie. Ons noem hulle macros.

837
01:09:08,340 --> 01:09:11,790
Dit is 'n makro.

838
01:09:11,790 --> 01:09:15,859
Dit is net die sintaksis vir dit.

839
01:09:15,859 --> 01:09:18,740
Jy kan skryf 'n makro om te doen wat jy wil.

840
01:09:18,740 --> 01:09:22,649
Sien jy gereeld macros vir die ontfouting van printfs en stuff.

841
01:09:22,649 --> 01:09:29,410
So 'n tipe van printf, is daar spesiale konstantes in C soos onderstreping LINE onderstreping,

842
01:09:29,410 --> 01:09:31,710
2 beklemtoon LINE onderstreep,

843
01:09:31,710 --> 01:09:37,550
en daar is ook Ek dink 2 beklemtoon funk. Wat dit kan wees nie. Iets soos dit.

844
01:09:37,550 --> 01:09:40,880
Hierdie dinge sal vervang word met die naam van die funksie

845
01:09:40,880 --> 01:09:42,930
of die getal van die lyn wat jy op.

846
01:09:42,930 --> 01:09:48,630
Jy skryf gereeld, die ontfouting van printfs dat hier af Ek kon net skryf dan

847
01:09:48,630 --> 01:09:54,260
Ontfout en dit sal die lyn en die funksie wat ek toevallig in print

848
01:09:54,260 --> 01:09:57,020
dat dit teëgekom dat DEBUG verklaring.

849
01:09:57,020 --> 01:09:59,550
En jy kan ook ander dinge druk.

850
01:09:59,550 --> 01:10:05,990
Sodat die een ding wat jy moet kyk uit vir as ek toevallig om te definieer # DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
as iets soos 2 * y en 2 * x.

852
01:10:11,380 --> 01:10:14,310
Dus, vir watter rede ookal, jy gebeur dat 'n baie om te doen.

853
01:10:14,310 --> 01:10:16,650
So maak dit 'n makro.

854
01:10:16,650 --> 01:10:18,680
Dit is eintlik gebreek.

855
01:10:18,680 --> 01:10:23,050
Ek noem dit deur om iets te doen soos DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
So, wat moet teruggestuur word?

857
01:10:28,840 --> 01:10:30,580
[Student] 12.

858
01:10:30,580 --> 01:10:34,800
Ja, moet 12 teruggestuur word, en 12 terugbesorg word.

859
01:10:34,800 --> 01:10:43,350
3 kry vir x vervang, kry 6 vervang vir y, en ons terugkeer 2 * 6, wat is 12.

860
01:10:43,350 --> 01:10:47,710
Nou wat oor hierdie? Wat moet teruggestuur word?

861
01:10:47,710 --> 01:10:50,330
[Student] 14. >> Ideaal, 14.

862
01:10:50,330 --> 01:10:55,290
Die probleem is dat hoe hash definieer werk, onthou dit is 'n letterlike kopieer en plak

863
01:10:55,290 --> 01:11:00,160
pretty much alles, so wat hierdie gaan vertolk word as

864
01:11:00,160 --> 01:11:11,270
is 3 minder as 1 plus 6, 2 keer 1 plus 6, 2 keer 3.

865
01:11:11,270 --> 01:11:19,780
>> Dus, om hierdie rede wat jy byna altyd draai alles in hakies.

866
01:11:22,180 --> 01:11:25,050
Enige veranderlike wat jy byna altyd draai in hakies.

867
01:11:25,050 --> 01:11:29,570
Daar is gevalle waar jy nie hoef te, soos ek weet dat ek nie nodig het nie wat om hier te doen nie

868
01:11:29,570 --> 01:11:32,110
omdat minder as is pretty much altyd net gaan om te werk,

869
01:11:32,110 --> 01:11:34,330
alhoewel dit kan selfs nie waar wees nie.

870
01:11:34,330 --> 01:11:41,870
As daar iets is belaglik soos DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
dan wat gaan om te vervang met 3 minder as 1 is gelyk aan gelyk is aan 2,

872
01:11:49,760 --> 01:11:53,460
en so dan is dit gaan te doen 3 minder as 1, dat gelyke 2,

873
01:11:53,460 --> 01:11:55,620
wat is nie wat ons wil hê.

874
01:11:55,620 --> 01:12:00,730
Dus, ten einde enige operateur voorrang probleme te voorkom,

875
01:12:00,730 --> 01:12:02,870
draai altyd in hakies.

876
01:12:03,290 --> 01:12:07,700
Okay. En dit is dit, 05:30.

877
01:12:08,140 --> 01:12:12,470
As jy enige vrae oor die pset, laat ons weet.

878
01:12:12,470 --> 01:12:18,010
Dit moet pret wees, en die hacker uitgawe is ook baie meer realistiese

879
01:12:18,010 --> 01:12:22,980
as die hacker uitgawe van verlede jaar se, so ons hoop dat baie van julle probeer om dit.

880
01:12:22,980 --> 01:12:26,460
Verlede jaar was baie oorweldigend.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]