1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [3 jakso - Lisää Mukava]

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

3
00:00:05,070 --> 00:00:07,310
>> [Tämä on CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Joten ensimmäinen kysymys on oudosti muotoiltu.

5
00:00:12,700 --> 00:00:17,480
GDB voit "debug"-ohjelma, mutta täsmällisemmin, mitä se antaa sinun tehdä?

6
00:00:17,480 --> 00:00:22,590
Minä vastaan, että yksi, ja en tiedä mitä tarkalleen odottaa,

7
00:00:22,590 --> 00:00:27,910
joten olen vierasta se on jotain tapaan sen avulla voit askel askeleelta

8
00:00:27,910 --> 00:00:31,540
kävellä ohjelman vuorovaikutuksessa sen kanssa, eri muuttujien, tehdä kaikki nämä asiat -

9
00:00:31,540 --> 00:00:34,270
pohjimmiltaan täysin hallita ohjelman suorituksen

10
00:00:34,270 --> 00:00:38,410
ja tarkasta tahansa osaa ohjelman täytäntöönpanon.

11
00:00:38,410 --> 00:00:43,030
Joten nämä ominaisuudet voit debug asioita.

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

13
00:00:44,830 --> 00:00:50,520
Miksi binäärihakupuu edellyttävät array lajitella?

14
00:00:50,520 --> 00:00:53,360
Kuka haluaa vastata tähän?

15
00:00:56,120 --> 00:01:00,070
[Opiskelija] Koska se ei toimi, jos se ei ole lajiteltu. >> Joo. [Naurua]

16
00:01:00,070 --> 00:01:04,910
Jos se ei ole lajiteltu, niin se on mahdotonta jakaa sen kahtia

17
00:01:04,910 --> 00:01:07,850
ja tiedämme, että kaiken vasemmalla on vähemmän ja kaikki oikealle

18
00:01:07,850 --> 00:01:10,490
on suurempi kuin keskimmäinen arvo.

19
00:01:10,490 --> 00:01:12,790
Joten se on ratkaistava.

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

21
00:01:14,170 --> 00:01:17,570
Miksi kupla lajitella O n neliö?

22
00:01:17,570 --> 00:01:23,230
Onko kukaan haluaa ensin antaa hyvin nopeasti korkean tason yleiskuvan siitä, mitä kuplan sort on?

23
00:01:25,950 --> 00:01:33,020
[Opiskelija] Olet periaatteessa käydä läpi jokaisen elementin ja voit tarkistaa muutaman ensimmäisen elementtejä.

24
00:01:33,020 --> 00:01:37,150
Jos he ovat poissa missä vaihtaa niitä, niin tarkista tulevina elementit ja niin edelleen.

25
00:01:37,150 --> 00:01:40,770
Kun tulet loppuun, niin tiedät, että suurin osa on sijoitettu lopussa

26
00:01:40,770 --> 00:01:42,750
niin ohitat että yksi sinun pitää käydä läpi,

27
00:01:42,750 --> 00:01:48,490
ja joka kerta täytyy tarkistaa yksi vähemmän elementti kunnes teet mitään muutoksia. >> Joo.

28
00:01:48,490 --> 00:01:58,470
Sitä kutsutaan kupla lajitella koska jos kääntää array kyljelleen niin se on ylös ja alas, pystysuora,

29
00:01:58,470 --> 00:02:03,100
Sitten suuret arvot vajoavat pohjaan ja pienet arvot tulee kupla ylös.

30
00:02:03,100 --> 00:02:05,210
Niin se on saanut nimensä.

31
00:02:05,210 --> 00:02:08,220
Ja joo, juuri läpi.

32
00:02:08,220 --> 00:02:11,190
Pidät läpi array, vaihtamalla suuremman arvon

33
00:02:11,190 --> 00:02:14,040
saada suurimmat arvot pohjaan.

34
00:02:14,040 --> 00:02:17,500
>> Miksi se O n neliö?

35
00:02:18,690 --> 00:02:24,620
Ensinnäkin, ei kukaan halua sanoa miksi se on O n neliö?

36
00:02:24,620 --> 00:02:28,760
[Opiskelija] Koska jokaisen ajon se menee n kertaa.

37
00:02:28,760 --> 00:02:32,100
Voit olla varma, että olet ottanut suurimman elementin kokonaan alas,

38
00:02:32,100 --> 00:02:35,230
sinun on toistettava, että niin monta elementtiä. >> Joo.

39
00:02:35,230 --> 00:02:41,800
Joten pitää mielessä, mitä Big O tarkoittaa ja mitä iso Omega keinoin.

40
00:02:41,800 --> 00:02:50,560
Big O on kuin yläraja kuinka hidas se voi todella ajaa.

41
00:02:50,560 --> 00:02:58,990
Joten sanomalla, että se on O n potenssiin, se ei ole O n tai muuten se voisi ajaa

42
00:02:58,990 --> 00:03:02,640
lineaarisessa ajassa, mutta se on O n kuutioitu

43
00:03:02,640 --> 00:03:06,390
koska se rajoittuu O n kuutioitu.

44
00:03:06,390 --> 00:03:12,300
Jos se rajoittuu O n neliö, niin se rajoittuu myös N kuutioitu.

45
00:03:12,300 --> 00:03:20,280
Joten se on n potenssiin, ja ehdoton pahimmassa tapauksessa se ei voi tehdä paremmin kuin n potenssiin,

46
00:03:20,280 --> 00:03:22,830
minkä vuoksi se on O n: n neliö.

47
00:03:22,830 --> 00:03:31,200
Joten nähdä hieman matematiikkaa, miten se tulee ulos n potenssiin,

48
00:03:31,200 --> 00:03:40,530
jos meillä on viisi asiaa listalta, ensimmäistä kertaa kuinka monta swap voisimme mahdollisesti täytyy tehdä

49
00:03:40,530 --> 00:03:47,170
Jotta saat tämän? Katsotaanpa oikeastaan ​​vain -

50
00:03:47,170 --> 00:03:52,040
Kuinka monta swap aiomme täytyy tehdä ensimmäisen ajaa kupla lajitella array?

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

52
00:03:53,540 --> 00:03:58,340
>> Jos on 5 elementtejä, olemme menossa tarvitse tehdä n - 1.

53
00:03:58,340 --> 00:04:01,100
Sitten toinen kuinka monta swap aiomme pitää tehdä?

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

55
00:04:03,440 --> 00:04:11,640
Ja kolmas tulee olemaan n - 3, ja sitten mukavuussyistä aion kirjoittaa kaksi viimeistä

56
00:04:11,640 --> 00:04:15,270
koska silloin olemme menossa tarvitse tehdä 2 swapit ja 1 swap.

57
00:04:15,270 --> 00:04:19,899
Oletan viimeinen tai ei oikeastaan ​​tarvitse tapahtua.

58
00:04:19,899 --> 00:04:22,820
Onko se swap? En tiedä.

59
00:04:22,820 --> 00:04:26,490
Nämä ovat siis kokonaismäärät swap tai ainakin vertailuja sinun täytyy tehdä.

60
00:04:26,490 --> 00:04:29,910
Vaikka et vaihtaa, tarvitset silti verrata arvoja.

61
00:04:29,910 --> 00:04:33,910
Joten on n - 1 vertailut ensimmäisen ajon kautta array.

62
00:04:33,910 --> 00:04:42,050
Jos järjestellä näitä asioita, mennään todella tehdä kuusi asiaa niin asiat pärjää hienosti,

63
00:04:42,050 --> 00:04:44,790
ja sitten minä teen 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Joten järjestämässä näitä summia, haluamme nähdä kuinka monta vertailuja teemme

65
00:04:49,910 --> 00:04:52,700
koko algoritmi.

66
00:04:52,700 --> 00:04:56,550
Joten jos saamme nämä kaverit täällä,

67
00:04:56,550 --> 00:05:07,470
Sitten me vielä vain yhteenlaskua kuitenkin monia vertailuja siellä oli.

68
00:05:07,470 --> 00:05:13,280
Mutta jos me kerätä ne ja me kerätä ne ja me kerätä ne,

69
00:05:13,280 --> 00:05:18,130
se on edelleen sama ongelma. Me vain todeta kyseisiä ryhmiä.

70
00:05:18,130 --> 00:05:22,400
>> Joten nyt olemme yhteenlaskua 3 N: n. Se ei ole vain 3 N: n.

71
00:05:22,400 --> 00:05:27,650
Se on aina olemaan n / 2 n-luvulla.

72
00:05:27,650 --> 00:05:29,430
Joten tässä meillä sattuu olemaan 6.

73
00:05:29,430 --> 00:05:34,830
Jos meillä oli 10 asiaa, niin voisimme tehdä tämän ryhmittymän 5 eri paria asioita

74
00:05:34,830 --> 00:05:37,180
ja lopulta n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Joten olet aina menossa n / 2 n: n, joten tämä me hiukkaakaan ulos n neliö / 2.

76
00:05:45,840 --> 00:05:48,890
Ja niin vaikka se tekijä puoli, joka sattuu tulla

77
00:05:48,890 --> 00:05:54,190
koska se seikka, että läpi jokaisen iteraation aikana array me vertaamme 1 vähemmän

78
00:05:54,190 --> 00:05:58,040
Niin, että miten saamme yli 2, mutta se on silti n: n potenssiin.

79
00:05:58,040 --> 00:06:01,650
Emme välitä vakio tekijä puoli.

80
00:06:01,650 --> 00:06:07,760
Joten paljon Big O tavaraa kuten tämä perustuu vain sellaista tekemässä tällaista matematiikkaa,

81
00:06:07,760 --> 00:06:12,260
laskutoimitusten summia ja geometrisen sarjan juttuja,

82
00:06:12,260 --> 00:06:17,750
mutta useimmat niistä tällä kurssilla ovat melko yksinkertaisia.

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

84
00:06:19,290 --> 00:06:24,430
Miksi lisäys lajitella Omega n? Mitä omega tarkoittaa?

85
00:06:24,430 --> 00:06:27,730
[Kaksi opiskelijaa puhuu kerralla - käsittämätön] >> Joo.

86
00:06:27,730 --> 00:06:30,630
Omega voit ajatella kuin alaraja.

87
00:06:30,630 --> 00:06:36,550
>> Joten ei ole väliä kuinka tehokas lisäyskohdan lajitella algoritmi on,

88
00:06:36,550 --> 00:06:41,810
riippumatta luettelon, joka on hyväksytty vuonna, se on aina verrata ainakin n asioita

89
00:06:41,810 --> 00:06:44,620
tai se on toistaa yli n. asioita.

90
00:06:44,620 --> 00:06:47,280
Miksi näin?

91
00:06:47,280 --> 00:06:51,190
[Opiskelija] Koska jos luettelo on jo järjestetty, sitten läpi ensimmäistä iterointia

92
00:06:51,190 --> 00:06:54,080
voit vain taata, että ensimmäinen osa on vähiten,

93
00:06:54,080 --> 00:06:56,490
ja toisen iteroinnin voit vain varmistaa kaksi ensimmäistä ovat

94
00:06:56,490 --> 00:07:00,010
koska et tiedä, että loput lajitellaan. >> Joo.

95
00:07:00,010 --> 00:07:08,910
Jos ohitat täysin järjestetty luettelo, ainakin sinun täytyy mennä yli kaikki elementit

96
00:07:08,910 --> 00:07:12,180
nähdä, että mitään ei tarvitse liikutella.

97
00:07:12,180 --> 00:07:14,720
Joten kulkevan listan ja sanoi oi, tämä on jo lajiteltu,

98
00:07:14,720 --> 00:07:18,240
on mahdotonta tietää, se lajitellaan kunnes tarkistaa kunkin elementin

99
00:07:18,240 --> 00:07:20,660
nähdä, että ne ovat lajiteltu järjestyksessä.

100
00:07:20,660 --> 00:07:25,290
Joten alaraja sijoittamista tavallaan on Omega n.

101
00:07:25,290 --> 00:07:28,210
Mitä pahimmassa tapauksessa käyntiaika merge lajitella,

102
00:07:28,210 --> 00:07:31,390
Pahimmassa tapauksessa on iso O uudelleen?

103
00:07:31,390 --> 00:07:37,660
Joten pahimmassa tapauksessa miten merge sort ajaa?

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

105
00:07:43,690 --> 00:07:49,990
Nopein yleinen lajittelualgoritmeja ovat n log n. Et voi tehdä paremmin.

106
00:07:51,930 --> 00:07:55,130
>> On olemassa erityisiä tapauksia, ja jos meillä on aikaa tänään - mutta luultavasti won't -

107
00:07:55,130 --> 00:07:59,330
näimme, joka tekee paremmin kuin n log n.

108
00:07:59,330 --> 00:08:04,050
Mutta yleisessä tapauksessa, et voi tehdä paremmin kuin n log n.

109
00:08:04,050 --> 00:08:09,680
Ja yhdistää tavallaan sattuu olemaan yksi sinun pitäisi tietää tämä tietenkin, että on n log n.

110
00:08:09,680 --> 00:08:13,260
Ja niin me oikeastaan ​​täytäntöönpanossa että tänään.

111
00:08:13,260 --> 00:08:18,070
Ja lopuksi, on enintään kolme virkettä, miten valinta tavallaan työtä?

112
00:08:18,070 --> 00:08:20,370
Onko joku haluaa vastata, ja minä laske teidän lauseita

113
00:08:20,370 --> 00:08:22,390
sillä jos menemme yli 3 -

114
00:08:25,530 --> 00:08:28,330
Muistaako kukaan valinta lajitella?

115
00:08:31,280 --> 00:08:37,809
Valinta sort on yleensä melko helppo muistaa vain nimestä.

116
00:08:37,809 --> 00:08:45,350
Sinä vain toistaa yli array, löytää mitä suurin arvo on tai pienin -

117
00:08:45,350 --> 00:08:47,290
missä järjestyksessä olet lajittelu sisään

118
00:08:47,290 --> 00:08:50,750
Joten sanokaamme me lajittelun pienimmästä eniten.

119
00:08:50,750 --> 00:08:55,250
Voit toistaa yli array, etsivät riippumatta minimi elementti on,

120
00:08:55,250 --> 00:08:59,750
valitse se, ja sitten vain vaihtaa se mitä on ensimmäinen paikka.

121
00:08:59,750 --> 00:09:04,090
Ja sitten toisen kulkevat array, etsiä pienin alkio uudelleen,

122
00:09:04,090 --> 00:09:07,490
valitse se, ja sitten vaihtaa se mitä toisessa asennossa.

123
00:09:07,490 --> 00:09:10,650
Joten me vain poiminta ja valitsemalla vähimmäisarvot

124
00:09:10,650 --> 00:09:16,050
ja työntämällä ne etuosaan array, kunnes se on järjestetty.

125
00:09:19,210 --> 00:09:21,560
Kysymyksiä tästä?

126
00:09:21,560 --> 00:09:25,710
>> Nämä väistämättä näkyvät lomakkeet täytyy täyttää, kun olet esittää PSET.

127
00:09:29,010 --> 00:09:32,360
Nämä ovat pohjimmiltaan vastauksia näihin.

128
00:09:32,360 --> 00:09:34,230
Okei, joten nyt koodaus ongelmia.

129
00:09:34,230 --> 00:09:40,140
Olen jo lähettänyt sähköpostissa - Näkikö kukaan saa sitä sähköpostilla? Okei.

130
00:09:40,140 --> 00:09:46,630
Olen jo lähetetty sähköpostissa tilaa, että aiomme käyttää,

131
00:09:46,630 --> 00:09:52,120
ja jos klikkaat nimeni - niin mielestäni aion olla pohjassa

132
00:09:52,120 --> 00:09:57,170
koska taaksepäin R - mutta jos klikkaa nimeni näet 2 revisions.

133
00:09:57,170 --> 00:10:02,650
Versio 1 aiotaan Olen jo kopioida ja liittää koodi Spaces

134
00:10:02,650 --> 00:10:06,900
Haun asia aiot tarvitse toteuttaa.

135
00:10:06,900 --> 00:10:10,540
Ja Versio 2 on tavallaan asia, että toteutamme sen jälkeen.

136
00:10:10,540 --> 00:10:15,770
Joten voit napsauttaa minun Versio 1 ja työskennellä siellä.

137
00:10:17,350 --> 00:10:22,060
Ja nyt me haluamme toteuttaa binäärihakupuu.

138
00:10:22,060 --> 00:10:26,470
>> Haluaako joku vain antaa pseudokoodi korkean tason selitys

139
00:10:26,470 --> 00:10:31,440
mitä aiomme pitää tehdä haun? Joo.

140
00:10:31,440 --> 00:10:36,170
[Opiskelija] Sinä vain ottaa keskelle array ja katso jos mitä etsit

141
00:10:36,170 --> 00:10:38,650
on pienempi kuin tai enemmän.

142
00:10:38,650 --> 00:10:41,080
Ja jos se on vähemmän, menet puoli, joka on vähemmän,

143
00:10:41,080 --> 00:10:44,750
ja jos se on enemmän, voit mennä puoli, joka on enemmän ja Voisitko toistaa kunnes vain yksi asia.

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

145
00:10:46,570 --> 00:10:51,320
Huomaa, että numerot taulukko on jo lajiteltu,

146
00:10:51,320 --> 00:10:57,190
ja niin se tarkoittaa, että voimme hyödyntää tätä ja voisimme tarkista ensin,

147
00:10:57,190 --> 00:11:00,390
Okei, etsin numero 50.

148
00:11:00,390 --> 00:11:03,720
Joten voin mennä keskelle.

149
00:11:03,720 --> 00:11:07,380
Keskellä on vaikea määritellä, kun se on vielä monia asioita,

150
00:11:07,380 --> 00:11:10,820
mutta sanotaanko me aina katkaista sen keskelle.

151
00:11:10,820 --> 00:11:14,420
Joten tässä meillä on 8 asioita, joten keskimmäinen olisi 16.

152
00:11:14,420 --> 00:11:17,330
Etsin 50, joten 50 on suurempi kuin 16.

153
00:11:17,330 --> 00:11:21,310
Joten nyt voin periaatteessa hoitaa minun array kuin nämä tekijät.

154
00:11:21,310 --> 00:11:23,450
Voin heittää pois kaiken 16 yli.

155
00:11:23,450 --> 00:11:27,440
Nyt minun array on vain nämä 4 elementtiä, ja toistan.

156
00:11:27,440 --> 00:11:31,910
Joten haluan löytää keskeltä uudestaan, mikä tulee olemaan 42.

157
00:11:31,910 --> 00:11:34,730
42 on alle 50, joten voin heittää pois nämä kaksi elementtiä.

158
00:11:34,730 --> 00:11:36,890
Tämä on minun jäljellä array.

159
00:11:36,890 --> 00:11:38,430
Aion löytää keskeltä uudestaan.

160
00:11:38,430 --> 00:11:42,100
Luulen 50 oli huono esimerkki, koska olin aina heittää pois asioita vasemmalle,

161
00:11:42,100 --> 00:11:48,280
mutta samalla mitalla, jos etsin jotain

162
00:11:48,280 --> 00:11:52,100
ja se on pienempi kuin elementin Olen tällä hetkellä katsot,

163
00:11:52,100 --> 00:11:55,080
Sitten aion heittää pois kaiken oikealle.

164
00:11:55,080 --> 00:11:58,150
Joten nyt meidän täytyy toteuttaa se.

165
00:11:58,150 --> 00:12:02,310
Huomaa, että meidän kulkea koko.

166
00:12:02,310 --> 00:12:06,730
Voimme myös ei tarvitse koodata koko.

167
00:12:06,730 --> 00:12:11,640
Joten jos pääsemme eroon että # define -

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

169
00:12:21,430 --> 00:12:27,180
Miten kauniisti selvittää, mitä numeroiden koko array hetkellä on?

170
00:12:27,180 --> 00:12:30,950
>> Kuinka monta elementtiä ovat numeroita array?

171
00:12:30,950 --> 00:12:33,630
[Opiskelija] Numbers, suluissa. Pituus?

172
00:12:33,630 --> 00:12:36,600
[Bowden] Tämä ei esiinny C.

173
00:12:36,600 --> 00:12:38,580
Tarvitsevat. Pituus.

174
00:12:38,580 --> 00:12:42,010
Arrays ei ole ominaisuuksia, joten ei ole mitään pituus omaisuutta pakat

175
00:12:42,010 --> 00:12:45,650
joka vain antaa sinulle kuitenkin kauan se sattuu olemaan.

176
00:12:48,180 --> 00:12:51,620
[Opiskelija] Katso kuinka paljon muistia se on ja jakaa kuinka paljon - >> Joo.

177
00:12:51,620 --> 00:12:55,810
Joten kuinka voimme nähdä kuinka paljon muistia se on? >> [Opiskelija] sizeof. >> Joo, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof on operaattori, joka tulee palauttaa numeroiden koko jono.

179
00:13:01,680 --> 00:13:10,060
Ja se tulee olemaan kuitenkin monta kokonaislukua on aikoja koko kokonaisluku

180
00:13:10,060 --> 00:13:14,050
sillä se, kuinka paljon muistia se todella aloittamisesta.

181
00:13:14,050 --> 00:13:17,630
Joten jos haluan monia asioita array,

182
00:13:17,630 --> 00:13:20,560
Sitten aion haluat jakaa koolla kokonaisluku.

183
00:13:22,820 --> 00:13:26,010
Okei. Niin että antaa minulle kulkea koko täällä.

184
00:13:26,010 --> 00:13:29,430
Miksi minun täytyy kulkea koko ollenkaan?

185
00:13:29,430 --> 00:13:38,570
Miksi en voi vain tehdä tänne int koko = sizeof (heinäsuovasta) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Miksi tämä ei toimi?

187
00:13:41,490 --> 00:13:44,470
[Opiskelija] Se ei ole globaali muuttuja.

188
00:13:44,470 --> 00:13:51,540
[Bowden] heinäsuovasta olemassa, ja olemme ohimennen numerot heinäsuovasta,

189
00:13:51,540 --> 00:13:54,700
ja tämä on eräänlainen esikuva mitä on tulossa. Joo.

190
00:13:54,700 --> 00:14:00,170
[Opiskelija] heinäsuovasta on vain viittaus siihen, niin se palaisi kuinka suuri tämä viittaus on.

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

192
00:14:02,150 --> 00:14:09,000
Epäilen luennossa, että olet nähnyt pino vielä todella, eikö?

193
00:14:09,000 --> 00:14:11,270
Olemme juuri puhuneet siitä.

194
00:14:11,270 --> 00:14:16,090
Joten pino on, jos kaikki muuttujat aiotaan varastoida.

195
00:14:16,090 --> 00:14:19,960
>> Jokainen muisti, joka on varattu paikallisia muuttujia on menossa pinoon

196
00:14:19,960 --> 00:14:24,790
ja jokaisen toiminnon saa oman tilan pino, oma pino runko on mitä se on nimeltään.

197
00:14:24,790 --> 00:14:31,590
Niin tärkein on sen pinokehys, ja sen sisällä on menossa olemassa tämän numerot array,

198
00:14:31,590 --> 00:14:34,270
ja se tulee olemaan koon sizeof (numerot).

199
00:14:34,270 --> 00:14:38,180
Se tulee olemaan kooltaan numeroiden jaettuna kokoa elementtejä,

200
00:14:38,180 --> 00:14:42,010
mutta kaikki elämänsä sisällä tärkeimmät n pinokehys.

201
00:14:42,010 --> 00:14:45,190
Kun me kutsumme haussa, saa oman pinokehys,

202
00:14:45,190 --> 00:14:48,840
omaa tilaa tallentaa kaikki paikalliset muuttujat.

203
00:14:48,840 --> 00:14:56,420
Mutta nämä väitteet - joten heinäsuovasta ei kopio tästä koko ryhmän.

204
00:14:56,420 --> 00:15:00,990
Emme luovuta koko levyjärjestelmän kopioida haku.

205
00:15:00,990 --> 00:15:04,030
Se vain kulkee viittaus kyseiseen array.

206
00:15:04,030 --> 00:15:11,470
Joten haku voi käyttää näitä numeroita läpi tämä viittaus.

207
00:15:11,470 --> 00:15:17,100
Se käyttää yhä asioita, jotka elävät sisällä tärkeimpien n pinokehys,

208
00:15:17,100 --> 00:15:22,990
mutta pohjimmiltaan, kun saamme osoittimia, joiden pitäisi olla pian,

209
00:15:22,990 --> 00:15:24,980
tämä on mitä osoittimet ovat.

210
00:15:24,980 --> 00:15:29,400
Osoittimet ovat vain viittauksia asioita, ja voit käyttää osoittimia pääsyn asioita

211
00:15:29,400 --> 00:15:32,030
jotka ovat muiden muassa "pino kehyksiä.

212
00:15:32,030 --> 00:15:37,660
Joten vaikka numerot on paikallinen tärkein, voimme silti käyttää sitä kautta osoitin.

213
00:15:37,660 --> 00:15:41,770
Mutta koska se on vain osoitin ja se on vain viite,

214
00:15:41,770 --> 00:15:45,040
sizeof (heinäsuovasta) palaa aivan koko viite itse.

215
00:15:45,040 --> 00:15:47,950
Se ei palauta koko asia se osoittaa.

216
00:15:47,950 --> 00:15:51,110
Se ei palauta todellinen koko numeroita.

217
00:15:51,110 --> 00:15:55,660
Ja niin tämä ei tule toimimaan haluamme sen.

218
00:15:55,660 --> 00:15:57,320
>> Kysymyksiä tästä?

219
00:15:57,320 --> 00:16:03,250
Osoittimet on mennyt huomattavasti enemmän kammottava yksityiskohtia tulevien viikkojen aikana.

220
00:16:06,750 --> 00:16:13,740
Ja siksi paljon asioita, jotka näet, kaikkein haku asioita tai lajitella asioita,

221
00:16:13,740 --> 00:16:16,990
he lähes kaikki menossa tarvitse tehdä todellinen taulukon koko,

222
00:16:16,990 --> 00:16:20,440
koska C, meillä ei ole aavistustakaan, mitä taulukon koko on.

223
00:16:20,440 --> 00:16:22,720
Sinun täytyy manuaalisesti siirtää sen sisään

224
00:16:22,720 --> 00:16:27,190
Ja et voi manuaalisesti siirtää koko joukko, koska olet vain ohimennen viite

225
00:16:27,190 --> 00:16:30,390
ja se ei voi saada koko vertailutasosta.

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

227
00:16:32,300 --> 00:16:38,160
Joten nyt me haluamme toteuttaa mitä selitettiin ennen.

228
00:16:38,160 --> 00:16:41,530
Voit työskennellä sen hetken,

229
00:16:41,530 --> 00:16:45,250
ja sinun ei tarvitse pelätä kaiken täydellisesti 100% työskentely.

230
00:16:45,250 --> 00:16:51,410
Vain kirjoittaa ylös puoli pseudokoodi miten luulet sen pitäisi toimia.

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

232
00:16:53,630 --> 00:16:56,350
Ei tarvitse olla täysin tehdä tätä vielä.

233
00:16:56,350 --> 00:17:02,380
Mutta ei kukaan Viihdyn mitä he ovat tähän asti,

234
00:17:02,380 --> 00:17:05,599
jotain voimme työskennellä yhdessä?

235
00:17:05,599 --> 00:17:09,690
Haluaako joku tehdä vapaaehtoistyötä? Tai en valitse sattumanvaraisesti.

236
00:17:12,680 --> 00:17:18,599
Sen ei tarvitse olla oikeus kaikilla mittareilla, mutta emme voi muuttaa osaksi toimivaan tilaan.

237
00:17:18,599 --> 00:17:20,720
[Opiskelija] Toki. >> Okei.

238
00:17:20,720 --> 00:17:27,220
Joten voit säästää tarkistuksen klikkaamalla pikku Tallenna-kuvaketta.

239
00:17:27,220 --> 00:17:29,950
Olet Ramya, eikö? >> [Opiskelija] Joo. >> [Bowden] Okei.

240
00:17:29,950 --> 00:17:35,140
Joten nyt voin nähdä tarkistamista ja jokainen voi vetää tarkistamista.

241
00:17:35,140 --> 00:17:38,600
Ja täällä meillä on - Okei.

242
00:17:38,600 --> 00:17:43,160
Niin Ramya meni rekursiivinen ratkaisu, joka on ehdottomasti pätevä ratkaisu.

243
00:17:43,160 --> 00:17:44,970
On kaksi tapaa voit tehdä tämän ongelman.

244
00:17:44,970 --> 00:17:48,060
Voit joko tehdä sen toistuvasti tai rekursiivisesti.

245
00:17:48,060 --> 00:17:53,860
Useimmat ongelmat kohtaat voidaan tehdä rekursiivisesti voi tehdä myös iteratiivisesti.

246
00:17:53,860 --> 00:17:58,510
Joten tässä olemme tehneet sen rekursiivisesti.

247
00:17:58,510 --> 00:18:03,730
>> Onko joku haluaa määritellä, mitä se tarkoittaa tehdä toiminnon rekursiivinen?

248
00:18:07,210 --> 00:18:08,920
[Opiskelija] Kun olet funktion kutsua itseään

249
00:18:08,920 --> 00:18:13,470
ja sitten soittaa itse kunnes se tulee ulos tosi ja totta. >> Joo.

250
00:18:13,470 --> 00:18:17,680
Rekursiivinen funktio on vain funktio, joka kutsuu itseään.

251
00:18:17,680 --> 00:18:24,140
On kolme suurta asiaa, että rekursiivinen funktio on.

252
00:18:24,140 --> 00:18:27,310
Ensimmäinen on tietysti se kutsuu itseään.

253
00:18:27,310 --> 00:18:29,650
Toinen on perustapaus.

254
00:18:29,650 --> 00:18:33,390
Niin jossain vaiheessa funktion täytyy pysäyttää kutsuu itseään,

255
00:18:33,390 --> 00:18:35,610
ja sitähän perustapaus on.

256
00:18:35,610 --> 00:18:43,860
Joten tässä me tiedämme, että meidän pitäisi lopettaa, meidän pitäisi luopua meidän haku

257
00:18:43,860 --> 00:18:48,150
kun alku vastaa loppua - ja me mennä yli, mitä se tarkoittaa.

258
00:18:48,150 --> 00:18:52,130
Mutta lopulta, viimeinen asia, joka on tärkeä rekursiiviset funktiot:

259
00:18:52,130 --> 00:18:59,250
toimintoja on jotenkin lähestyä perustapaus.

260
00:18:59,250 --> 00:19:04,140
Kuten jos et itse päivittää mitään, kun teet toisen rekursiivinen puhelun,

261
00:19:04,140 --> 00:19:07,880
jos olet kirjaimellisesti vain kutsumalla funktiota uudelleen samat argumentit

262
00:19:07,880 --> 00:19:10,130
eikä globaalien muuttujien ovat muuttuneet tai mitään,

263
00:19:10,130 --> 00:19:14,430
et koskaan pääse perustapaus, jolloin se on paha.

264
00:19:14,430 --> 00:19:17,950
Se tulee olemaan loputtoman rekursion ja pinon ylivuoto.

265
00:19:17,950 --> 00:19:24,330
Mutta tässä näemme, että päivitys tapahtuu, koska me Päivitämme aloittaa + loppuun / 2,

266
00:19:24,330 --> 00:19:28,180
olemme päivittää loppua argumentti täällä, me päivittäminen alusta argumentti täällä.

267
00:19:28,180 --> 00:19:32,860
Joten kaikki rekursiivinen puhelut Päivitämme jotain. Okei.

268
00:19:32,860 --> 00:19:38,110
Haluatko kävellä meille läpi ratkaisu? >> Toki.

269
00:19:38,110 --> 00:19:44,270
Käytän SearchHelp niin että aina kun teen tätä toimintoa puhelun

270
00:19:44,270 --> 00:19:47,910
Olen alusta missä Etsin pakassa ja loppu

271
00:19:47,910 --> 00:19:49,380
, missä Etsin array.

272
00:19:49,380 --> 00:19:55,330
>> Jokaisessa vaiheessa, jossa se sanoo se keskimmäinen elementti, joka on alku + loppu / 2,

273
00:19:55,330 --> 00:19:58,850
että sama mitä etsimme?

274
00:19:58,850 --> 00:20:04,650
Ja jos on, niin löysimme sen, ja luulen, että saa siirtää ylös tasoa rekursion.

275
00:20:04,650 --> 00:20:12,540
Ja jos se ei ole totta, niin voimme tarkistaa onko keskimmäinen arvo joukko on liian suuri,

276
00:20:12,540 --> 00:20:19,320
jolloin katsomme vasen puoli array menemällä alusta keskeltä indeksi.

277
00:20:19,320 --> 00:20:22,710
Ja muuten teemme loppu puoli.

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

279
00:20:24,740 --> 00:20:27,730
Kuulostaa hyvältä.

280
00:20:27,730 --> 00:20:36,640
Okei, joten pari asiaa, ja itse asiassa, tämä on erittäin korkean tason juttu

281
00:20:36,640 --> 00:20:41,270
että sinun ei tarvitse koskaan tietää tämän kurssin, mutta se on totta.

282
00:20:41,270 --> 00:20:46,080
Rekursiivinen toimintoja, aina kuulla, että he ovat huono sopimus

283
00:20:46,080 --> 00:20:51,160
koska jos rekursiivisesti kutsua itseäsi liian monta kertaa, saat pinon ylivuoto

284
00:20:51,160 --> 00:20:54,990
sillä, kuten aiemmin sanoin, jokainen toiminto saa oman pinokehys.

285
00:20:54,990 --> 00:20:59,500
Joten jokainen kutsu rekursiivinen funktio saa oman pinokehys.

286
00:20:59,500 --> 00:21:04,140
Joten jos teet 1000 rekursiivinen puheluja, saat 1000 pino kehyksiä,

287
00:21:04,140 --> 00:21:08,390
ja nopeasti te johtaa liian monta pino kehyksiä ja asiat vain rikkoa.

288
00:21:08,390 --> 00:21:13,480
Joten siksi rekursiiviset toiminnot ovat yleensä huonoja.

289
00:21:13,480 --> 00:21:19,370
Mutta on mukava osajoukko rekursiiviset funktiot kutsutaan hännän rekursiiviset toimintoja,

290
00:21:19,370 --> 00:21:26,120
ja tämä sattuu olemaan esimerkiksi sellainen, jossa jos kääntäjä huomaa tämän

291
00:21:26,120 --> 00:21:29,920
ja se pitäisi mielestäni - in clang jos ohitat sen, O2 lippu

292
00:21:29,920 --> 00:21:33,250
se huomaa tämä on häntä rekursiivinen ja tehdä asioita hyvin.

293
00:21:33,250 --> 00:21:40,050
>> Se käyttää samaa pinokehys yhä uudelleen ja uudelleen kullekin rekursiivista puhelun.

294
00:21:40,050 --> 00:21:47,010
Ja niin, koska käytät samaa pinokehys, sinun ei tarvitse pelätä

295
00:21:47,010 --> 00:21:51,690
koskaan pino täynnä, ja samaan aikaan, kuten sanoit aiemmin,

296
00:21:51,690 --> 00:21:56,380
Jos kerran palaat totta, se on palautettava kaikkia näitä pinon kehyksiä

297
00:21:56,380 --> 00:22:01,740
ja 10. kutsun SearchHelp on palata 9th, on palata 8..

298
00:22:01,740 --> 00:22:05,360
Niin että ei tarvitse tapahtua, kun toimintoja häntä rekursiivisia.

299
00:22:05,360 --> 00:22:13,740
Ja niin mitä tekee tämä toiminto häntä rekursiivinen on ilmoitus, että minkä tahansa puhelun searchHelp

300
00:22:13,740 --> 00:22:18,470
rekursiivinen puhelu, että se tekee mitä se palaa.

301
00:22:18,470 --> 00:22:25,290
Niinpä ensimmäisen puhelun SearchHelp, me joko välittömästi palauttaa false,

302
00:22:25,290 --> 00:22:29,590
välittömästi palauttaa true tai teemme rekursiivinen kutsu SearchHelp

303
00:22:29,590 --> 00:22:33,810
missä me olemme palaamassa mitä se puhelu on palaamassa.

304
00:22:33,810 --> 00:22:51,560
Ja me ei tehdä tätä, jos teimme jotain int x = SearchHelp, paluu x * 2,

305
00:22:51,560 --> 00:22:55,440
vain joitakin satunnaisia ​​muutoksia.

306
00:22:55,440 --> 00:23:01,470
>> Joten nyt tämä rekursiivinen puhelun, tämä int x = SearchHelp rekursiivinen puhelun

307
00:23:01,470 --> 00:23:05,740
ei enää häntää rekursiivinen, koska se todella ei tarvitse palata

308
00:23:05,740 --> 00:23:10,400
takaisin edelliseen pinokehys niin että edellinen puhelu toiminto

309
00:23:10,400 --> 00:23:13,040
voi sitten tehdä jotain tuottoarvo.

310
00:23:13,040 --> 00:23:22,190
Joten tämä ei ole häntää rekursiivinen, mutta mitä meillä oli ennen on mukavasti häntä rekursiivinen. Joo.

311
00:23:22,190 --> 00:23:27,000
[Opiskelija] Pitäisikö toisen tukiaseman tapauksessa tarkistetaan ensin

312
00:23:27,000 --> 00:23:30,640
sillä voisi olla tilanne, jossa kun ohitat sen väitteen

313
00:23:30,640 --> 00:23:35,770
olet start = lopussa, mutta ne ovat neulan arvoa.

314
00:23:35,770 --> 00:23:47,310
Kysymystä emme voi törmätä jos pää on neula arvo

315
00:23:47,310 --> 00:23:52,000
tai start = loppu, asianmukaisesti, aloita = loppu

316
00:23:52,000 --> 00:23:59,480
ja et ole itse tarkistanut kyseisen arvon vielä,

317
00:23:59,480 --> 00:24:03,910
sitten aloittaa + pää / 2 on vain olemaan sama arvo.

318
00:24:03,910 --> 00:24:07,890
Mutta olemme jo palannut vääriä emmekä koskaan tarkastetaan arvoa.

319
00:24:07,890 --> 00:24:14,240
Joten ainakin, että ensimmäinen puhelu, jos koko on 0, niin haluamme palauttaa false.

320
00:24:14,240 --> 00:24:17,710
Mutta jos koko on 1, niin käynnistys ei tule yhtä loppuun,

321
00:24:17,710 --> 00:24:19,820
ja me ainakin tarkistaa yksi elementti.

322
00:24:19,820 --> 00:24:26,750
Mutta mielestäni olet oikeassa, että voimme päätyä tapauksessa aloittaa + loppuun / 2,

323
00:24:26,750 --> 00:24:31,190
käynnistys päätyy on sama kuin alku + lopussa / 2,

324
00:24:31,190 --> 00:24:35,350
mutta emme koskaan tarkistanut, että elementti.

325
00:24:35,350 --> 00:24:44,740
>> Joten jos ensin tarkistettava keskimmäinen elementti arvo etsimme,

326
00:24:44,740 --> 00:24:47,110
voimme heti palata totta.

327
00:24:47,110 --> 00:24:50,740
If he yhtä, niin ei ole mitään järkeä jatkaa

328
00:24:50,740 --> 00:24:58,440
koska olemme juuri menossa päivittää tapauksessa olemme yhden elementin array.

329
00:24:58,440 --> 00:25:01,110
Jos tämä yksittäinen tekijä ei ole yksi etsimme,

330
00:25:01,110 --> 00:25:03,530
Sitten kaikki on väärin. Joo.

331
00:25:03,530 --> 00:25:08,900
[Opiskelija] Olennaista on, että koska koko on itse asiassa suurempi kuin elementtien määrä array,

332
00:25:08,900 --> 00:25:13,070
on jo offset - >> Niin käy koko -

333
00:25:13,070 --> 00:25:19,380
[Opiskelija] Sano, jos matriisi oli koko 0, niin SearchHelp todella tarkistaa haystack 0

334
00:25:19,380 --> 00:25:21,490
ensimmäisen puhelun.

335
00:25:21,490 --> 00:25:25,300
Array koko on 0, joten 0 on - >> Joo.

336
00:25:25,300 --> 00:25:30,750
On toinen asia, että - se voisi olla hyvä. Ajatellaanpa.

337
00:25:30,750 --> 00:25:40,120
Joten jos ryhmä oli 10-elementtejä ja keskimmäinen aiomme tarkistaa indeksinumero 5,

338
00:25:40,120 --> 00:25:45,700
joten olemme tarkkailun 5, ja sanotaan, että arvo on pienempi.

339
00:25:45,700 --> 00:25:50,720
Joten me heittää kaiken pois 5 eteenpäin.

340
00:25:50,720 --> 00:25:54,030
Niin alkaa + pää / 2 tulee olemaan uusi loppu,

341
00:25:54,030 --> 00:25:57,450
niin joo, se on aina menossa pysyä päättymisen jälkeen jono.

342
00:25:57,450 --> 00:26:03,570
Jos se on, jos se on parillinen tai pariton, niin voisimme tarkistaa, sanoa, 4,

343
00:26:03,570 --> 00:26:05,770
mutta olemme silti heittää pois -

344
00:26:05,770 --> 00:26:13,500
Niin joo, pää on aina olemaan pidemmälle todellisen loppuun array.

345
00:26:13,500 --> 00:26:18,350
Eli elementit keskitymme, pää on aina olemaan yksi jälkeen.

346
00:26:18,350 --> 00:26:24,270
Ja niin jos alusta ei koskaan yhtä loppuun, olemme joukko koko 0.

347
00:26:24,270 --> 00:26:35,600
>> Toinen asia Ajattelin on Päivitämme voidaan aloittaa aloittaa + loppuun / 2,

348
00:26:35,600 --> 00:26:44,020
joten tämä on asia, joka minulla on ongelmia, jos aloittaa + pää / 2

349
00:26:44,020 --> 00:26:46,820
on elementti olemme tarkkailun.

350
00:26:46,820 --> 00:26:58,150
Sanotaan meillä oli 10-elementti array. Whatever.

351
00:26:58,150 --> 00:27:03,250
Niin alkaa + pää / 2 tulee olemaan jotain tällaista yksi,

352
00:27:03,250 --> 00:27:07,060
ja jos se ei ole arvoa, sanovat haluamme päivittää.

353
00:27:07,060 --> 00:27:10,060
Arvo on suurempi, joten haluamme tarkastella tätä puolta array.

354
00:27:10,060 --> 00:27:15,910
Joten miten olet päivittämässä alku, me päivittäminen alkaa nyt olla tätä elementtiä.

355
00:27:15,910 --> 00:27:23,790
Mutta tämä voi silti toimia, tai ainakin voit tehdä alku + loppu / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Opiskelija] Sinun ei tarvitse aloittaa + pää [kuulumattomissa] >> Joo.

357
00:27:27,850 --> 00:27:33,240
Olemme jo tarkistanut tämän elementin ja tietää se ei ole yksi etsimme.

358
00:27:33,240 --> 00:27:36,800
Joten meidän ei tarvitse päivittää alkaa olla tätä elementtiä.

359
00:27:36,800 --> 00:27:39,560
Voimme vain ohittaa sen ja päivittää alkavat olla tätä elementtiä.

360
00:27:39,560 --> 00:27:46,060
Ja onko koskaan tapaus, sanotaanko, että tämä oli varten

361
00:27:46,060 --> 00:27:53,140
niin käynnistä olisi tämän käynnistämällä + pää / 2 olisi tässä,

362
00:27:53,140 --> 00:28:00,580
alkaa + loppu - Joo, mielestäni se voi päätyä loputtoman rekursion.

363
00:28:00,580 --> 00:28:12,690
Sanotaan se on vain joukko kokoa 2 tai joukko koko 1. Mielestäni tämä toimii.

364
00:28:12,690 --> 00:28:19,490
Joten nyt, alku on se elementti, ja loppu on 1 sen ulkopuolella.

365
00:28:19,490 --> 00:28:24,110
Joten elementti, että me aiomme tarkistaa tämä yksi,

366
00:28:24,110 --> 00:28:29,400
ja sitten kun me päivittää alusta, olemme päivittäminen alkaa olla 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
joka tulee päättymään meidät takaisin alkaa olla tätä elementtiä.

368
00:28:33,160 --> 00:28:36,210
>> Joten me tarkistaa saman elementin uudestaan ​​ja uudestaan.

369
00:28:36,210 --> 00:28:43,310
Joten tämä on asia, jossa jokainen rekursiivinen puhelu on todella päivittää jotain.

370
00:28:43,310 --> 00:28:48,370
Joten meidän täytyy tehdä alku + loppu / 2 + 1, tai muuten siellä asia

371
00:28:48,370 --> 00:28:50,710
jos emme oikeastaan ​​päivittää alkua.

372
00:28:50,710 --> 00:28:53,820
Jokainen nähdä, että?

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

374
00:28:56,310 --> 00:29:03,860
Onko kellään kysyttävää tähän ratkaisuun tai enemmän kommentteja?

375
00:29:05,220 --> 00:29:10,280
Okei. Onko kellään iteratiivinen ratkaisu, että me kaikki voimme katsoa?

376
00:29:17,400 --> 00:29:20,940
Oliko me kaikki teemme sen rekursiivisesti?

377
00:29:20,940 --> 00:29:25,950
Tai myös Oletan, jos olet avannut omansa, niin saatat olla ohittaa teidän edellinen.

378
00:29:25,950 --> 00:29:28,810
Onko se automaattisesti tallentaa? En ole varma.

379
00:29:35,090 --> 00:29:39,130
Onko kellään iteratiivinen?

380
00:29:39,130 --> 00:29:42,430
Voimme kävellä sen läpi yhdessä, jos ei.

381
00:29:46,080 --> 00:29:48,100
Ajatus tulee olemaan sama.

382
00:30:00,260 --> 00:30:02,830
Iteratiivinen ratkaisu.

383
00:30:02,830 --> 00:30:07,140
Aiomme haluavat periaatteessa tehdä sama ajatus

384
00:30:07,140 --> 00:30:16,530
jossa haluamme seurata uuden vuoden jono ja uusi alku on array

385
00:30:16,530 --> 00:30:18,510
ja tehdä sen uudestaan ​​ja uudestaan.

386
00:30:18,510 --> 00:30:22,430
Ja jos me olemme tarkkailemalla kuin alku ja loppu koskaan leikkaavat,

387
00:30:22,430 --> 00:30:29,020
silloin emme löydä sitä, ja me voimme palata vääriä.

388
00:30:29,020 --> 00:30:37,540
Joten miten voin tehdä sen? Kellään ehdotuksia tai koodia minun vetää ylös?

389
00:30:42,190 --> 00:30:47,450
[Opiskelija] Do while-silmukka. >> Joo.

390
00:30:47,450 --> 00:30:49,450
Olet menossa halua tehdä silmukka.

391
00:30:49,450 --> 00:30:51,830
>> Oliko sinulla koodin voisin vetää ylös, tai mitä aioit ehdottaa?

392
00:30:51,830 --> 00:30:56,340
[Opiskelija] Luulen niin. >> Selvä. Tämä helpottaa asioita. Mikä oli nimesi?

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

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

395
00:31:04,190 --> 00:31:13,200
Matala me kutsuimme aloittaa ennen.

396
00:31:13,200 --> 00:31:17,080
Up ei ole aivan mitä vaadimme loppua ennen.

397
00:31:17,080 --> 00:31:22,750
Oikeastaan, loppu on nyt sisällä array. Se osa meidän pitäisi harkita.

398
00:31:22,750 --> 00:31:26,890
Niin alhainen on 0, ylös on koko array - 1,

399
00:31:26,890 --> 00:31:34,780
ja nyt looping, ja olemme tarkkailun -

400
00:31:34,780 --> 00:31:37,340
Oletan, voit kävellä sen läpi.

401
00:31:37,340 --> 00:31:41,420
Mikä oli sinun ajattelu kautta? Kävele meihin koodi.

402
00:31:41,420 --> 00:31:49,940
[Opiskelija] Toki. Katsokaa heinäsuovasta arvo keskeltä ja verrata sitä neulaa.

403
00:31:49,940 --> 00:31:58,520
Joten jos se on suurempi kuin neula, sitten haluat - oh, todella, että pitäisi olla taaksepäin.

404
00:31:58,520 --> 00:32:05,180
Olet menossa halua heittää pois oikea puoli, ja niin joo, se olisi tie.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Joten tämä olisi vähemmän? Onko se mitä sanoit? >> [Opiskelija] Joo.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Okei. Vähemmän.

407
00:32:10,390 --> 00:32:15,700
Joten jos mitä me tarkastelemme on pienempi kuin mitä me haluamme,

408
00:32:15,700 --> 00:32:19,410
Sitten joo, me haluamme heittää pois vasen puoli,

409
00:32:19,410 --> 00:32:22,210
mikä tarkoittaa Päivitämme kaiken harkitset

410
00:32:22,210 --> 00:32:26,610
siirtämällä alhainen oikealle jono.

411
00:32:26,610 --> 00:32:30,130
Tämä näyttää hyvältä.

412
00:32:30,130 --> 00:32:34,550
Mielestäni se on sama asia, sanoimme edellinen,

413
00:32:34,550 --> 00:32:49,760
jos jos pieni on 0 ja ylös on 1, niin pieni + ylös / 2 on menossa perustamaan olla saman uudestaan.

414
00:32:49,760 --> 00:32:53,860
>> Ja vaikka se ei pidä paikkaansa, se on vielä tehokkaampi ainakin

415
00:32:53,860 --> 00:32:57,630
vain heittää pois elementin me vain katsoi jonka tiedämme olevan väärin.

416
00:32:57,630 --> 00:33:03,240
Niin pieni + ylös / 2 + 1 - >> [opiskelija] Sen pitäisi olla toisinpäin.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Tai Tämän pitäisi olla - 1 ja toinen tulisi olla + 1.

418
00:33:05,900 --> 00:33:09,580
[Opiskelija] Ja olisi kaksinkertainen yhtäläisyysmerkki. >> [Bowden] Joo.

419
00:33:09,580 --> 00:33:11,340
[Opiskelija] Joo.

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

421
00:33:15,910 --> 00:33:21,280
Ja lopuksi, nyt kun meillä on tämä + 1-1 juttu,

422
00:33:21,280 --> 00:33:31,520
on se - se voisi olla - se on aina mahdollista alhainen päätyä arvo on suurempi kuin ylös?

423
00:33:35,710 --> 00:33:40,320
Mielestäni ainoa tapa, joka voi tapahtua - Onko se mahdollista? >> [Opiskelija] En tiedä.

424
00:33:40,320 --> 00:33:45,220
Mutta jos se saa katkaistaan ​​ja sitten saa miinus että 1 ja sitten - >> Joo.

425
00:33:45,220 --> 00:33:47,480
[Opiskelija] Olisi ehkä saada sekaisin.

426
00:33:49,700 --> 00:33:53,940
Mielestäni olisi hyvä vain siksi

427
00:33:53,940 --> 00:33:58,800
se päätyy pienempi niillä olisi oltava yhtäläiset, luulen.

428
00:33:58,800 --> 00:34:03,070
Mutta jos he ovat yhtä, niin emme olisi tehneet samalla silmukka aloittaa

429
00:34:03,070 --> 00:34:06,670
ja me vain olisi palannut arvoa. Joten mielestäni olemme nyt hyvä.

430
00:34:06,670 --> 00:34:11,530
Huomaa, että vaikka tämä ongelma ei ole enää rekursiivinen,

431
00:34:11,530 --> 00:34:17,400
samanlaiset näkemykset sovelleta, jos voimme nähdä miten tämä niin helposti otollisia

432
00:34:17,400 --> 00:34:23,659
on rekursiivinen ratkaisu se, että olemme vain päivittää indeksejä uudestaan ​​ja uudestaan,

433
00:34:23,659 --> 00:34:29,960
Teemme ongelma pienempiä ja pienempiä, emme keskitytään osajoukko jono.

434
00:34:29,960 --> 00:34:40,860
[Opiskelija] Jos alhainen, on 0 ja ylös on 1, ne molemmat olla 0 + 1/2, joka menisi 0,

435
00:34:40,860 --> 00:34:44,429
ja sitten yksi olisi + 1, yksi olisi - 1.

436
00:34:47,000 --> 00:34:50,870
[Opiskelija] Mihin olemme tarkkailun tasa-arvoa?

437
00:34:50,870 --> 00:34:55,100
Kuten jos keskimmäinen on todella neula?

438
00:34:55,100 --> 00:34:58,590
Emme tällä hetkellä tee sitä? Oh!

439
00:35:00,610 --> 00:35:02,460
Jos Se on -

440
00:35:05,340 --> 00:35:13,740
Kyllä. Emme voi vain tehdä testi täällä, koska sanotaanko ensimmäinen Lähi -

441
00:35:13,740 --> 00:35:16,430
[Opiskelija] Se oikeastaan ​​kuin saa heittää pois sidottu.

442
00:35:16,430 --> 00:35:20,220
Joten jos heität pois sidottu, sinun täytyy tarkistaa se ensin tai mitä tahansa.

443
00:35:20,220 --> 00:35:23,350
Ah. Joo. >> [Opiskelija] Joo.

444
00:35:23,350 --> 00:35:29,650
Joten nyt olemme heittäneet pois joka meillä nyt katseli,

445
00:35:29,650 --> 00:35:33,260
mikä tarkoittaa, että meidän on nyt myös

446
00:35:33,260 --> 00:35:44,810
if (heinäsuovasta [(matala + ylös) / 2] == neula), voimme palata totta.

447
00:35:44,810 --> 00:35:52,070
Ja onko Laitoin muuten tai vain, jos se tarkoittaa kirjaimellisesti sama asia

448
00:35:52,070 --> 00:35:57,110
koska tämä olisi palannut totta.

449
00:35:57,110 --> 00:36:01,450
Joten laitan if, mutta sillä ei ole väliä.

450
00:36:01,450 --> 00:36:10,440
>> Joten if tämä, muuten tämä, ja tämä on yhteinen asia, en

451
00:36:10,440 --> 00:36:14,340
jos vaikka se on silloin kaikki on hyvin täällä,

452
00:36:14,340 --> 00:36:22,780
kuten alhainen ei voi koskaan olla suurempi kuin ylöspäin, se ei kannata perusteluja siitä onko se totta.

453
00:36:22,780 --> 00:36:28,010
Joten voit yhtä hyvin sanoa, kun pieni on pienempi tai yhtä suuri

454
00:36:28,010 --> 00:36:30,720
tai kun pieni on alle

455
00:36:30,720 --> 00:36:35,300
joten jos ne ovat koskaan yhtä tai matala sattuu kulkemaan ylös,

456
00:36:35,300 --> 00:36:40,130
voimme murtautua ulos tästä silmukan.

457
00:36:41,410 --> 00:36:44,630
Kysymyksiä, huolenaiheita, kommentteja?

458
00:36:47,080 --> 00:36:49,270
Okei. Tämä näyttää hyvältä.

459
00:36:49,270 --> 00:36:52,230
Nyt haluamme tehdä lajitella.

460
00:36:52,230 --> 00:37:04,030
Jos menemme toinen tarkistus, näemme nämä samat numerot,

461
00:37:04,030 --> 00:37:07,550
mutta nyt ne eivät ole enää lajiteltu järjestyksessä.

462
00:37:07,550 --> 00:37:12,840
Ja haluamme toteuttaa lajitella jollakin algoritmi O n log n.

463
00:37:12,840 --> 00:37:17,240
Joten mikä algoritmi luulet meidän pitäisi toteuttaa täällä? >> [Opiskelija] Merge sort.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Joo. Yhdistä sort on O (n log n), niin että me aiomme tehdä.

465
00:37:23,810 --> 00:37:26,680
Ja ongelma tulee olemaan melko samanlainen,

466
00:37:26,680 --> 00:37:31,920
jos se helposti otollisia rekursiivinen ratkaisu.

467
00:37:31,920 --> 00:37:35,580
Voimme myös keksiä iteratiivinen ratkaisu, jos haluamme,

468
00:37:35,580 --> 00:37:42,540
mutta rekursio on helpompaa täällä ja meidän pitäisi tehdä rekursion.

469
00:37:45,120 --> 00:37:49,530
Kai me käydään läpi merge sort ensin

470
00:37:49,530 --> 00:37:54,280
vaikka on ihana video merge sort jo. [Naurua]

471
00:37:54,280 --> 00:37:59,780
Joten yhdistää lajitella olemassa - Olen tuhlata niin paljon tämän paperin.

472
00:37:59,780 --> 00:38:02,080
Voi, on vain yksi jäljellä.

473
00:38:02,080 --> 00:38:03,630
Joten yhdistää.

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

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

476
00:38:29,910 --> 00:38:33,460
Merge kestää kaksi erillistä taulukot.

477
00:38:33,460 --> 00:38:36,780
Yksilöllisesti nämä kaksi ryhmää ovat molemmat lajitellaan.

478
00:38:36,780 --> 00:38:40,970
Joten tämä array, 1, 3, 5, lajitellaan. Tämä joukko, 0, 2, 4, lajitellaan.

479
00:38:40,970 --> 00:38:46,710
Nyt mitä Yhdistämisen pitäisi tehdä, on yhdistää ne yhdeksi array, joka on itse lajiteltu.

480
00:38:46,710 --> 00:38:57,130
Joten me haluamme erilaisia ​​kooltaan 6, joka tulee olemaan näiden elementtien sisälle

481
00:38:57,130 --> 00:38:59,390
vuonna lajiteltu järjestyksessä.

482
00:38:59,390 --> 00:39:03,390
>> Ja jotta voimme hyödyntää sitä, että nämä kaksi ryhmää on lajiteltu

483
00:39:03,390 --> 00:39:06,800
tehdä tämän lineaarisessa ajassa,

484
00:39:06,800 --> 00:39:13,510
lineaarista aikaa merkityksensä, jos tämä joukko on koko x ja tämä on koko Y,

485
00:39:13,510 --> 00:39:20,970
sitten koko algoritmin tulisi olla O-(x + y). Okei.

486
00:39:20,970 --> 00:39:23,150
Joten ehdotuksia.

487
00:39:23,150 --> 00:39:26,030
[Opiskelija] Voisimmeko aloittaa vasemmalta?

488
00:39:26,030 --> 00:39:30,150
Joten voit laittaa 0 alas ensin ja sitten 1 ja sitten täällä olet 2.

489
00:39:30,150 --> 00:39:33,320
Joten se on tavallaan kuin sinulla välilehti joka liikkuu oikealle. >> [Bowden] Joo.

490
00:39:33,320 --> 00:39:41,070
Kummankin matriiseja, jos me vain keskitymme vasemmanpuoleisin elementti.

491
00:39:41,070 --> 00:39:43,530
Koska molemmat ryhmät lajitellaan, me tiedämme, että nämä 2 elementtiä

492
00:39:43,530 --> 00:39:46,920
ovat pienimpiä elementtejä joko array.

493
00:39:46,920 --> 00:39:53,500
Joten se tarkoittaa, että 1 näistä 2 elementtien täytyy olla pienin osa meidän sulautuneen array.

494
00:39:53,500 --> 00:39:58,190
Se vain on niin, että pienin on yksi oikein tällä kertaa.

495
00:39:58,190 --> 00:40:02,580
Niin otamme 0, aseta se vasemmalla koska 0 on pienempi kuin 1,

496
00:40:02,580 --> 00:40:08,210
niin otetaan 0, aseta se meidän ensimmäinen asentoon, ja sitten me päivittää tätä

497
00:40:08,210 --> 00:40:12,070
nyt keskittyä ensimmäinen osa.

498
00:40:12,070 --> 00:40:14,570
Ja nyt me toistamme.

499
00:40:14,570 --> 00:40:20,670
Joten nyt vertaamme 2 ja 1. 1 on pienempi, niin me lisätään 1.

500
00:40:20,670 --> 00:40:25,300
Me päivittää tämän osoitin osoittamaan tämä kaveri.

501
00:40:25,300 --> 00:40:33,160
Nyt teemme sen uudestaan, niin 2. Tämä päivittää, vertaa näitä 2, 3.

502
00:40:33,160 --> 00:40:37,770
Tämä päivittää, sitten 4 ja 5.

503
00:40:37,770 --> 00:40:42,110
Joten se on merge.

504
00:40:42,110 --> 00:40:49,010
>> Sen pitäisi olla aika selvää, että se on lineaarinen aika koska olemme vain mennä poikki jokaisen elementin kerran.

505
00:40:49,010 --> 00:40:55,980
Ja se on suurin askel täytäntöönpanoon merge sort tekee tätä.

506
00:40:55,980 --> 00:40:59,330
Ja se ei ole niin kova.

507
00:40:59,330 --> 00:41:15,020
Pari asiaa murehtia on sanokaamme olimme yhdistäminen 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
Tällöin päädymme tilanteessa, jossa tämä tulee olemaan pienempi,

509
00:41:30,930 --> 00:41:36,160
sitten päivittää tätä osoitin, tämä tulee olemaan pienempi, päivittää tätä,

510
00:41:36,160 --> 00:41:41,280
tämä on pienempi, ja nyt sinulla on tunnustettava

511
00:41:41,280 --> 00:41:44,220
kun olet todella loppuu elementtejä verrata.

512
00:41:44,220 --> 00:41:49,400
Koska olemme jo käyttäneet tätä koko jono,

513
00:41:49,400 --> 00:41:55,190
kaikki tämä joukko on nyt vain työnnetään täällä.

514
00:41:55,190 --> 00:42:02,040
Joten jos me koskaan joutunut siihen pisteeseen, jossa yksi paneelit on täysin yhdistetty jo,

515
00:42:02,040 --> 00:42:06,510
Sitten me vain ottaa kaikki osatekijät muiden array ja aseta ne loppuun array.

516
00:42:06,510 --> 00:42:13,630
Joten voimme vain lisätä 4, 5, 6. Okei.

517
00:42:13,630 --> 00:42:18,070
Se on yksi asia varoa.

518
00:42:22,080 --> 00:42:26,120
Toteuttaminen pitäisi olla vaihe 1.

519
00:42:26,120 --> 00:42:32,600
Yhdistä lajitella sitten perustuu, että se on 2 vaihetta, 2 typerä vaiheita.

520
00:42:38,800 --> 00:42:42,090
Mennään vain antaa tämän array.

521
00:42:57,920 --> 00:43:05,680
Joten yhdistää lajitella, vaihe 1 on rekursiivisesti rikkoa taulukon kahtia.

522
00:43:05,680 --> 00:43:09,350
Joten jakaa tämä ryhmä kahtia.

523
00:43:09,350 --> 00:43:22,920
Meillä on nyt 4, 15, 16, 50 ja 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
Ja nyt me teemme sen uudelleen ja me jakaa nämä kahteen puoliskoon.

525
00:43:25,800 --> 00:43:27,530
Otan vain tehdä sen tällä puolella.

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

527
00:43:34,790 --> 00:43:37,440
Haluamme tehdä saman täällä.

528
00:43:37,440 --> 00:43:40,340
Ja nyt me jakaa sen kahtia uudelleen.

529
00:43:40,340 --> 00:43:51,080
Ja meillä on 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Niin, että on meidän tukikohta tapauksessa.

531
00:43:53,170 --> 00:44:00,540
Kun ryhmät ovat kooltaan 1, sitten pysähtyy halkaisu kahtia.

532
00:44:00,540 --> 00:44:03,190
>> Mitä nyt teemme tämän?

533
00:44:03,190 --> 00:44:15,730
Päädymme tähän myös jakautuvat 8, 23, 42, ja 108.

534
00:44:15,730 --> 00:44:24,000
Joten nyt olemme tässä vaiheessa, nyt lisättävä kaksi merge sort on vain yhdistämällä paria listoille.

535
00:44:24,000 --> 00:44:27,610
Niinpä haluamme yhdistää nämä. Me vain kutsumme sulautua.

536
00:44:27,610 --> 00:44:31,410
Tiedämme merge palaa näitä lajiteltu järjestyksessä.

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

538
00:44:33,920 --> 00:44:41,440
Nyt haluamme yhdistää nämä, ja joka palauttaa listan kanssa kuin lajiteltu järjestyksessä,

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

540
00:44:44,160 --> 00:44:57,380
Me yhdistää nuo - En pysty kirjoittamaan - 8, 23 ja 42, 108.

541
00:44:57,380 --> 00:45:02,890
Joten meillä on sulautunut paria kerran.

542
00:45:02,890 --> 00:45:05,140
Nyt me vain yhdistää uudelleen.

543
00:45:05,140 --> 00:45:10,130
Huomaa, että kukin näistä luetteloista lajitellaan itsessään,

544
00:45:10,130 --> 00:45:15,220
ja sitten voimme vain yhdistää nämä luettelot saada luettelon kokoa 4, joka on järjestetty

545
00:45:15,220 --> 00:45:19,990
ja yhdistää nämä kaksi luetteloa saada listan kokoa 4, joka on järjestetty.

546
00:45:19,990 --> 00:45:25,710
Ja lopuksi, voimme yhdistää nämä kaksi luetteloa koko 4 saada yksi listan koko 8, joka on järjestetty.

547
00:45:25,710 --> 00:45:34,030
Joten nähdä, että tämä on yleinen n log n, olemme jo nähneet, että yhdistämisessä on lineaarinen,

548
00:45:34,030 --> 00:45:40,390
joten kun olemme tekemisissä yhdistämällä näitä, niin kuin kokonaiskustannukset merge

549
00:45:40,390 --> 00:45:43,410
Näiden kahden luettelon on vain 2, koska -

550
00:45:43,410 --> 00:45:49,610
Tai no, se on O n, mutta n tässä on vain nämä 2 elementtiä, joten se on 2.

551
00:45:49,610 --> 00:45:52,850
Ja nämä 2 ovat 2 ja nämä 2 ovat 2 ja nämä 2 ovat 2,

552
00:45:52,850 --> 00:45:58,820
joten kaikilla on sulautuu että meidän täytyy tehdä, päädymme tekemään n..

553
00:45:58,820 --> 00:46:03,210
Kuten 2 + 2 + 2 + 2 on 8, joka on n,

554
00:46:03,210 --> 00:46:08,060
joten kustannukset sulautuvan tähän sarjaan on n.

555
00:46:08,060 --> 00:46:10,810
Ja sitten sama asia tässä.

556
00:46:10,810 --> 00:46:16,980
Me yhdistää nämä 2, niin nämä 2 ja erikseen tätä Yhdistäminen kestää neljä operaatiota,

557
00:46:16,980 --> 00:46:23,610
Tämän yhdistämisen kestää neljä operaatiota, mutta jälleen kerran, kaikkien näiden,

558
00:46:23,610 --> 00:46:29,030
päädymme sulautuvan n kaikista asioista, joten tämä vaihe kestää n..

559
00:46:29,030 --> 00:46:33,670
Ja niin jokainen taso kestää n alkio on yhdistetty.

560
00:46:33,670 --> 00:46:36,110
>> Ja kuinka monta tasoa on olemassa?

561
00:46:36,110 --> 00:46:40,160
Kullakin tasolla, meidän array kasvaa koko 2.

562
00:46:40,160 --> 00:46:44,590
Tässä meidän paneelit ovat kooltaan 1, täällä he kokoa 2, täällä he koon 4,

563
00:46:44,590 --> 00:46:46,470
ja lopuksi he kooltaan 8.

564
00:46:46,470 --> 00:46:56,450
Joten koska se kaksinkertaistaa, siellä tulevat olemaan yhteensä log n näiden tasojen.

565
00:46:56,450 --> 00:47:02,090
Joten log n tasoa, kukin taso ottaen n yhteensä toiminnan

566
00:47:02,090 --> 00:47:05,720
saamme n log n algoritmi.

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

568
00:47:08,940 --> 00:47:13,320
Ovatko ihmiset jo edistynyt miten toteuttaa tämä?

569
00:47:13,320 --> 00:47:18,260
Onko joku jo tilassa, jossa voin vain vetää heidän koodia?

570
00:47:20,320 --> 00:47:22,260
Voin antaa minuutti.

571
00:47:24,770 --> 00:47:27,470
Tämä tulee olemaan pidempi.

572
00:47:27,470 --> 00:47:28,730
Suosittelen toistu -

573
00:47:28,730 --> 00:47:30,510
Sinun ei tarvitse tehdä rekursio varten Yhdistämisen

574
00:47:30,510 --> 00:47:33,750
koska tehdä rekursio varten yhdistämisen, olet menossa on kuljettava joukko erikokoisia.

575
00:47:33,750 --> 00:47:37,150
Voit, mutta se on ärsyttävää.

576
00:47:37,150 --> 00:47:43,720
Mutta rekursio for sort itsessään on melko helppoa.

577
00:47:43,720 --> 00:47:49,190
Sinä vain kirjaimellisesti soittaa eräänlainen vasemmalla puoli, lajitella oikealla puoli. Okei.

578
00:47:51,770 --> 00:47:54,860
Kellään mitään voin vetää vielä?

579
00:47:54,860 --> 00:47:57,540
Tai muuten Annan minuutti.

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

581
00:47:59,900 --> 00:48:02,970
Kellään jotain voimme työskennellä?

582
00:48:05,450 --> 00:48:09,680
Tai muuten me vain toimi tässä ja laajenna sitten sieltä.

583
00:48:09,680 --> 00:48:14,050
>> Kellään enemmän kuin tämä, että voin vetää?

584
00:48:14,050 --> 00:48:17,770
[Opiskelija] Joo. Voit vetää omani. >> Selvä.

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

586
00:48:22,170 --> 00:48:25,280
[Opiskelija] Oli paljon ehtoja. >> Voi ampua. Voitko -

587
00:48:25,280 --> 00:48:28,110
[Opiskelija] Minun täytyy pelastaa se. >> Joo.

588
00:48:32,420 --> 00:48:35,730
Niin teimme tehdä yhdistämisen erikseen.

589
00:48:35,730 --> 00:48:38,570
Voi, mutta se ei ole niin paha.

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

591
00:48:41,650 --> 00:48:47,080
Joten tavallaan itse vain soittaa mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Selitä meille, mitä mergeSortHelp tekee.

593
00:48:49,530 --> 00:48:55,700
[Opiskelija] MergeSortHelp melko paljon tekee kaksi päävaihetta,

594
00:48:55,700 --> 00:49:01,270
joka on lajitella kummankin puolen array ja sitten yhdistää molemmat.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Okei, joten anna minulle toinen.

596
00:49:10,850 --> 00:49:13,210
Mielestäni tämä - >> [opiskelija] Minun täytyy -

597
00:49:17,100 --> 00:49:19,400
Joo. Olen puuttuu jotain.

598
00:49:19,400 --> 00:49:23,100
Vuonna merge, ymmärrän, että minun täytyy luoda uuden taulukon

599
00:49:23,100 --> 00:49:26,530
koska en voinut tehdä sitä paikallaan. >> Kyllä. Et voi. Korjaa.

600
00:49:26,530 --> 00:49:28,170
[Opiskelija] Joten voin luoda uuden taulukon.

601
00:49:28,170 --> 00:49:31,510
Unohdin lopussa sulautua uudelleen muuttaa.

602
00:49:31,510 --> 00:49:34,490
Okei. Tarvitsemme uuden taulukon.

603
00:49:34,490 --> 00:49:41,000
Vuonna merge sort, tämä on melkein aina totta.

604
00:49:41,000 --> 00:49:44,340
Osa kustannuksista parempaa algoritmia ajallisesti

605
00:49:44,340 --> 00:49:47,310
on lähes aina tarvitse käyttää hieman enemmän muistia.

606
00:49:47,310 --> 00:49:51,570
Joten tässä, ei väliä kuinka teet yhdistää lajitella,

607
00:49:51,570 --> 00:49:54,780
sinun väistämättä täytyy käyttää ylimääräistä muistia.

608
00:49:54,780 --> 00:49:58,240
Hän loi uuden taulukon.

609
00:49:58,240 --> 00:50:03,400
Ja sitten sanot lopussa meidän tarvitsee vain kopioida uuden array osaksi alkuperäistä array.

610
00:50:03,400 --> 00:50:04,830
[Opiskelija] Luulen niin, kyllä.

611
00:50:04,830 --> 00:50:08,210
En tiedä, jos se toimii suhteen laskeminen viittaamalla tai mitä tahansa -

612
00:50:08,210 --> 00:50:11,650
Joo, se toimii. >> [Opiskelija] Okei.

613
00:50:20,620 --> 00:50:24,480
Oletko kokeilla tämän? >> [Opiskelija] Ei, ei vielä. >> Okei.

614
00:50:24,480 --> 00:50:28,880
Kokeilla sitä, ja sitten minä puhua sitä toista.

615
00:50:28,880 --> 00:50:35,200
[Opiskelija] Minun täytyy olla kaikkien tehtävä prototyyppejä ja kaikkea, mutta, eikö?

616
00:50:37,640 --> 00:50:40,840
Toiminto prototyypit. Ai, tarkoitatko kuin - Kyllä.

617
00:50:40,840 --> 00:50:43,040
Järjestä soittaa mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Joten jotta sort soittaa mergeSortHelp, mergeSortHelp on joko on määritelty

619
00:50:47,390 --> 00:50:56,370
ennen lajitella tai meidän täytyy vain prototyyppi. Kopioi ja liitä se.

620
00:50:56,370 --> 00:50:59,490
Ja vastaavasti mergeSortHelp kutsuu sulautuvat,

621
00:50:59,490 --> 00:51:03,830
mutta Yhdistämisen ei ole vielä määritelty, joten voimme vain antaa mergeSortHelp tietää

622
00:51:03,830 --> 00:51:08,700
että sitähän yhdistää tulee näyttämään, ja se siitä.

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

624
00:51:22,770 --> 00:51:32,660
Meillä on ongelma täällä, jossa meillä ei ole perustapaus.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp on rekursiivinen, joten mitään rekursiivista funktiota

626
00:51:38,110 --> 00:51:42,610
on menossa on jonkinlainen pohja asian tietää milloin lopettaa rekursiivisesti itseään kutsuva.

627
00:51:42,610 --> 00:51:45,590
Mikä on meidän tukikohta tapaus aiotaan täällä? Joo.

628
00:51:45,590 --> 00:51:49,110
[Opiskelija] Jos koko on 1? >> [Bowden] Kyllä.

629
00:51:49,110 --> 00:51:56,220
Niin kuin näimme oikeassa, pysähdyimme halkaisu ryhmät

630
00:51:56,220 --> 00:52:01,850
kun saimme paneelit koko 1, mikä väistämättä lajitellaan itse.

631
00:52:01,850 --> 00:52:09,530
Joten jos koko on 1, tiedämme taulukko on jo lajiteltu,

632
00:52:09,530 --> 00:52:12,970
joten voimme vain palata.

633
00:52:12,970 --> 00:52:16,880
>> Huomaa, että on mitätön, joten emme palauta mitään erityistä, me vain palata.

634
00:52:16,880 --> 00:52:19,580
Okei. Niin, että meidän perustapaus.

635
00:52:19,580 --> 00:52:27,440
Luulen meidän tukikohta tapauksessa voisi myös olla, jos satumme olla sulautuvan joukko koko 0,

636
00:52:27,440 --> 00:52:30,030
me luultavasti halua lopettaa jossain vaiheessa,

637
00:52:30,030 --> 00:52:33,610
joten voimme sanoa koko on vähemmän kuin 2 tai pienempi tai yhtä suuri kuin 1

638
00:52:33,610 --> 00:52:37,150
niin että tämä toimii mitään array nyt.

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

640
00:52:38,870 --> 00:52:42,740
Niin, että meidän perustapaus.

641
00:52:42,740 --> 00:52:45,950
Nyt haluat kävellä meitä merge?

642
00:52:45,950 --> 00:52:49,140
Mitä nämä tapaukset tarkoittaa?

643
00:52:49,140 --> 00:52:54,480
Täällä, me vain teemme saman ajatuksen, -

644
00:52:56,970 --> 00:53:02,470
[Opiskelija] minun täytyy kulkee koko kaikki mergeSortHelp puhelut.

645
00:53:02,470 --> 00:53:10,080
Lisäsin koko ylimääräisenä ensisijaisena ja se ei ole siellä, kuten koko / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, koko / 2, koko / 2. >> [Opiskelija] Niin, ja myös edellä toimisivat yhtä hyvin.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Täällä? >> [Opiskelija] Vain kokoa. >> [Bowden] Oh. Koko, koko? >> [Opiskelija] Joo.

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

649
00:53:23,010 --> 00:53:26,580
Saanen ajatella toista.

650
00:53:26,580 --> 00:53:28,780
Onko meillä törmätä ongelma?

651
00:53:28,780 --> 00:53:33,690
Olemme aina hoidettaessa vasemmalle 0. >> [Opiskelija] No

652
00:53:33,690 --> 00:53:36,340
Se on väärin myös. Anteeksi. Sen pitäisi olla alku. Joo.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Okei. Pidän siitä paremmin.

654
00:53:39,230 --> 00:53:43,880
Ja loppu. Okei.

655
00:53:43,880 --> 00:53:47,200
Joten nyt haluat kävellä meitä merge? >> [Opiskelija] Okei.

656
00:53:47,200 --> 00:53:52,150
Olen vain kävelemällä tämän uuden taulukon, että olen luonut.

657
00:53:52,150 --> 00:53:57,420
Sen koko on koko osan array, että haluamme voidaan lajitella

658
00:53:57,420 --> 00:54:03,460
ja yrittää löytää tekijä, että minun pitäisi laittaa uuden taulukon askel.

659
00:54:03,460 --> 00:54:10,140
Niin tehdä, että ensin olen tarkistaa, jos vasen puoli array edelleen saada lisää elementtejä,

660
00:54:10,140 --> 00:54:14,260
ja jos ei, niin menet alas, että muu tila, joka vain sanoo

661
00:54:14,260 --> 00:54:20,180
Okei, sen on oltava oikeassa array, ja laitamme, että nykyinen indeksi newArray.

662
00:54:20,180 --> 00:54:27,620
>> Ja sitten muuten olen tarkistaa, jos oikea puoli matriisi on myös valmis,

663
00:54:27,620 --> 00:54:30,630
jolloin juuri laittaa vasemmalle.

664
00:54:30,630 --> 00:54:34,180
Jotka eivät ehkä ole todellisuudessa tarpeen. En ole varma.

665
00:54:34,180 --> 00:54:40,970
Mutta joka tapauksessa, kaksi muuta Tarkista, kumpi on pienempi vasemmalle tai oikealle.

666
00:54:40,970 --> 00:54:49,770
Ja myös kussakin tapauksessa olen mukaa kumpi paikkamerkki I kasvattaa.

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

668
00:54:52,040 --> 00:54:53,840
Se näyttää hyvältä.

669
00:54:53,840 --> 00:54:58,800
Onko kellään kommentteja tai huolenaiheita tai kysymyksiä?

670
00:55:00,660 --> 00:55:07,720
Joten neljästä tapauksesta, että meidän on tuotava asiat oikeisiin vain on - tai se näyttää Five -

671
00:55:07,720 --> 00:55:13,100
mutta meidän on harkittava vasemmalla array on loppunut asioita meidän yhdistää,

672
00:55:13,100 --> 00:55:16,390
onko oikea joukko on loppunut asioita meidän yhdistää -

673
00:55:16,390 --> 00:55:18,400
Olen osoittaen mitään.

674
00:55:18,400 --> 00:55:21,730
Joten onko vasemmalla array on loppunut asioita tai oikealle array on loppunut asioita.

675
00:55:21,730 --> 00:55:24,320
Nämä ovat kaksi tapausta.

676
00:55:24,320 --> 00:55:30,920
Tarvitsemme myös triviaali asia, onko vasemman asia on pienempi kuin oikein.

677
00:55:30,920 --> 00:55:33,910
Sitten haluamme valita vasemmalle asia.

678
00:55:33,910 --> 00:55:37,630
Nämä ovat tapauksia.

679
00:55:37,630 --> 00:55:40,990
Joten tämä oli oikeassa, niin se siitä.

680
00:55:40,990 --> 00:55:46,760
Array vasemmalle. Se on 1, 2, 3. Okei. Niin joo, ne ovat neljä asioita kannattaa tehdä.

681
00:55:50,350 --> 00:55:54,510
Ja me ei mennä yli iteratiivinen ratkaisu.

682
00:55:54,510 --> 00:55:55,980
En suosittele -

683
00:55:55,980 --> 00:56:03,070
Yhdistämisen sort on esimerkki funktio, joka on sekä ei hännän rekursiivinen

684
00:56:03,070 --> 00:56:07,040
se ei ole helppoa tehdä häntää rekursiivinen,

685
00:56:07,040 --> 00:56:13,450
mutta se ei ole kovin helppoa tehdä iteratiivinen.

686
00:56:13,450 --> 00:56:16,910
Tämä on erittäin helppoa.

687
00:56:16,910 --> 00:56:19,170
Tämä täytäntöönpano merge lajitella,

688
00:56:19,170 --> 00:56:22,140
yhdistää, ei väliä mitä teet, olet menossa rakentaa yhdistämisen.

689
00:56:22,140 --> 00:56:29,170
>> Joten yhdistää sort päälle rakennetaan Merge rekursiivisesti vain nämä kolme riviä.

690
00:56:29,170 --> 00:56:34,700
Iteratiivisesti, se on ärsyttävää ja vaikea ajatella.

691
00:56:34,700 --> 00:56:41,860
Mutta huomaa, että se ei ole häntää rekursiivinen koska mergeSortHelp - kun se kutsuu itseään -

692
00:56:41,860 --> 00:56:46,590
se on vielä tehdä asioita tämän jälkeen rekursiivinen puhelu palaa.

693
00:56:46,590 --> 00:56:50,830
Joten tämä pinokehys on edelleen olemassa, vaikka kutsumalla tätä.

694
00:56:50,830 --> 00:56:54,170
Ja sitten kun soitat tätä, pinokehys on edelleen olemassa

695
00:56:54,170 --> 00:56:57,780
sillä senkin jälkeen puhelun, tarvitsemme vielä yhdistää.

696
00:56:57,780 --> 00:57:01,920
Ja se on triviaali tehdä tämä häntää rekursiivinen.

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

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

699
00:57:09,860 --> 00:57:13,400
Niin menee takaisin lajitella - Voi, on kaksi asiaa haluan näyttää. Okei.

700
00:57:13,400 --> 00:57:17,840
Palataan lajitella, teemme tämän nopeasti.

701
00:57:17,840 --> 00:57:21,030
Tai etsi. Lajittele? Lajittele. Joo.

702
00:57:21,030 --> 00:57:22,730
Palataan alkua lajitella.

703
00:57:22,730 --> 00:57:29,870
Haluamme luoda algoritmi, joka lajittelee taulukon jollakin algoritmilla

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

705
00:57:33,660 --> 00:57:40,860
Joten miten tämä on mahdollista? Onko kellään minkäänlaista -

706
00:57:40,860 --> 00:57:44,300
Olen vihjannut ennen klo -

707
00:57:44,300 --> 00:57:48,300
Jos aiomme paranevan n log n O n,

708
00:57:48,300 --> 00:57:51,450
olemme parantaneet algoritmin ajallisesti,

709
00:57:51,450 --> 00:57:55,250
mikä tarkoittaa sitä, mitä aiomme pitää tehdä tehdä niin, että?

710
00:57:55,250 --> 00:57:59,520
[Opiskelija] Space. >> Joo. Aiomme käyttää enemmän tilaa.

711
00:57:59,520 --> 00:58:04,490
Eikä edes enemmän tilaa, se on eksponentiaalisesti enemmän tilaa.

712
00:58:04,490 --> 00:58:14,320
Joten mielestäni tällainen algoritmi on pseudo jotain, pseudo polynomin -

713
00:58:14,320 --> 00:58:18,980
pseudo - En muista. Pseudo jotain.

714
00:58:18,980 --> 00:58:22,210
Mutta se johtuu meidän täytyy käyttää niin paljon tilaa

715
00:58:22,210 --> 00:58:28,610
, että tämä on saavutettavissa, mutta ei realistinen.

716
00:58:28,610 --> 00:58:31,220
>> Ja miten saavutamme tämän?

717
00:58:31,220 --> 00:58:36,810
Voimme saavuttaa tämän, jos voimme taata, että tietty alkio

718
00:58:36,810 --> 00:58:39,600
alittaa tietyn koon.

719
00:58:42,070 --> 00:58:44,500
Joten vain sanoa, että koko on 200,

720
00:58:44,500 --> 00:58:48,130
tahansa osa matriisi on alle koko 200.

721
00:58:48,130 --> 00:58:51,080
Ja tämä on todella realistinen.

722
00:58:51,080 --> 00:58:58,660
Voit helposti saada array että tiedät kaiken siinä

723
00:58:58,660 --> 00:59:00,570
tulee olemaan pienempi kuin jokin määrä.

724
00:59:00,570 --> 00:59:07,400
Kuten jos sinulla on joitakin erittäin massiivinen vektori tai jotain

725
00:59:07,400 --> 00:59:11,810
mutta tiedät kaiken tulee olla välillä 0 ja 5,

726
00:59:11,810 --> 00:59:14,790
niin se tulee olemaan huomattavasti nopeampi tehdä tätä.

727
00:59:14,790 --> 00:59:17,930
Ja sitoutunut mihin tahansa elementtien on 5,

728
00:59:17,930 --> 00:59:21,980
joten tämä sidottu, eli kuinka paljon muistia aiot käyttää.

729
00:59:21,980 --> 00:59:26,300
Niin sidottu on 200.

730
00:59:26,300 --> 00:59:32,960
Teoriassa on aina sidottu, koska kokonaisluku voi olla vain jopa 4000000000,

731
00:59:32,960 --> 00:59:40,600
mutta se on epärealistinen jälkeen olisimme käyttäen tilaa

732
00:59:40,600 --> 00:59:44,400
suuruusluokkaa 4000000000. Niin, että on epärealistista.

733
00:59:44,400 --> 00:59:47,060
Mutta tässä me sanomme meidän sidottu on 200.

734
00:59:47,060 --> 00:59:59,570
Temppu tehdä sitä O n on teemme toinen joukko kutsutaan laskee koon sidottu.

735
00:59:59,570 --> 01:00:10,470
Joten oikeastaan, tämä on oikotie - En oikeastaan ​​tiedä, jos clang tämä.

736
01:00:11,150 --> 01:00:15,330
Mutta GCC ainakin - Olen olettaen clang tekee sen liian -

737
01:00:15,330 --> 01:00:18,180
tämä vain alustaa koko ryhmän olevan 0s.

738
01:00:18,180 --> 01:00:25,320
Joten jos en halua tehdä sitä, niin voisin erikseen tehdä (int i = 0;

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

740
01:00:31,500 --> 01:00:35,260
Joten nyt kaikki on alustettu 0.

741
01:00:35,260 --> 01:00:39,570
Olen toistaa yli minun array,

742
01:00:39,570 --> 01:00:51,920
ja mitä olen tekemässä on Luotan määrä kunkin - Mennään tänne.

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

744
01:00:55,480 --> 01:01:00,010
Mitä Luotan on esiintymien lkm jokainen näistä seikoista.

745
01:01:00,010 --> 01:01:03,470
Katsotaanpa itse lisätä pari enemmän täällä joitakin toistoja.

746
01:01:03,470 --> 01:01:11,070
Joten arvo täällä on, arvo, joka tulee olemaan array [i].

747
01:01:11,070 --> 01:01:14,850
Joten val voi olla 4 tai 8 tai mitä tahansa.

748
01:01:14,850 --> 01:01:18,870
Ja nyt olen counting kuinka moni tästä arvosta olen nähnyt,

749
01:01:18,870 --> 01:01:21,230
niin väliä [Val] + +;

750
01:01:21,230 --> 01:01:29,430
Kun tämä on tehty, tärkeintä on menossa katsomaan jotain 0001.

751
01:01:29,430 --> 01:01:42,190
Tehdään väliä [Val] - Bound + 1.

752
01:01:42,190 --> 01:01:48,230
>> Nyt se vain selittää, että olemme alkaen 0.

753
01:01:48,230 --> 01:01:50,850
Joten jos 200 tulee olemaan meidän suurin määrä,

754
01:01:50,850 --> 01:01:54,720
Sitten 0-200 on 201 asiaa.

755
01:01:54,720 --> 01:02:01,540
Joten laskee, se tulee näyttämään 00001 koska meillä on yksi 4.

756
01:02:01,540 --> 01:02:10,210
Sitten meillä on 0001, jossa meillä on 1 8. indeksi count.

757
01:02:10,210 --> 01:02:14,560
Meillä on 2 23. indeksi count.

758
01:02:14,560 --> 01:02:17,630
Meillä on 2 42. indeksi count.

759
01:02:17,630 --> 01:02:21,670
Joten voimme käyttää count.

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

761
01:02:44,920 --> 01:02:52,540
Ja niin jos num_of_item on 2, se tarkoittaa, että haluamme lisätä 2 numero i

762
01:02:52,540 --> 01:02:55,290
meidän lajiteltu array.

763
01:02:55,290 --> 01:03:02,000
Joten meidän täytyy seurata, kuinka pitkälle olemme osaksi array.

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

765
01:03:05,470 --> 01:03:09,910
Array - Minä vain kirjoitan sen.

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
Sitäkö haluan? Luulen, että se mitä haluan.

769
01:03:35,100 --> 01:03:38,290
Kyllä, tämä näyttää hyvältä. Okei.

770
01:03:38,290 --> 01:03:43,050
Joten ei kaikki ymmärrä, mitä tarkoitusta minun laskee array on?

771
01:03:43,050 --> 01:03:48,140
Se laskee tapahtumien määrä kutakin näistä numeroista.

772
01:03:48,140 --> 01:03:51,780
Sitten olen iteroimalla yli ratkaisee array,

773
01:03:51,780 --> 01:03:57,190
ja i: nnen aseman laskee array

774
01:03:57,190 --> 01:04:01,930
on määrä minun tuo pitäisi näkyä minun lajiteltu array.

775
01:04:01,930 --> 01:04:06,840
Siksi laskennat 4 tulee olemaan 1

776
01:04:06,840 --> 01:04:11,840
ja laskee 8 tulee olemaan 1, laskee 23 tulee olemaan 2.

777
01:04:11,840 --> 01:04:16,900
Niin, että miten moni heistä Haluan lisätä minun lajiteltu array.

778
01:04:16,900 --> 01:04:19,200
Sitten vain tehdä se.

779
01:04:19,200 --> 01:04:28,960
Olen lisäämällä num_of_item i on minun lajiteltu array.

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

781
01:04:32,460 --> 01:04:43,100
Ja niin tämä on jälleen lineaarinen aika, koska olemme juuri iteroimalla yli tämän kerran,

782
01:04:43,100 --> 01:04:47,470
mutta se on myös lineaarinen mitä tämä numero sattuu olemaan,

783
01:04:47,470 --> 01:04:50,730
ja niin se on vahvasti riippuvainen mitä sidotun on.

784
01:04:50,730 --> 01:04:53,290
Sidotulla 200, se ei ole niin paha.

785
01:04:53,290 --> 01:04:58,330
Jos sidottu tulee olemaan 10000, niin se on hieman huonompi,

786
01:04:58,330 --> 01:05:01,360
mutta jos sitoutuneen tulee olemaan 4 miljardia, joka on täysin epärealistinen

787
01:05:01,360 --> 01:05:07,720
ja tämä ryhmä on menossa on oltava koko 4 miljardia euroa, mikä on epärealistista.

788
01:05:07,720 --> 01:05:10,860
Joten se siitä. Kysymyksiä?

789
01:05:10,860 --> 01:05:13,270
[Äänetön opiskelija vastausta] >> Okei.

790
01:05:13,270 --> 01:05:15,710
Tajusin yhden asian, kun olimme menossa läpi.

791
01:05:17,980 --> 01:05:23,720
Mielestäni ongelmana oli Lucasin ja luultavasti joka ikinen olemme nähneet.

792
01:05:23,720 --> 01:05:26,330
Olen täysin unohtanut.

793
01:05:26,330 --> 01:05:31,040
Ainoa asia, jonka halusin kommentoida on, että kun olet tekemisissä asioita, kuten indeksit,

794
01:05:31,040 --> 01:05:38,320
et koskaan todella nähdä tämän, kun olet kirjoittamassa varten silmukka,

795
01:05:38,320 --> 01:05:41,120
mutta teknisesti, kun olet tekemisissä näiden indeksien,

796
01:05:41,120 --> 01:05:45,950
sinun pitäisi oikeastaan ​​aina käsitellä unsigned kokonaislukuja.

797
01:05:45,950 --> 01:05:53,850
Syynä tähän on, kun olet tekemisissä allekirjoitettu kokonaislukuja,

798
01:05:53,850 --> 01:05:56,090
joten jos sinulla on 2 allekirjoittaneet kokonaislukuja ja lisäät ne yhteen

799
01:05:56,090 --> 01:06:00,640
ja he päätyvät liian iso, niin voit päätyä negatiivinen luku.

800
01:06:00,640 --> 01:06:03,410
Niin, että mitä kokonaisluvun ylivuoto on.

801
01:06:03,410 --> 01:06:10,500
>> Jos lisään 2000000000 ja 1000000000, päädyn negatiivinen 1000000000.

802
01:06:10,500 --> 01:06:15,480
Näin kokonaislukuja toimi tietokoneissa.

803
01:06:15,480 --> 01:06:17,510
Joten ongelma käyttäen -

804
01:06:17,510 --> 01:06:23,500
Se on hienoa, paitsi jos pieni sattuu olemaan 2 miljardia jopa sattuu olemaan 1000000000,

805
01:06:23,500 --> 01:06:27,120
tämä tulee olemaan negatiivinen 1000000000 ja sitten me aiomme jakaa, että 2

806
01:06:27,120 --> 01:06:29,730
ja lopulta negatiivinen 500 miljoonaa euroa.

807
01:06:29,730 --> 01:06:33,760
Joten tämä on vain ongelma, jos satut olemaan hakuja array

808
01:06:33,760 --> 01:06:38,070
miljardeja asioita.

809
01:06:38,070 --> 01:06:44,050
Mutta jos pieni + asti tapahtuu ylivuoto, niin se on ongelma.

810
01:06:44,050 --> 01:06:47,750
Heti kun saamme heidät unsigned, sitten 2 miljardia plus 1 miljardi on 3000000000.

811
01:06:47,750 --> 01:06:51,960
3000000000 jaettuna 2 on 1,5 miljardia euroa.

812
01:06:51,960 --> 01:06:55,670
Joten kun he unsigned, kaikki on täydellistä.

813
01:06:55,670 --> 01:06:59,900
Ja niin se on myös ongelma, kun olet kirjoittanut silmukoita,

814
01:06:59,900 --> 01:07:03,940
ja oikeastaan ​​se luultavasti tekee sen automaattisesti.

815
01:07:09,130 --> 01:07:12,330
Se oikeastaan ​​vain huutaa sinulle.

816
01:07:12,330 --> 01:07:21,610
Joten jos tämä määrä on liian suuri vain kokonaisluku, mutta se sopii allekirjoittamaton kokonaisluku,

817
01:07:21,610 --> 01:07:24,970
se huutaa sinulle, joten siksi te koskaan joutunut asiaa.

818
01:07:29,150 --> 01:07:34,820
Voit nähdä, että indeksi ei koskaan tule olemaan negatiivinen,

819
01:07:34,820 --> 01:07:39,220
joten kun olet iteroimalla yli array,

820
01:07:39,220 --> 01:07:43,970
voit melkein aina sanoa unsigned int i, mutta et todellakaan tarvitse.

821
01:07:43,970 --> 01:07:47,110
Asiat ovat menossa töihin melko paljon yhtä hyvin.

822
01:07:48,740 --> 01:07:50,090
Okei. [Kuiskaa] Mitä kello on?

823
01:07:50,090 --> 01:07:54,020
Viimeinen asia, jonka halusin näyttää - ja minä vain tehdä se todella nopeasti.

824
01:07:54,020 --> 01:08:03,190
Tiedätkö miten olemme # define jotta voimme # define MAX kuin 5 tai jotain?

825
01:08:03,190 --> 01:08:05,940
Älkäämme tee MAX. # Define sidottava 200. Niinhän me teimme ennen.

826
01:08:05,940 --> 01:08:10,380
Se määrittelee vakio, joka on juuri menossa kopioida ja liittää

827
01:08:10,380 --> 01:08:13,010
missä satumme kirjoittaa sidottu.

828
01:08:13,010 --> 01:08:18,189
>> Jotta voimme todella tehdä enemmän # määrittelee.

829
01:08:18,189 --> 01:08:21,170
Voimme # define toimintoja.

830
01:08:21,170 --> 01:08:23,410
He eivät oikeasti toimii, mutta me kutsumme heitä toimintoja.

831
01:08:23,410 --> 01:08:36,000
Esimerkiksi olisi jotain MAX (x, y) on määritelty (x <y? Y: x). Okei.

832
01:08:36,000 --> 01:08:40,660
Joten sinun pitäisi tottua ternäärinen operaattorin syntaksi,

833
01:08:40,660 --> 01:08:49,029
mutta on x pienempi kuin y? Return y, muuten palauta x.

834
01:08:49,029 --> 01:08:54,390
Näet siis voit tehdä tämän erillisenä toimintona,

835
01:08:54,390 --> 01:09:01,399
ja toiminta voisi olla bool MAX kestää 2 argumentteja, palauta.

836
01:09:01,399 --> 01:09:08,340
Tämä on yksi yleisimpiä näen tehnyt näin. Me kutsumme heitä makroja.

837
01:09:08,340 --> 01:09:11,790
Tämä on makro.

838
01:09:11,790 --> 01:09:15,859
Tämä on vain syntaksi sitä.

839
01:09:15,859 --> 01:09:18,740
Voit kirjoittaa makron tehdä mitä haluat.

840
01:09:18,740 --> 01:09:22,649
Voit usein nähdä makroja virheenkorjaus printfs ja tavaraa.

841
01:09:22,649 --> 01:09:29,410
Joten tyyppi printf olemassa erityisiä vakiot C kuten alaviiva LINE alaviiva

842
01:09:29,410 --> 01:09:31,710
2 alaviivoja LINE alaviiva

843
01:09:31,710 --> 01:09:37,550
ja siellä on myös mielestäni 2 alaviivoja FUNC. Se voi olla sitä. Jotain sellaista.

844
01:09:37,550 --> 01:09:40,880
Nämä asiat korvataan funktion nimi

845
01:09:40,880 --> 01:09:42,930
tai numero rivin olet.

846
01:09:42,930 --> 01:09:48,630
Usein, kirjoittaa virheenkorjaus printfs että tänne voisin sitten vain kirjoittamaan

847
01:09:48,630 --> 01:09:54,260
Debug ja se tulostaa rivin numero ja toiminto, satun olemaan

848
01:09:54,260 --> 01:09:57,020
että se olisi kohdannut että DEBUG lausuma.

849
01:09:57,020 --> 01:09:59,550
Ja voit myös tulostaa muita asioita.

850
01:09:59,550 --> 01:10:05,990
Joten yksi asia sinun pitäisi varoa on jos satun # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
kuin jotain 2 * y ja 2 * x.

852
01:10:11,380 --> 01:10:14,310
Joten jostain syystä satut tehdä paljon.

853
01:10:14,310 --> 01:10:16,650
Joten tee se makro.

854
01:10:16,650 --> 01:10:18,680
Tämä on itse asiassa rikki.

855
01:10:18,680 --> 01:10:23,050
Minä kutsuisin sitä tekemällä jotain DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Joten mitä pitäisi palauttaa?

857
01:10:28,840 --> 01:10:30,580
[Opiskelija] 12.

858
01:10:30,580 --> 01:10:34,800
Kyllä, 12 olisi palautettava, ja 12 palautetaan.

859
01:10:34,800 --> 01:10:43,350
3 saa korvataan x, 6 saa korvata y, ja palaamme 2 * 6, joka on 12.

860
01:10:43,350 --> 01:10:47,710
Mitä nyt tästä? Mitä pitäisi palauttaa?

861
01:10:47,710 --> 01:10:50,330
[Opiskelija] 14. >> Ihannetapauksessa 14.

862
01:10:50,330 --> 01:10:55,290
Kyse on siitä, miten hash määrittelee työn, muista se kirjaimellisesti kopioi ja liitä

863
01:10:55,290 --> 01:11:00,160
on aika paljon kaikkea, niin mitä tämä tulee tulkita

864
01:11:00,160 --> 01:11:11,270
on 3 alle 1 + 6, 2 kertaa 1 + 6, 2 kertaa 3.

865
01:11:11,270 --> 01:11:19,780
>> Joten tästä syystä melkein aina kääri kaiken suluissa.

866
01:11:22,180 --> 01:11:25,050
Jokainen muuttuja melkein aina kääri suluissa.

867
01:11:25,050 --> 01:11:29,570
On tapauksia, joissa ei tarvitse, kuin minä tiedän, että minun ei tarvitse tehdä sitä täällä

868
01:11:29,570 --> 01:11:32,110
koska alle on melko paljon aina juuri menossa töihin,

869
01:11:32,110 --> 01:11:34,330
vaikka se ehkä ole edes totta.

870
01:11:34,330 --> 01:11:41,870
Jos siellä on jotain naurettavaa kuten DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
niin se on menossa korvataan 3 alle 1 vastaa vastaa 2,

872
01:11:49,760 --> 01:11:53,460
ja niin sitten se tulee tehdä 3 alle 1, ei se yhtä 2,

873
01:11:53,460 --> 01:11:55,620
joka ei ole sitä, mitä me haluamme.

874
01:11:55,620 --> 01:12:00,730
Joten estääkseen operaattorin edelle ongelmia,

875
01:12:00,730 --> 01:12:02,870
Kääri suluissa.

876
01:12:03,290 --> 01:12:07,700
Okei. Ja siinä se, 5:30.

877
01:12:08,140 --> 01:12:12,470
Jos sinulla on kysyttävää PSET, meille.

878
01:12:12,470 --> 01:12:18,010
Sen pitäisi olla hauskaa, ja hakkeri painos on myös paljon realistisempi

879
01:12:18,010 --> 01:12:22,980
kuin hakkeri painos viime vuoden, joten toivomme, että paljon yrität sitä.

880
01:12:22,980 --> 01:12:26,460
Viime vuoden oli erittäin ylivoimainen.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]