1
00:00:00,000 --> 00:00:11,904
>> [Musiikkia]

2
00:00:11,904 --> 00:00:12,910
>> PROFESSORI: Selvä.

3
00:00:12,910 --> 00:00:16,730
Tämä on CS50 ja tämä on
viikon lopussa kolme.

4
00:00:16,730 --> 00:00:20,230
Joten olemme täällä tänään, eikä Sanders
Teatteri, sen sijaan Weidner kirjasto.

5
00:00:20,230 --> 00:00:23,170
Jonka sisällä on studio
tunnetaan Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
tai sanokaamme Studio H, tai on
me say-- jos olet nauttinut että vitsi,

7
00:00:28,310 --> 00:00:30,540
se on todella maasta
luokkatoveri, Mark, verkossa,

8
00:00:30,540 --> 00:00:32,420
joka ehdotti niin paljon Twitterin kautta.

9
00:00:32,420 --> 00:00:34,270
Nyt mitä viileä noin
täällä studiossa

10
00:00:34,270 --> 00:00:38,410
on että olen ympäröi Vihreiden
seinät, green screen tai chromakey,

11
00:00:38,410 --> 00:00:43,290
niin sanoakseni, mikä tarkoittaa, että CS50: n
tuotanto joukkue, tietämättä minulle

12
00:00:43,290 --> 00:00:47,380
nyt voisi olla laskemisesta
minua eniten kaikkialla maailmassa,

13
00:00:47,380 --> 00:00:48,660
parempaan tai huonompaan.

14
00:00:48,660 --> 00:00:51,800
>> Nyt mitä on edessä, Harjoitus
kaksi on teidän käsissänne Tällä viikolla

15
00:00:51,800 --> 00:00:53,830
mutta Harjoitus
kolme tulevalla viikolla,

16
00:00:53,830 --> 00:00:56,600
teidät haastetaan kanssa
ns peli 15,

17
00:00:56,600 --> 00:00:58,960
vanhan puolueen puolesta, että
saatat muistaa saaneen

18
00:00:58,960 --> 00:01:02,030
kuin lapsi, joka on koko joukko
numeroita, jotka voivat liukua ylös, alas,

19
00:01:02,030 --> 00:01:05,790
vasemmalle ja oikealle, ja siellä on yksi aukko
sisällä palapeli, johon voit

20
00:01:05,790 --> 00:01:07,840
voi todella liukua ne palapelin palaset.

21
00:01:07,840 --> 00:01:11,150
Lopulta saat tämän
palapeli joissakin semi satunnaisessa järjestyksessä,

22
00:01:11,150 --> 00:01:12,940
ja tavoitteena on
lajitella, ylhäältä alas,

23
00:01:12,940 --> 00:01:16,310
vasemmalta oikealle, yhdestä
koko matkan läpi 15.

24
00:01:16,310 --> 00:01:19,360
>> Valitettavasti täytäntöönpano
sinulla on käsillä

25
00:01:19,360 --> 00:01:21,590
tulee olemaan ohjelmisto
pohjainen, ei fyysisesti.

26
00:01:21,590 --> 00:01:25,280
Olet todella täytyy kirjoittaa
koodia, jotka opiskelija tai käyttäjä voi

27
00:01:25,280 --> 00:01:26,760
pelata peliä 15.

28
00:01:26,760 --> 00:01:29,030
Ja itse asiassa hakkeri
painos peli 15,

29
00:01:29,030 --> 00:01:32,155
sinun on haaste toteuttaa,
ei vain pelaaminen tämän vanhan koulun

30
00:01:32,155 --> 00:01:35,010
peli, vaan ratkaiseminen
siitä, täytäntöönpanon jumala tilassa

31
00:01:35,010 --> 00:01:38,280
niin sanoakseni, että todella
ratkaisee palapeli ihmisen,

32
00:01:38,280 --> 00:01:41,080
tarjoamalla heille vihje,
jälkeen vihje, kun vihje.

33
00:01:41,080 --> 00:01:42,280
Niin siitä lisää ensi viikolla.

34
00:01:42,280 --> 00:01:43,720
Mutta se, mitä on edessä.

35
00:01:43,720 --> 00:01:47,610
>> Nyt muistaa, että aiemmin tällä viikolla
meillä oli jännitysnäytelmä, jos haluatte,

36
00:01:47,610 --> 00:01:52,560
jolloin paras teemme lajittelu
viisas oli ylärajana Big O n

37
00:01:52,560 --> 00:01:53,210
potenssiin.

38
00:01:53,210 --> 00:01:56,520
Toisin sanoen, kuplalajittelu,
valinta lajitella, lisäyslajittelun,

39
00:01:56,520 --> 00:01:59,120
ne kaikki, kun taas eri
niiden täytäntöönpanossa,

40
00:01:59,120 --> 00:02:03,480
siirretty osaksi n potenssiin käynnissä
aika hyvin pahimmassa tapauksessa.

41
00:02:03,480 --> 00:02:06,010
Ja me yleensä olettaa, että
hyvin pahimmassa tapauksessa lajitteluun

42
00:02:06,010 --> 00:02:08,814
on yksi että tuloa
ovat täysin taaksepäin.

43
00:02:08,814 --> 00:02:11,980
Ja todellakin, se kesti aivan muutaman askeleen
toteuttaa jokainen näistä algoritmeja.

44
00:02:11,980 --> 00:02:15,110
>> Nyt aivan lopussa luokan
Recall, vertasimme kuplalajittelu

45
00:02:15,110 --> 00:02:19,390
vastaan ​​valinta lajitella vastaan ​​yksi muu
että kutsuimme yhdistää lajitella tuolloin,

46
00:02:19,390 --> 00:02:22,120
ja ehdotan, että se ottaa
etuna oppitunti viikossa

47
00:02:22,120 --> 00:02:24,060
nolla, hajota ja hallitse.

48
00:02:24,060 --> 00:02:28,810
Ja jotenkin saavuttaa jonkinlaista
logaritminen käyntiaika lopulta,

49
00:02:28,810 --> 00:02:31,024
sijasta jotain
se on puhtaasti asteen.

50
00:02:31,024 --> 00:02:33,440
Ja se ei ole aivan logaritminen,
se on hieman enemmän.

51
00:02:33,440 --> 00:02:36,520
Mutta jos muistatte luokasta,
se oli paljon, paljon nopeammin.

52
00:02:36,520 --> 00:02:38,210
Katsotaanpa katsomaan mihin jäimme.

53
00:02:38,210 --> 00:02:41,880

54
00:02:41,880 --> 00:02:45,370
>> Kuplalajittelu vs. valinta
lajitella vs. Yhdistämisen lajitella.

55
00:02:45,370 --> 00:02:47,700
Nyt he kaikki käynnissä, vuonna
Teoriassa samaan aikaan.

56
00:02:47,700 --> 00:02:50,510
CPU on käynnissä samalla nopeudella.

57
00:02:50,510 --> 00:02:54,990
Mutta voit tuntea kuinka tylsää tämä
on hyvin nopeasti tulossa,

58
00:02:54,990 --> 00:02:58,790
ja kuinka nopeasti, kun pistää
hiukan viikon nolla algoritmit,

59
00:02:58,790 --> 00:03:00,080
voimme nopeuttaa asioita.

60
00:03:00,080 --> 00:03:01,630
>> Joten merkki lajitella näyttää hämmästyttävän.

61
00:03:01,630 --> 00:03:05,220
Miten voimme hyödyntää sitä, jotta
lajitella numeroita nopeammin.

62
00:03:05,220 --> 00:03:07,140
No katsotaanpa muistelen
ainesosaa että me

63
00:03:07,140 --> 00:03:10,380
oli takaisin viikolla nolla, että
etsivät joku puhelinluettelosta,

64
00:03:10,380 --> 00:03:12,380
ja muistuttaa, että
pseudokoodilla että ehdotimme,

65
00:03:12,380 --> 00:03:14,560
jonka kautta voimme löytää
joku kuten Mike Smith,

66
00:03:14,560 --> 00:03:16,310
näytti vähän jotain tällaista.

67
00:03:16,310 --> 00:03:20,820
>> Nyt katsomaan erityisesti
rivillä 7 ja 8, ja 10 ja 11,

68
00:03:20,820 --> 00:03:25,240
joka aiheuttaa että silmukka, jolloin pidimme
menee takaisin linja 3 uudestaan, ja uudestaan,

69
00:03:25,240 --> 00:03:26,520
ja uudelleen.

70
00:03:26,520 --> 00:03:31,790
Mutta käy ilmi, että voimme katsella
tämä algoritmi, täällä pseudokoodilla,

71
00:03:31,790 --> 00:03:33,620
hieman kokonaisvaltaisemmin.

72
00:03:33,620 --> 00:03:35,960
Itse asiassa, mitä etsin
klo täällä ruudulla,

73
00:03:35,960 --> 00:03:41,180
on algoritmi etsii
Mike Smith joukossa joitakin joukko sivuja.

74
00:03:41,180 --> 00:03:45,520
Ja todellakin, voisimme yksinkertaistaa tämä
algoritmi ne rivit 7 ja 8,

75
00:03:45,520 --> 00:03:49,860
ja 10 ja 11 vain sanoa,
jonka olen esitetään tässä keltaisella.

76
00:03:49,860 --> 00:03:52,210
Toisin sanoen, jos Mike
Smith on aiemmin kirja,

77
00:03:52,210 --> 00:03:55,004
meidän ei tarvitse määrittää vaiheessa
askeleelta nyt miten edetä löytää hänet.

78
00:03:55,004 --> 00:03:56,920
Meillä ei tarvitse määritellä
palata linja 3,

79
00:03:56,920 --> 00:03:58,960
Miksi emme vain sen sijaan,
sanoa yleisemmin,

80
00:03:58,960 --> 00:04:01,500
etsi Mike
vasen puoli kirjan.

81
00:04:01,500 --> 00:04:03,960
>> Toisaalta, jos Mike on
todella myöhemmin kirjan,

82
00:04:03,960 --> 00:04:07,540
miksi emme vain lainata lainaus haku
Mike oikeassa puoliskossa kirjan.

83
00:04:07,540 --> 00:04:11,030
Toisin sanoen, miksi emme vain
tavallaan punt itsellemme sanomalla,

84
00:04:11,030 --> 00:04:13,130
etsi Mike tässä
osajoukko kirjan,

85
00:04:13,130 --> 00:04:16,279
ja jättää sen nykyisiä
algoritmi kertoa meille

86
00:04:16,279 --> 00:04:18,750
miten etsiä Mike
että vasen puoli kirjan.

87
00:04:18,750 --> 00:04:20,750
Toisin sanoen, meidän
algoritmi toimii onko se

88
00:04:20,750 --> 00:04:24,670
puhelinluettelo tämän paksuus, tämän
paksuus, tai paksuus lainkaan.

89
00:04:24,670 --> 00:04:27,826
Joten voimme rekursiivisesti
määritellä tämä algoritmi.

90
00:04:27,826 --> 00:04:29,950
Toisin sanoen, on
näyttö täällä, on algoritmi

91
00:04:29,950 --> 00:04:33,130
etsimiseen Mike Smith
keskuudessa sivut puhelinluettelosta.

92
00:04:33,130 --> 00:04:37,410
Joten rivi 7 ja 10, katsotaanpa
vain sanoa juuri sitä.

93
00:04:37,410 --> 00:04:40,250
Ja käytän tätä termiä hetki
sitten, ja todellakin, rekursio

94
00:04:40,250 --> 00:04:42,450
on muotisana nyt,
ja se on tämän prosessin

95
00:04:42,450 --> 00:04:47,210
tehdä jotain syklistä jotenkin
koodia käyttämällä että sinulla jo on,

96
00:04:47,210 --> 00:04:49,722
ja kutsuen sitä uudelleen,
ja uudestaan, ja uudestaan.

97
00:04:49,722 --> 00:04:51,930
Nyt se tulee olemaan tärkeä
että me jotenkin pohja

98
00:04:51,930 --> 00:04:53,821
pois, ja älä tee sitä äärettömän pitkä.

99
00:04:53,821 --> 00:04:56,070
Muuten aiomme
on todellakin päättymättömään silmukkaan.

100
00:04:56,070 --> 00:04:59,810
Mutta katsotaan jos voimme lainata tätä ajatusta
rekursiivisen, tehdä jotain uudelleen

101
00:04:59,810 --> 00:05:03,600
ja uudestaan ​​ja uudestaan, ratkaista
lajittelu ongelma kautta yhdistämisen

102
00:05:03,600 --> 00:05:05,900
lajitella, kaikki tehokkaammin.

103
00:05:05,900 --> 00:05:06,970
>> Joten annan sinulle yhdistää lajitella.

104
00:05:06,970 --> 00:05:07,920
Katsotaanpa katsomaan.

105
00:05:07,920 --> 00:05:10,850
Joten tässä on pseudokoodilla, kanssa
jotka voisimme toteuttaa lajittelu,

106
00:05:10,850 --> 00:05:12,640
Käyttämällä tätä algoritmia kutsutaan yhdistämisen lajitella.

107
00:05:12,640 --> 00:05:13,880
Ja se on yksinkertaisesti tämä.

108
00:05:13,880 --> 00:05:15,940
Syötteellä n alkion,
Toisin sanoen, jos olet

109
00:05:15,940 --> 00:05:18,830
annettuja n elementtejä ja numeroita ja
kirjaimia tai mikä tulo on,

110
00:05:18,830 --> 00:05:22,430
jos olet antanut n elementtiä, jos
n on pienempi kuin 2, palaa.

111
00:05:22,430 --> 00:05:22,930
Oikea?

112
00:05:22,930 --> 00:05:26,430
Koska jos n on pienempi kuin 2, että
tarkoittaa, että minun luettelo elementtien

113
00:05:26,430 --> 00:05:30,446
on joko kokoa 0 tai 1, ja
sekä näissä triviaaleja tapauksissa

114
00:05:30,446 --> 00:05:31,570
luettelo on jo järjestetty.

115
00:05:31,570 --> 00:05:32,810
Jos ei ole luettelossa, se on järjestetty.

116
00:05:32,810 --> 00:05:35,185
Ja jos on lista pituus
1, se on tietenkin järjestetty.

117
00:05:35,185 --> 00:05:38,280
Joten algoritmi tarvitsee vain
todella jotain mielenkiintoista,

118
00:05:38,280 --> 00:05:40,870
jos meillä on kaksi tai useampia
elementtejä meille annettu.

119
00:05:40,870 --> 00:05:42,440
Joten katsokaamme taika sitten.

120
00:05:42,440 --> 00:05:47,500
Else järjestellä vasemmalla puolella elementtejä,
sitten lajitella oikealla puolella elementtejä,

121
00:05:47,500 --> 00:05:49,640
sitten yhdistää lajiteltu puolikkaat.

122
00:05:49,640 --> 00:05:52,440
Ja mikä on tavallaan mielen taivutus
täällä, on että en ole oikeastaan

123
00:05:52,440 --> 00:05:56,190
näyttävät määrännyt
mitään ihan vielä, eikö?

124
00:05:56,190 --> 00:05:59,560
Kaikki Olen sanonut on, annetaan luettelo
n elementtiä, lajitella vasen puoli,

125
00:05:59,560 --> 00:06:01,800
sitten oikea puoli, sitten
yhdistää lajiteltu puolikkaat,

126
00:06:01,800 --> 00:06:03,840
mutta missä on todellinen salainen kastike?

127
00:06:03,840 --> 00:06:05,260
Missä algoritmi?

128
00:06:05,260 --> 00:06:09,150
No näyttää siltä, ​​että nämä kaksi riviä
ensimmäinen, eräänlainen vasen puoli elementtejä,

129
00:06:09,150 --> 00:06:13,970
ja tavallaan oikea puoli elementtejä,
ovat rekursiokutsua, niin sanoakseni.

130
00:06:13,970 --> 00:06:16,120
>> Onhan tässä
vaiheessa, minulla on

131
00:06:16,120 --> 00:06:18,950
algoritmi, jolla voidaan
lajitella koko joukko tekijöitä?

132
00:06:18,950 --> 00:06:19,450
Kyllä.

133
00:06:19,450 --> 00:06:20,620
Se on täällä.

134
00:06:20,620 --> 00:06:25,180
Se on täällä ruudulla, ja
joten voin käyttää, että samoja vaiheita

135
00:06:25,180 --> 00:06:28,500
lajitella vasen puoli,
kuin voin oikea puoli.

136
00:06:28,500 --> 00:06:30,420
Ja todellakin, uudestaan, ja uudestaan.

137
00:06:30,420 --> 00:06:34,210
Joten tavalla tai toisella, ja me pian
nähdä tämän, taika yhdistämisen sort

138
00:06:34,210 --> 00:06:37,967
on upotettu että hyvin lopullisessa
linja, yhdistämällä lajitellut puoliskot.

139
00:06:37,967 --> 00:06:39,300
Ja joka tuntuu melko intuitiivinen.

140
00:06:39,300 --> 00:06:41,050
Otat kaksi puoliskoa, ja te,
jotenkin, yhdistää ne yhteen,

141
00:06:41,050 --> 00:06:43,260
ja näemme tämän
konkreettisesti hetki.

142
00:06:43,260 --> 00:06:45,080
>> Mutta tämä on täydellinen algoritmi.

143
00:06:45,080 --> 00:06:46,640
Ja nyt nähdä tarkalleen miksi.

144
00:06:46,640 --> 00:06:50,912
No olettaa, että meille annetaan nämä samat
kahdeksan elementtejä tässä ruudulla, yksi

145
00:06:50,912 --> 00:06:53,120
kautta kahdeksan, mutta ne ovat
näennäisen satunnaisessa järjestyksessä.

146
00:06:53,120 --> 00:06:55,320
Ja tavoite käsillä on
lajitella nämä elementit.

147
00:06:55,320 --> 00:06:58,280
No miten voin mennä noin
tekee sen avulla, jälleen,

148
00:06:58,280 --> 00:07:00,407
yhdistää lajitella, kuten per tämä pseudokoodina?

149
00:07:00,407 --> 00:07:02,740
Ja vielä, ingrain tämä
mielesi, vain hetken.

150
00:07:02,740 --> 00:07:05,270
Ensimmäinen tapaus on melko
triviaali, jos se on vähemmän kuin 2,

151
00:07:05,270 --> 00:07:07,060
vain palata, ei ole tehtävää.

152
00:07:07,060 --> 00:07:09,290
Joten oikeastaan ​​siellä on vain kolme
toimet todella pitää mielessä.

153
00:07:09,290 --> 00:07:11,081
Jälleen ja jälleen, olen
menossa haluavat olla

154
00:07:11,081 --> 00:07:13,980
lajitella vasen puoli,
lajitella oikea puoli,

155
00:07:13,980 --> 00:07:15,890
ja sitten kun niiden
kaksi puolikasta lajitellaan,

156
00:07:15,890 --> 00:07:18,710
Haluan yhdistää ne yhteen
yhdeksi lajiteltu lista.

157
00:07:18,710 --> 00:07:19,940
Niin pitää tämä mielessä.

158
00:07:19,940 --> 00:07:21,310
>> Joten tässä alkuperäisen luettelon.

159
00:07:21,310 --> 00:07:23,510
Katsotaanpa käsittelemään tätä
array, kun aloimme

160
00:07:23,510 --> 00:07:25,800
viikolla kaksi, joka on
yhtenäinen alue muistia.

161
00:07:25,800 --> 00:07:28,480
Tässä tapauksessa, joka sisältää kahdeksan
numeroita, takaisin takaisin takaisin.

162
00:07:28,480 --> 00:07:30,700
Ja lähdetään nyt sovelletaan yhdistämisen lajitella.

163
00:07:30,700 --> 00:07:33,300
Joten Haluan ensin lajitella
vasen puoli tämän luettelon,

164
00:07:33,300 --> 00:07:37,370
ja nyt, siksi,
keskittyvät 4, 8, 6, ja 2.

165
00:07:37,370 --> 00:07:41,000
>> Nyt miten voin mennä noin
lajittelun luettelo koko 4?

166
00:07:41,000 --> 00:07:45,990
No minun täytyy nyt harkita
lajittelu vasemmalla vasemmalla puolella.

167
00:07:45,990 --> 00:07:47,720
Jälleen, nyt kelata vain hetken.

168
00:07:47,720 --> 00:07:51,010
Jos pseudokoodi on tämä,
ja olen antanut kahdeksan elementtejä,

169
00:07:51,010 --> 00:07:53,230
8 on ilmeisesti suurempi
kuin tai yhtä suuri kuin 2.

170
00:07:53,230 --> 00:07:54,980
Joten ensimmäinen tapaus ei koske.

171
00:07:54,980 --> 00:07:58,120
Joten lajitella kahdeksan elementtejä, haluan ensin
lajitella vasemmalla puolella elementtejä,

172
00:07:58,120 --> 00:08:01,930
sitten lajitella oikea puoli, sitten yhdistää
kaksi lajitellut puolikkaat, kukin koko 4.

173
00:08:01,930 --> 00:08:02,470
OK.

174
00:08:02,470 --> 00:08:07,480
>> Mutta jos olet juuri kertonut minulle, lajitella
vasen puoli, joka on nyt on koko 4,

175
00:08:07,480 --> 00:08:09,350
miten voin lajitella vasen puoli?

176
00:08:09,350 --> 00:08:11,430
No jos minulla on
tuloon neljä elementtiä,

177
00:08:11,430 --> 00:08:14,590
Haluan ensin lajitella vasemmalle
kaksi, sitten oikea kaksi,

178
00:08:14,590 --> 00:08:16,210
ja sitten yhdistää ne yhteen.

179
00:08:16,210 --> 00:08:18,700
Niin uudelleen, se tulee hieman
of mielen taivutus peli täällä,

180
00:08:18,700 --> 00:08:21,450
koska te, tavallaan, on
muistaa missä olet tarina,

181
00:08:21,450 --> 00:08:23,620
mutta loppujen lopuksi,
antanut mitään useita tekijöitä,

182
00:08:23,620 --> 00:08:25,620
ensin haluat lajitella
vasen puoli, sitten oikea puoli,

183
00:08:25,620 --> 00:08:26,661
sitten yhdistää ne yhteen.

184
00:08:26,661 --> 00:08:28,630
Aloitetaan juuri siihen.

185
00:08:28,630 --> 00:08:30,170
Tässä panos kahdeksan elementtejä.

186
00:08:30,170 --> 00:08:31,910
Nyt me tarkastelemme vasen puoli täällä.

187
00:08:31,910 --> 00:08:33,720
Miten lajitella neljä elementtiä?

188
00:08:33,720 --> 00:08:35,610
No ensin lajitella vasemmalle puolen.

189
00:08:35,610 --> 00:08:37,720
Nyt miten voin lajitella vasen puoli?

190
00:08:37,720 --> 00:08:39,419
No Olen saanut kaksi elementtiä.

191
00:08:39,419 --> 00:08:41,240
Joten järjestää kaksi elementtiä.

192
00:08:41,240 --> 00:08:44,540
2 on suurempi tai
vastaa 2, tietenkin.

193
00:08:44,540 --> 00:08:46,170
Niin että ensimmäinen tapaus ei koske.

194
00:08:46,170 --> 00:08:49,010
>> Joten minulla on nyt lajitella vasemmalle
puolet näistä kahdesta elementistä.

195
00:08:49,010 --> 00:08:50,870
Vasen puoli, tietenkin, on vain 4.

196
00:08:50,870 --> 00:08:54,020
Joten miten voin lajitella luettelon yhden elementin?

197
00:08:54,020 --> 00:08:57,960
No nyt, että erityistä perustapaus
ylös, niin sanotusti, sovelletaan.

198
00:08:57,960 --> 00:09:01,470
1 on pienempi kuin 2, ja minun
luettelo on todellakin koko 1.

199
00:09:01,470 --> 00:09:02,747
Joten en juuri palata.

200
00:09:02,747 --> 00:09:03,580
En tee mitään.

201
00:09:03,580 --> 00:09:06,770
Ja todellakin, katso mitä olen
tehty, 4 on jo järjestetty.

202
00:09:06,770 --> 00:09:09,220
Kuten olen jo
osittain onnistunut tässä.

203
00:09:09,220 --> 00:09:11,750
>> Nyt näyttää typerää
vaatia, mutta se on totta.

204
00:09:11,750 --> 00:09:13,700
4 on luettelo koko 1.

205
00:09:13,700 --> 00:09:15,090
Se on jo järjestetty.

206
00:09:15,090 --> 00:09:16,270
Se vasen puoli.

207
00:09:16,270 --> 00:09:18,010
Nyt minä lajitella oikea puoli.

208
00:09:18,010 --> 00:09:22,310
Minun panos on yksi elementti, 8
Samoin jo järjestetty.

209
00:09:22,310 --> 00:09:25,170
Tyhmä, liian, mutta jälleen,
tämä perusperiaate

210
00:09:25,170 --> 00:09:28,310
aikoo jotta voimme nyt rakentaa
päälle tämän onnistuneesti.

211
00:09:28,310 --> 00:09:32,260
4 lajiteltu, 8 lajitellaan, nyt
mikä oli viimeinen askel?

212
00:09:32,260 --> 00:09:35,330
Niin kolmas ja viimeinen vaihe, mikä tahansa
kerran olet lajittelun lista, muistaa,

213
00:09:35,330 --> 00:09:38,310
oli yhdistää kaksi puolikasta,
vasemmalle ja oikealle.

214
00:09:38,310 --> 00:09:39,900
Joten juuri siihen.

215
00:09:39,900 --> 00:09:41,940
Minun vasen puoli on tietenkin, 4.

216
00:09:41,940 --> 00:09:43,310
Minun oikea puoli on 8.

217
00:09:43,310 --> 00:09:44,100
>> Joten tehdään tämä.

218
00:09:44,100 --> 00:09:46,410
Ensinnäkin aion jakaa
jotkut lisämuistia,

219
00:09:46,410 --> 00:09:48,680
että minä täällä edustan,
koska vain toissijainen array,

220
00:09:48,680 --> 00:09:49,660
joka on iso mahtuakseen tähän.

221
00:09:49,660 --> 00:09:52,243
Mutta voit kuvitella jatkamisesta
että suorakulmion koko pituudeltaan,

222
00:09:52,243 --> 00:09:53,290
jos tarvitsemme lisää myöhemmin.

223
00:09:53,290 --> 00:09:58,440
Miten otan 4 ja 8, ja yhdistää
nämä kaksi luetteloa koko 1 yhdessä?

224
00:09:58,440 --> 00:10:00,270
Tässäkin melko yksinkertainen.

225
00:10:00,270 --> 00:10:03,300
4 tulee ensin, sitten tulee 8.

226
00:10:03,300 --> 00:10:07,130
Koska jos haluan lajitella
vasen puoli, sitten oikea puoli,

227
00:10:07,130 --> 00:10:09,900
ja sitten yhdistää nämä kaksi puolikasta
yhdessä, lajiteltu järjestyksessä,

228
00:10:09,900 --> 00:10:11,940
4 tulee ensin, sitten tulee 8.

229
00:10:11,940 --> 00:10:15,810
>> Joten näytämme edistyy, vaikka
vaikka en ole tehnyt mitään varsinaista työtä.

230
00:10:15,810 --> 00:10:17,800
Mutta muista missä olemme tarina.

231
00:10:17,800 --> 00:10:19,360
Olemme alunperin kesti kahdeksan elementtejä.

232
00:10:19,360 --> 00:10:21,480
Olemme järjestetty vasen puoli, joka on 4.

233
00:10:21,480 --> 00:10:24,450
Sitten lajitellaan vasen puoli
vasemman puolen, mikä oli 2.

234
00:10:24,450 --> 00:10:25,270
Ja tässä sitä mennään.

235
00:10:25,270 --> 00:10:26,920
Olemme tehneet tämän askeleen.

236
00:10:26,920 --> 00:10:29,930
>> Joten jos olemme lajiteltu
vasen puoli 2, nyt meillä

237
00:10:29,930 --> 00:10:32,130
on lajitella oikea puoli 2.

238
00:10:32,130 --> 00:10:35,710
Joten oikea puoli 2 on
nämä kaksi arvoa täällä, 6 ja 2.

239
00:10:35,710 --> 00:10:40,620
Joten nyt ottaa panos koko
2, ja lajitella vasen puoli, ja sitten

240
00:10:40,620 --> 00:10:42,610
oikea puoli, ja sitten
yhdistää ne yhteen.

241
00:10:42,610 --> 00:10:45,722
No miten voin lajitella luettelon koko
1, joka sisältää vain numero 6?

242
00:10:45,722 --> 00:10:46,430
Olen jo tehnyt.

243
00:10:46,430 --> 00:10:48,680
Että luettelo koko 1 lajitellaan.

244
00:10:48,680 --> 00:10:52,140
>> Miten lajitella toinen luettelo
koko 1, niin sanottu oikea puoli.

245
00:10:52,140 --> 00:10:54,690
No sekin on jo järjestetty.

246
00:10:54,690 --> 00:10:56,190
Numero 2 on yksin.

247
00:10:56,190 --> 00:11:00,160
Joten nyt minulla on kaksi puoliskoa, vasemmalle ja
oikea, minun täytyy yhdistää ne yhteen.

248
00:11:00,160 --> 00:11:01,800
Annan itselleni ylimääräistä tilaa.

249
00:11:01,800 --> 00:11:05,580
Ja laittaa 2 siellä,
sitten 6 siellä, mikä

250
00:11:05,580 --> 00:11:10,740
lajittelu että luettelo, vasen ja oikea,
ja yhdistämällä se yhteen, lopulta.

251
00:11:10,740 --> 00:11:12,160
Joten olen hieman paremmassa kunnossa.

252
00:11:12,160 --> 00:11:16,250
En ole tehnyt, koska selvästi 4, 8, 2,
6 ei ole lopullinen tilaus, että haluan.

253
00:11:16,250 --> 00:11:20,640
Mutta Minulla on nyt kaksi luetteloa koko 2, että
ovat molemmat vastaavasti on lajiteltu.

254
00:11:20,640 --> 00:11:24,580
Joten nyt jos taaksepäin sielusi
silmä, mistä se jättää meidät?

255
00:11:24,580 --> 00:11:28,520
Aloitin kahdeksan elementtejä, niin minä
supistetaan se alas vasemmalla puolella 4,

256
00:11:28,520 --> 00:11:31,386
sitten vasen puoli 2, ja
sitten oikea puoli 2,

257
00:11:31,386 --> 00:11:34,510
Lopetin, siis, lajittelu vasen
puolet 2, ja oikea puoli 2,

258
00:11:34,510 --> 00:11:37,800
niin mitä kolmas ja viimeinen vaihe tässä?

259
00:11:37,800 --> 00:11:41,290
Minun täytyy yhdistää yhdessä
kaksi luetteloa koko 2.

260
00:11:41,290 --> 00:11:42,040
Joten mene eteenpäin.

261
00:11:42,040 --> 00:11:43,940
Ja ruudulla täällä, antaa
minulle lisämuistia,

262
00:11:43,940 --> 00:11:47,170
vaikka teknisesti, huomaa, että olen
sai koko joukko tyhjä tila ylös

263
00:11:47,170 --> 00:11:47,670
siellä.

264
00:11:47,670 --> 00:11:50,044
Jos haluan olla erityisen
tehokkaasti tilaa viisas,

265
00:11:50,044 --> 00:11:52,960
Voisin vain alkaa liikkuvat osat
edestakaisin, ylhäällä ja alhaalla.

266
00:11:52,960 --> 00:11:55,460
Mutta vain visuaalinen selkeys,
Aion laittaa se alas alla,

267
00:11:55,460 --> 00:11:56,800
pitää asiat mukava ja puhdas.

268
00:11:56,800 --> 00:11:58,150
>> Joten minulla kaksi luetteloa koko 2.

269
00:11:58,150 --> 00:11:59,770
Ensimmäinen luettelo on 4 ja 8.

270
00:11:59,770 --> 00:12:01,500
Toisessa luettelossa on 2 ja 6.

271
00:12:01,500 --> 00:12:03,950
Katsotaanpa yhdistää ne
yhdessä lajiteltu järjestyksessä.

272
00:12:03,950 --> 00:12:09,910
2, tietenkin, tulee ensin,
sitten 4, sitten 6, sitten 8.

273
00:12:09,910 --> 00:12:12,560
Ja nyt me näyttävät saada
jonnekin mielenkiintoinen.

274
00:12:12,560 --> 00:12:15,720
Nyt olen lajiteltu puolet
luetella, ja sattumalta, se on

275
00:12:15,720 --> 00:12:18,650
kaikki parilliset numerot, mutta että
on todellakin vain sattumaa.

276
00:12:18,650 --> 00:12:22,220
Ja nyt on lajiteltu vasen
puoli, että se on 2, 4, 6, ja 8.

277
00:12:22,220 --> 00:12:23,430
Mikään ei ole epäkunnossa.

278
00:12:23,430 --> 00:12:24,620
Joka tuntuu edistystä.

279
00:12:24,620 --> 00:12:26,650
>> Nyt tuntuu kuin olisin
puhuneet ikuisesti nyt,

280
00:12:26,650 --> 00:12:29,850
niin mitä jää nähtäväksi, jos tämä
algoritmi on todellakin tehokkaampi.

281
00:12:29,850 --> 00:12:31,766
Mutta olemme menossa läpi
se erittäin järjestelmällisesti.

282
00:12:31,766 --> 00:12:34,060
Tietokone, tietenkin,
tekisi sen niin.

283
00:12:34,060 --> 00:12:34,840
Missä siis olemme?

284
00:12:34,840 --> 00:12:36,180
Aloitimme kahdeksan elementtejä.

285
00:12:36,180 --> 00:12:37,840
Olen lajiteltu vasemmalla puolella 4.

286
00:12:37,840 --> 00:12:39,290
Näytän tehdä sen kanssa.

287
00:12:39,290 --> 00:12:42,535
Joten nyt seuraava askel on
lajitella oikea puoli 4.

288
00:12:42,535 --> 00:12:44,410
Ja tämä osa voimme mennä
läpi hieman enemmän

289
00:12:44,410 --> 00:12:47,140
nopeasti, vaikka olet
Tervetuloa kelata tai pysäyttää, vain

290
00:12:47,140 --> 00:12:49,910
ajatella sen läpi
omaan tahtiin, mutta mitä

291
00:12:49,910 --> 00:12:53,290
meillä nyt on tilaisuus
tehdä täsmälleen samaa algoritmia neljään

292
00:12:53,290 --> 00:12:54,380
eri numeroille.

293
00:12:54,380 --> 00:12:57,740
>> Joten mene eteenpäin, ja keskitytään
oikea puoli, jotka olemme täällä.

294
00:12:57,740 --> 00:13:01,260
Vasen puoli on, että
oikea puoli, ja nyt

295
00:13:01,260 --> 00:13:04,560
vasen puoli vasemman
puolet oikea puoli,

296
00:13:04,560 --> 00:13:08,030
ja miten lajitella luettelon koko
1, joka sisälsi vain numero 1?

297
00:13:08,030 --> 00:13:09,030
Se on jo tehty.

298
00:13:09,030 --> 00:13:11,830
Miten teen sama lista
koon 1, joka sisältää vain 7?

299
00:13:11,830 --> 00:13:12,840
Se on jo tehty.

300
00:13:12,840 --> 00:13:16,790
Vaihe kolme tähän puoli sitten
on yhdistää nämä kaksi tekijää

301
00:13:16,790 --> 00:13:20,889
uuteen luettelo koko 2, 1 ja 7.

302
00:13:20,889 --> 00:13:23,180
Eivät näytä tehneen kaikki
että paljon mielenkiintoista työtä.

303
00:13:23,180 --> 00:13:24,346
Katsotaan, mitä tapahtuu seuraavaksi.

304
00:13:24,346 --> 00:13:29,210
Olen juuri järjestetty vasemmalla puolella
oikea puoli minun alkuperäinen panos.

305
00:13:29,210 --> 00:13:32,360
Nyt lajitella oikealla
puoli, joka sisältää 5 ja 3.

306
00:13:32,360 --> 00:13:35,740
Katsotaanpa jälleen katsoa vasemmalle
puoli, lajiteltu, oikea puoli, lajiteltu,

307
00:13:35,740 --> 00:13:39,120
ja yhdistää nämä kaksi yhdessä,
johonkin lisätilaa,

308
00:13:39,120 --> 00:13:41,670
3 tulee ensin, sitten tulee 5.

309
00:13:41,670 --> 00:13:46,190
Ja nyt olemme lajiteltu
vasemmalla puolella oikea puoli

310
00:13:46,190 --> 00:13:49,420
alkuperäisen ongelman, ja
oikea puoli oikea puoli

311
00:13:49,420 --> 00:13:50,800
alkuperäisen ongelman.

312
00:13:50,800 --> 00:13:52,480
Mikä on kolmas ja viimeinen vaihe?

313
00:13:52,480 --> 00:13:54,854
Hyvin yhdistää nämä kaksi puolikasta yhteen.

314
00:13:54,854 --> 00:13:57,020
Joten haluan saada itselleni
lisätilaa, mutta, jälleen, minä

315
00:13:57,020 --> 00:13:58,699
saattaa käyttää, että vapaata tilaa ylös.

316
00:13:58,699 --> 00:14:00,490
Mutta aiomme pitää
se yksinkertainen visuaalisesti.

317
00:14:00,490 --> 00:14:07,070
Saanen sulautuvat nyt 1, ja
sitten 3, ja sitten 5, ja sitten 7.

318
00:14:07,070 --> 00:14:10,740
Mikä jättää minua nyt
oikeus puolet alkuperäisestä ongelmasta

319
00:14:10,740 --> 00:14:12,840
joka on täydellisesti lajitellaan.

320
00:14:12,840 --> 00:14:13,662
>> Niin mitä jää jäljelle?

321
00:14:13,662 --> 00:14:16,120
Tunnen pitää sanoa
samat asiat uudestaan, ja uudestaan,

322
00:14:16,120 --> 00:14:18,700
mutta se kuvastaa
Se, että käytämme rekursion.

323
00:14:18,700 --> 00:14:21,050
Prosessi käyttää
algoritmi uudestaan, ja uudestaan,

324
00:14:21,050 --> 00:14:23,940
pienempiin osajoukot
alkuperäiseen ongelmaan.

325
00:14:23,940 --> 00:14:27,580
Joten minulla on nyt vasemmalle lajiteltu
puolet alkuperäisestä ongelmasta.

326
00:14:27,580 --> 00:14:30,847
Minulla on oikeus lajitellut puoli
alkuperäisen ongelman.

327
00:14:30,847 --> 00:14:32,180
Mikä on kolmas ja viimeinen vaihe?

328
00:14:32,180 --> 00:14:33,590
Voi, se on sulautuvat.

329
00:14:33,590 --> 00:14:34,480
Joten tehdä.

330
00:14:34,480 --> 00:14:36,420
Katsotaanpa jakaa joitakin uusia
muisti, mutta luoja, me

331
00:14:36,420 --> 00:14:37,503
voisi laittaa sen minne nyt.

332
00:14:37,503 --> 00:14:40,356
Meillä on niin paljon tilaa
meille, mutta me pitää se yksinkertainen.

333
00:14:40,356 --> 00:14:42,730
Sijaan menee takaisin ja
esiin ja alkuperäistä muistia,

334
00:14:42,730 --> 00:14:44,480
Haluan vain tehdä se
visuaalisesti täällä alla,

335
00:14:44,480 --> 00:14:47,240
loppuun asti sulautuvien
vasen puoli ja oikea puoli.

336
00:14:47,240 --> 00:14:49,279
>> Joten yhdistämällä, mitä minun pitää tehdä?

337
00:14:49,279 --> 00:14:50,820
Haluan ottaa elementtejä järjestyksessä.

338
00:14:50,820 --> 00:14:53,230
Joten etsit vasen puoli,
Näen ensimmäinen numero on 2.

339
00:14:53,230 --> 00:14:55,230
Katson oikea puoli,
Näen ensimmäinen numero

340
00:14:55,230 --> 00:14:58,290
on 1, niin ilmeisesti joka
numero Haluanko nyppiä pois,

341
00:14:58,290 --> 00:15:00,430
ja laittaa ensimmäinen minun lopullisen luettelon?

342
00:15:00,430 --> 00:15:01,449
Tietenkin, 1.

343
00:15:01,449 --> 00:15:02,990
Nyt haluan kysyä saman kysymyksen.

344
00:15:02,990 --> 00:15:05,040
Vasemmalla puolella, olen
silti saanut numero 2.

345
00:15:05,040 --> 00:15:07,490
Oikealla puoliskolla,
Minulla numero 3.

346
00:15:07,490 --> 00:15:08,930
Kumpi minä haluan valita?

347
00:15:08,930 --> 00:15:11,760
Tietenkin, numero 2 ja
nyt huomaa ehdokkaat

348
00:15:11,760 --> 00:15:13,620
4 vasemmalla, 3 oikealla.

349
00:15:13,620 --> 00:15:15,020
Katsotaanpa, tietenkin, valitse 3.

350
00:15:15,020 --> 00:15:18,020
Nyt ehdokkaat ovat 4
vasemmalla, 5 oikealla.

351
00:15:18,020 --> 00:15:19,460
Me tietenkin valita 4.

352
00:15:19,460 --> 00:15:21,240
6 vasemmalla, 5 oikealla.

353
00:15:21,240 --> 00:15:22,730
Me tietenkin valita 5.

354
00:15:22,730 --> 00:15:25,020
6 vasemmalla, 7 oikealla.

355
00:15:25,020 --> 00:15:29,320
Valitsemme 6, ja sitten me
valita 7, ja sitten päätämme 8.

356
00:15:29,320 --> 00:15:30,100
Voila.

357
00:15:30,100 --> 00:15:34,370
>> Joten valtava määrä sanoja myöhemmin, me
ovat lajiteltu tämä lista kahdeksan toiminnallisuutta

358
00:15:34,370 --> 00:15:38,450
listaan ​​yhden kautta kahdeksan,
joka on kasvaa jokaisessa vaiheessa,

359
00:15:38,450 --> 00:15:40,850
mutta kuinka paljon aikaa ja teki
se vie meidät siihen.

360
00:15:40,850 --> 00:15:43,190
No Olen tarkoituksella
laid asioita kuvallisesti

361
00:15:43,190 --> 00:15:46,330
täällä, jotta voimme tavallaan
nähdä tai arvostaa divisioona

362
00:15:46,330 --> 00:15:49,060
valloittavat että on tapahtunut.

363
00:15:49,060 --> 00:15:52,830
>> Todellakin jos muistella vanavedessä,
Olen jättänyt kaikki nämä pisteviivoilla

364
00:15:52,830 --> 00:15:55,660
paikallaan haltijoille, voit,
sellainen, katso, päinvastaisessa järjestyksessä,

365
00:15:55,660 --> 00:15:58,800
jos sellainen muistella
historia nyt, minun alkuperäinen lista

366
00:15:58,800 --> 00:16:00,250
on, tietenkin, koon 8.

367
00:16:00,250 --> 00:16:03,480
Ja sitten aikaisemmin, olin
käsittelevät kaksi luetteloa koko 4,

368
00:16:03,480 --> 00:16:08,400
ja sitten neljä luettelot koko 2,
ja sitten kahdeksan luettelot koko 1.

369
00:16:08,400 --> 00:16:10,151
>> Mitä tämä,
sellainen, muistuttaa teitä?

370
00:16:10,151 --> 00:16:11,858
Hyvin, itse asiassa, mitä tahansa
algoritmit olemme

371
00:16:11,858 --> 00:16:14,430
Katsoin toistaiseksi jossa
jakaa, ja jakaa, ja jakaa,

372
00:16:14,430 --> 00:16:19,500
pitää ottaa asioita uudelleen, ja
jälleen, johtaa tämä yleinen ajatus.

373
00:16:19,500 --> 00:16:23,100
Ja niin siellä on jotain
logaritminen tekeillä.

374
00:16:23,100 --> 00:16:26,790
Ja se ei ole aivan loki n, mutta
siellä on logaritminen komponentti

375
00:16:26,790 --> 00:16:28,280
mitä olemme juuri tehneet.

376
00:16:28,280 --> 00:16:31,570
>> Nyt pohtia, miten se todella on.

377
00:16:31,570 --> 00:16:34,481
Joten log n, taas oli
suuri käyntiaika,

378
00:16:34,481 --> 00:16:36,980
kun teimme jotain
binäärihakupuu, kuten me nyt kutsumme sitä,

379
00:16:36,980 --> 00:16:40,090
hajota ja hallitse strategia
jonka kautta löysimme Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Nyt teknisesti.

381
00:16:41,020 --> 00:16:43,640
Se on log pohja 2 n, jopa
vaikka useimmissa matematiikka luokissa,

382
00:16:43,640 --> 00:16:45,770
10 on yleensä pohja että oletat.

383
00:16:45,770 --> 00:16:48,940
Mutta tietotekniikan tutkijoita lähes aina
ajatella ja puhutaan pohja 2,

384
00:16:48,940 --> 00:16:52,569
joten me yleensä vain sanoa loki
n, sen sijaan, että tukin pohjaan 2 n,

385
00:16:52,569 --> 00:16:55,110
mutta ne ovat täsmälleen yksi ja
Sama maailmassa tietokone

386
00:16:55,110 --> 00:16:57,234
tiede, ja syrjään,
on jatkuva tekijä

387
00:16:57,234 --> 00:17:01,070
Ero näiden kahden välillä, joten se on
kiistanalainen joka tapauksessa, enemmän muodollista syistä.

388
00:17:01,070 --> 00:17:04,520
>> Mutta nyt, mitä me välitämme
Tietoja on tässä esimerkissä.

389
00:17:04,520 --> 00:17:08,520
Joten ei osoittaa esimerkkiä, mutta
Ainakin käyttää esimerkiksi numeroita

390
00:17:08,520 --> 00:17:10,730
käsillä järki tarkistaa, jos haluatte.

391
00:17:10,730 --> 00:17:14,510
Joten aiemmin kaava oli log pohja
2 n, mutta mikä on n tässä asiassa.

392
00:17:14,510 --> 00:17:18,526
Minulla oli n alkuperäinen numeroita tai 8
Alkuperäisen numero erityisesti.

393
00:17:18,526 --> 00:17:20,359
Nyt se on ollut hieman
vaikka, mutta olen melko

394
00:17:20,359 --> 00:17:25,300
Varmista, että log pohja 2
arvo 8 on 3,

395
00:17:25,300 --> 00:17:29,630
ja todellakin, mitä kiva siitä on
että 3 on juuri monta kertaa

396
00:17:29,630 --> 00:17:33,320
että voit jakaa lista
pituuden 8 uudestaan, ja uudestaan,

397
00:17:33,320 --> 00:17:36,160
ja uudelleen, kunnes olet jäänyt
luettelot vain koko 1.

398
00:17:36,160 --> 00:17:36,660
Oikea?

399
00:17:36,660 --> 00:17:40,790
8 menee 4, menee 2,
menee 1, ja se on

400
00:17:40,790 --> 00:17:43,470
heijastava nimenomaan kyseisen
kuva meillä oli vain hetki sitten.

401
00:17:43,470 --> 00:17:47,160
Niin vähän järki tarkistaa, missä
logaritmi on todella mukana.

402
00:17:47,160 --> 00:17:50,180
>> Joten nyt, mitä muuta on mukana tässä? n.

403
00:17:50,180 --> 00:17:53,440
Niin huomaa, että jokainen
kerta kun jakaa luettelon,

404
00:17:53,440 --> 00:17:58,260
vaikkakin käänteisessä järjestyksessä historiassa
täällä, olin vielä tekemässä n asioita.

405
00:17:58,260 --> 00:18:02,320
Että sulautuvan vaihe edellytti, että
Kosketan jokainen numeroita,

406
00:18:02,320 --> 00:18:05,060
jotta työnnä se
sen sopivaan paikkaan.

407
00:18:05,060 --> 00:18:10,760
Joten vaikka korkeus tämän
kaavio on koko lokin n n tai 3,

408
00:18:10,760 --> 00:18:13,860
Erityisesti, toisin sanoen,
Tein kolme divisioonaa täällä.

409
00:18:13,860 --> 00:18:18,800
Kuinka paljon työtä minä tein vaakasuunnassa
pitkin tämä kaavio joka kerta?

410
00:18:18,800 --> 00:18:21,110
>> No, tein n vaiheet
työtä, koska jos olen

411
00:18:21,110 --> 00:18:24,080
sai neljä elementit ja neljä elementtiä,
ja minun täytyy yhdistää ne yhteen.

412
00:18:24,080 --> 00:18:26,040
Minun täytyy mennä läpi
nämä neljä ja nämä neljä,

413
00:18:26,040 --> 00:18:28,123
lopulta yhdistää ne
takaisin kahdeksan elementtejä.

414
00:18:28,123 --> 00:18:32,182
Jos päinvastoin Minulla kahdeksan sormea
tänne, jota en ole, ja kahdeksan

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry--, jos olen
sai neljä sormea ​​tänne,

416
00:18:34,390 --> 00:18:37,380
jota en, neljä sormea
tänne, jota en,

417
00:18:37,380 --> 00:18:40,590
niin se sama
Esimerkiksi kuten ennenkin, jos en

418
00:18:40,590 --> 00:18:44,010
on kahdeksan sormea ​​vaikka
yhteensä, jota voin, sellainen, do.

419
00:18:44,010 --> 00:18:47,950
Voin tarkalleen tehdä täällä,
Sitten voin varmasti

420
00:18:47,950 --> 00:18:50,370
yhdistää kaikki nämä luettelot
on koko 1 yhdessä.

421
00:18:50,370 --> 00:18:54,050
Mutta en todellakaan tarvitse katsoa
kunkin alkion tasan kerran.

422
00:18:54,050 --> 00:18:59,640
Joten korkeus tämä prosessi on loki n,
leveys tämän prosessin, niin sanoakseni,

423
00:18:59,640 --> 00:19:02,490
on n, niin mitä me näytämme
on, lopulta, on

424
00:19:02,490 --> 00:19:06,470
ajoaika koko n kertaa log n.

425
00:19:06,470 --> 00:19:08,977
>> Toisin sanoen, jaoimme
lista, log n kertaa,

426
00:19:08,977 --> 00:19:11,810
mutta joka kerta teimme että meillä oli
koskettaa jokainen elementtien

427
00:19:11,810 --> 00:19:13,560
jotta yhdistää ne
kaikki yhdessä, jotka

428
00:19:13,560 --> 00:19:18,120
oli n kappaletta askel, joten meillä on n kertaa log n,
tai tietojenkäsittelytieteessä sanoisi,

429
00:19:18,120 --> 00:19:20,380
asymptoottisesti, joka
olisi iso sana

430
00:19:20,380 --> 00:19:22,810
kuvaamaan ylempään
sidottu aika,

431
00:19:22,810 --> 00:19:28,010
meillä on käynnissä iso O
log n aikaa, niin sanoakseni.

432
00:19:28,010 --> 00:19:31,510
>> Nyt tämä on merkittävä, koska
muistaa, mitä käynnissä ajat olivat

433
00:19:31,510 --> 00:19:34,120
kupla lajitella, ja valinta
lajitella, ja lisäyslajittelun,

434
00:19:34,120 --> 00:19:38,200
ja jopa muutamia muita olemassa,
n potenssiin oli kun olimme.

435
00:19:38,200 --> 00:19:39,990
Ja voit, tavallaan, katso täällä.

436
00:19:39,990 --> 00:19:45,720
Jos n potenssiin on selvästi n kertaa
n, mutta täällä meillä on n kertaa log n,

437
00:19:45,720 --> 00:19:48,770
ja tiedämme jo viikko
nolla, että log n, logaritminen,

438
00:19:48,770 --> 00:19:50,550
on parempi kuin jotain lineaarinen.

439
00:19:50,550 --> 00:19:52,930
Onhan muistaa kuva
kanssa punainen ja keltainen

440
00:19:52,930 --> 00:19:56,500
ja vihreät viivat että me kiinnitti,
vihreä logaritminen linja oli paljon pienempi.

441
00:19:56,500 --> 00:20:00,920
Ja siksi, paljon paremmin ja nopeammin
kuin suora keltainen ja punainen linjat,

442
00:20:00,920 --> 00:20:05,900
n kertaa log n on todellakin parempi
kuin n kertaa n, tai n neliö.

443
00:20:05,900 --> 00:20:09,110
>> Joten meillä näyttää
tunnistettu algoritmi yhdistämisen

444
00:20:09,110 --> 00:20:11,870
lajitella, joka toimii paljon
lyhyemmän ajan, ja todellakin,

445
00:20:11,870 --> 00:20:16,560
siksi, aiemmin tällä viikolla, kun
näimme että kilpailun välillä kupla

446
00:20:16,560 --> 00:20:20,750
lajitella, valinta lajitella, ja yhdistää
lajitella, yhdistäminen lajitella todella, todella voitti.

447
00:20:20,750 --> 00:20:23,660
Ja todellakin, emme edes odota
varten kuplalajittelu ja valinta lajitella

448
00:20:23,660 --> 00:20:24,790
saada valmiiksi.

449
00:20:24,790 --> 00:20:27,410
>> Nyt ottaa yksi muu syöttö
tässä, mistä hieman

450
00:20:27,410 --> 00:20:31,030
muodollinen näkökulmasta, vain
tapauksessa tämä resonoi paremmin

451
00:20:31,030 --> 00:20:33,380
kuin tämän korkeamman tason keskustelu.

452
00:20:33,380 --> 00:20:34,880
Joten tässä on algoritmi uudelleen.

453
00:20:34,880 --> 00:20:36,770
Katsotaanpa kysyä itseltämme,
mitä käyntiaika

454
00:20:36,770 --> 00:20:39,287
on tämän algoritmit eri vaiheet?

455
00:20:39,287 --> 00:20:41,620
Katsotaanpa se jaetaan ensimmäiseen
tapaus ja toisessa tapauksessa.

456
00:20:41,620 --> 00:20:46,280
IF ja muu IF tapauksessa,
Jos N on pienempi kuin 2, palaa.

457
00:20:46,280 --> 00:20:47,580
Tuntuu vakio aikaa.

458
00:20:47,580 --> 00:20:50,970
Se on, tavallaan, kuten kahdessa vaiheessa,
Jos n on pienempi kuin 2, palaa sitten.

459
00:20:50,970 --> 00:20:54,580
Mutta kuten sanoi maanantaina,
vakio aikaa, tai Big O 1,

460
00:20:54,580 --> 00:20:57,130
voi olla kahdessa vaiheessa, kolme
vaiheet, jopa 1000 askelta.

461
00:20:57,130 --> 00:20:59,870
Tärkeintä on, että se on
jatkuva useita vaiheita.

462
00:20:59,870 --> 00:21:03,240
Joten keltainen korostettu pseudokoodina
täällä toimii, me kutsumme sitä,

463
00:21:03,240 --> 00:21:04,490
vakio aikaa.

464
00:21:04,490 --> 00:21:06,780
Joten enemmän virallisesti, ja
aiomme to-- tämä

465
00:21:06,780 --> 00:21:09,910
on se, missä määrin me
virallistaa tämän oikeuden now-- T n,

466
00:21:09,910 --> 00:21:15,030
ajoaika ongelma
joka vie n somethings syötteenä

467
00:21:15,030 --> 00:21:19,150
Yhtä suuri O yhden,
Jos n on pienempi kuin 2.

468
00:21:19,150 --> 00:21:20,640
Joten on edellytyksenä, että.

469
00:21:20,640 --> 00:21:24,150
Joten olla selkeä, jos n on pienempi kuin
2, meillä on hyvin lyhyt lista, sitten

470
00:21:24,150 --> 00:21:29,151
ajoaika, T, n, missä n on
1 tai 0, tässä hyvin erityinen tapaus,

471
00:21:29,151 --> 00:21:30,650
se vain tulee olemaan vakio aikaa.

472
00:21:30,650 --> 00:21:32,691
Se tulee ottaa yksi
vaihe, kaksi vaihetta riippumatta.

473
00:21:32,691 --> 00:21:33,950
Se on kiinteä useita vaiheita.

474
00:21:33,950 --> 00:21:38,840
>> Niin mehukas osa on varmasti vuonna
Toisessa tapauksessa vuonna pseudokoodina.

475
00:21:38,840 --> 00:21:40,220
ELSE tapaus.

476
00:21:40,220 --> 00:21:44,870
Lajittele vasemmalla puolella elementtejä, lajitella oikea
puolet elementtejä, yhdistää lajiteltu puolikkaat.

477
00:21:44,870 --> 00:21:46,800
Kuinka kauan kukin näistä askeleensa?

478
00:21:46,800 --> 00:21:49,780
No, jos käynnissä
aika lajitella n elementtiä

479
00:21:49,780 --> 00:21:53,010
on, kutsukaamme sitä hyvin
yleisesti, T, n,

480
00:21:53,010 --> 00:21:55,500
sitten lajittelu vasen
puolet elementit

481
00:21:55,500 --> 00:21:59,720
on, tavallaan, kuin sanoisi,
T n jaettuna 2,

482
00:21:59,720 --> 00:22:03,000
ja samoin lajittelu oikea puoli
elementtejä on, sellainen, kuin sanoisi,

483
00:22:03,000 --> 00:22:06,974
T n jaettu 2, ja sitten
yhdistämällä lajiteltu puolikkaat.

484
00:22:06,974 --> 00:22:08,890
No jos minulla joitakin
alkioiden lukumäärä täällä,

485
00:22:08,890 --> 00:22:11,230
kuten neljä, ja jotkut numero
elementtejä täällä, kuten neljä,

486
00:22:11,230 --> 00:22:14,650
ja minun täytyy yhdistää kuhunkin neljään
vuonna, ja jokainen näistä neljä, yksi

487
00:22:14,650 --> 00:22:17,160
toisensa jälkeen siten, että
lopulta minulla on kahdeksan elementtejä.

488
00:22:17,160 --> 00:22:20,230
Tuntuu, että on iso o n vaiheet?

489
00:22:20,230 --> 00:22:23,500
Jos Minulla n sormien ja kukin
ne on tarkoitus sisällyttää paikalleen,

490
00:22:23,500 --> 00:22:25,270
se on kuin toinen n vaiheet.

491
00:22:25,270 --> 00:22:27,360
>> Joten todellakin formulaically,
Voimme ilmaista tämän,

492
00:22:27,360 --> 00:22:29,960
vaikkakin hieman pelottavan aluksi
silmäyksellä, mutta se on jotain

493
00:22:29,960 --> 00:22:31,600
että kaappaa juuri tätä logiikkaa.

494
00:22:31,600 --> 00:22:35,710
Juokseva aika, T, n, jos n
on suurempi tai yhtä suuri kuin 2.

495
00:22:35,710 --> 00:22:42,500
Tässä tapauksessa, MUUTEN tapauksessa on T n
jaettuna 2, sekä T N jaettuna 2,

496
00:22:42,500 --> 00:22:45,320
plus Big O n, jotkut
lineaarinen useita vaiheita,

497
00:22:45,320 --> 00:22:51,630
ehkä täsmälleen n, ehkä 2 kertaa
n, mutta se on karkeasti, jotta n.

498
00:22:51,630 --> 00:22:54,060
Niin että myös, miten voimme
ilmaista tämä formulaically.

499
00:22:54,060 --> 00:22:56,809
Nyt et tiedä tätä, ellei
olet tallentanut sen mielessäsi,

500
00:22:56,809 --> 00:22:58,710
tai etsiä se
takana oppikirja, joka

501
00:22:58,710 --> 00:23:00,501
saattaa olla hieman
huijata arkki lopussa,

502
00:23:00,501 --> 00:23:03,940
mutta tämä on todellakin menossa
antaa meille iso O n log n,

503
00:23:03,940 --> 00:23:06,620
koska toistumisen että
näette täällä ruudulla,

504
00:23:06,620 --> 00:23:09,550
jos todella teki sen ulos, kanssa
ääretön määrä esimerkkejä,

505
00:23:09,550 --> 00:23:13,000
tai teit sen formulaically, olisit
nähdä, että tämä, koska tämä kaava

506
00:23:13,000 --> 00:23:17,100
itsessään on rekursiivinen, jossa t
n yli jotain oikealla,

507
00:23:17,100 --> 00:23:21,680
ja t N yli vasemmalla, tämä voi
todella ilmaistava, lopulta,

508
00:23:21,680 --> 00:23:24,339
niin suuri irti n log n.

509
00:23:24,339 --> 00:23:26,130
Jos ei vakuuttunut, että on
hieno nyt, vain

510
00:23:26,130 --> 00:23:28,960
ottaa uskossa, että se on todellakin,
mitä se toistuminen johtaa,

511
00:23:28,960 --> 00:23:31,780
mutta tämä on vain hieman enemmän
matemaattinen lähestymistapa näköinen

512
00:23:31,780 --> 00:23:36,520
klo ajoaika yhdistämisen sort
perustuvat sen pseudokoodilla yksin.

513
00:23:36,520 --> 00:23:39,030
>> Nyt kestää vähän
hengähdystauon kaiken tämän,

514
00:23:39,030 --> 00:23:41,710
ja katsomaan
tiettyjä entinen senaattori, joka

515
00:23:41,710 --> 00:23:44,260
saattaa näyttää hieman tuttu,
joka istui Googlen Eric

516
00:23:44,260 --> 00:23:48,410
Schmidt, jokin aika sitten, haastatteluun
lavalla, edessä koko joukko

517
00:23:48,410 --> 00:23:53,710
ihmiset, puhuvat lopulta noin
aihe, joka on aika nyt tuttu.

518
00:23:53,710 --> 00:23:54,575
Katsotaanpa katsomaan.

519
00:23:54,575 --> 00:24:01,020

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt: Nyt senaattori,
olet täällä Googlessa,

521
00:24:03,890 --> 00:24:09,490
ja haluan ajatella
puheenjohtajuudesta työhaastattelu.

522
00:24:09,490 --> 00:24:11,712
Nyt on vaikea saada työtä presidenttinä.

523
00:24:11,712 --> 00:24:12,670
Presidentti Obama: Oikea.

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt: Ja olet
aikoo tehdä [kuulumattomiin] nyt.

525
00:24:13,940 --> 00:24:15,523
On myös vaikea saada työtä Google.

526
00:24:15,523 --> 00:24:17,700
Presidentti Obama: Oikea.

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt: Meillä on kysymyksiä,
ja pyydämme ehdokkaita kysymyksiä,

528
00:24:21,330 --> 00:24:24,310
ja tämä yksi on Larry Schwimmer.

529
00:24:24,310 --> 00:24:25,890
>> Presidentti Obama: OK.

530
00:24:25,890 --> 00:24:27,005
>> Eric Schmidt: Mitä?

531
00:24:27,005 --> 00:24:28,130
Te ajatella olen tosissasi?

532
00:24:28,130 --> 00:24:30,590
Se on täällä.

533
00:24:30,590 --> 00:24:33,490
Mikä on tehokkain tapa
lajitella miljoona 32 bittisiä kokonaislukuja?

534
00:24:33,490 --> 00:24:37,560

535
00:24:37,560 --> 00:24:38,979
>> Presidentti Obama: Well--

536
00:24:38,979 --> 00:24:41,020
Eric Schmidt: Joskus
ehkä olen pahoillani, maybe--

537
00:24:41,020 --> 00:24:42,750
Presidentti Obama: Ei, ei,
ei, ei, ei, minä think--

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt: Se ei ole it--

539
00:24:43,240 --> 00:24:45,430
Presidentti Obama: I
ajatella, mielestäni kupla

540
00:24:45,430 --> 00:24:46,875
lajitella olisi väärä tapa edetä.

541
00:24:46,875 --> 00:24:49,619

542
00:24:49,619 --> 00:24:50,535
Eric Schmidt: Tule.

543
00:24:50,535 --> 00:24:52,200
Jotka kertoivat hänelle tämän?

544
00:24:52,200 --> 00:24:54,020
OK.

545
00:24:54,020 --> 00:24:55,590
En tietojenkäsittelytieteen on--

546
00:24:55,590 --> 00:24:58,986
>> Presidentti Obama: Olemme
saimme vakoojia siellä.

547
00:24:58,986 --> 00:24:59,860
PROFESSORI: Selvä.

548
00:24:59,860 --> 00:25:03,370
Jätetään taaksemme nyt
teoreettinen maailma algoritmien

549
00:25:03,370 --> 00:25:06,520
vuonna asymptoottinen analyysi
sen, ja palata joitakin aiheita

550
00:25:06,520 --> 00:25:09,940
viikosta nolla ja yksi, ja alku
poistaa joitakin apupyörät,

551
00:25:09,940 --> 00:25:10,450
jos haluatte.

552
00:25:10,450 --> 00:25:13,241
Niin että te todella ymmärtää
lopulta maasta ylös, mitä

553
00:25:13,241 --> 00:25:16,805
meneillään alla huppu, kun
kirjoittaa, kääntää, ja suorittaa ohjelmia.

554
00:25:16,805 --> 00:25:19,680
Recall erityisesti, että tämä oli
ensimmäinen C-ohjelma me katsoimme,

555
00:25:19,680 --> 00:25:22,840
Canonical, yksinkertainen ohjelma
tapaisena suhteellisesti

556
00:25:22,840 --> 00:25:24,620
jolloin se tulostaa, Hello World.

557
00:25:24,620 --> 00:25:27,610
Ja muistaa, että minä sanoin, prosessi
että lähdekoodi menee läpi

558
00:25:27,610 --> 00:25:28,430
on juuri tämä.

559
00:25:28,430 --> 00:25:31,180
Otat lähdekoodia, siirtää
se läpi kääntäjä, kuten kalahtaa,

560
00:25:31,180 --> 00:25:34,650
ja ulos tulee kohdekoodin, että
voisi näyttää tältä, nollia ja ykkösiä

561
00:25:34,650 --> 00:25:37,880
että tietokoneen prosessoria, keskeinen
käsittely-yksikön tai aivoissa,

562
00:25:37,880 --> 00:25:39,760
lopulta ymmärtää.

563
00:25:39,760 --> 00:25:42,460
>> On käynyt ilmi, että se on
vähän yksinkertaistamista,

564
00:25:42,460 --> 00:25:44,480
että olemme nyt
kanta kiusanhenki toisistaan

565
00:25:44,480 --> 00:25:46,720
ymmärtää, mitä on todella ollut
meneillään alla huppu

566
00:25:46,720 --> 00:25:48,600
aina käyttää
Sointi, tai yleisemmin,

567
00:25:48,600 --> 00:25:53,040
aina kun teet ohjelmaa,
käyttämällä Tee ja CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
Erityisesti tavaraa kuten
tämä on ensin luotu,

569
00:25:56,760 --> 00:25:58,684
kun ensin kääntää ohjelma.

570
00:25:58,684 --> 00:26:00,600
Toisin sanoen, kun
ota lähdekoodi

571
00:26:00,600 --> 00:26:04,390
ja kääntää se, mikä on ensimmäinen
on ulostulevien kalahtaa

572
00:26:04,390 --> 00:26:06,370
on jotain tunnetaan kokoonpano koodi.

573
00:26:06,370 --> 00:26:08,990
Ja itse asiassa se näyttää täsmälleen samalta kuin tämä.

574
00:26:08,990 --> 00:26:11,170
>> Juoksin komento
komentoriviltä aikaisemmin.

575
00:26:11,170 --> 00:26:16,260
Kalahtaa viiva pääoma s hello.c,
ja tämä loi tiedosto

576
00:26:16,260 --> 00:26:19,490
minulle kutsutaan hello.s,
jonka sisällä olivat täsmälleen

577
00:26:19,490 --> 00:26:22,290
näitä pitoisuuksia, ja hieman enemmän
yläpuolella ja hieman alle,

578
00:26:22,290 --> 00:26:25,080
mutta olen koonnut juiciest
tietoa täältä ruudulla.

579
00:26:25,080 --> 00:26:29,190
Ja jos katsot tarkkaan, näet
ainakin muutamia tuttuja avainsanoja.

580
00:26:29,190 --> 00:26:31,330
Olemme tärkein ylhäällä.

581
00:26:31,330 --> 00:26:35,140
Olemme printf alas keskellä.

582
00:26:35,140 --> 00:26:38,670
Ja meillä on myös Hello World
kenoviiva n lainausmerkkeihin alhaalla.

583
00:26:38,670 --> 00:26:42,450
>> Ja kaikki muu täällä
on hyvin alhainen ohjeet

584
00:26:42,450 --> 00:26:45,500
että tietokoneen prosessoria ymmärtää.

585
00:26:45,500 --> 00:26:50,090
CPU ohjeet, jotka liikkuvat muisti
ympäri, jonka painon jouset muistista,

586
00:26:50,090 --> 00:26:52,750
ja lopulta, tulostaa
asiat näytöltä.

587
00:26:52,750 --> 00:26:56,780
Nyt mitä tapahtuu vaikka jälkeen
tämä kokoonpano koodi luodaan?

588
00:26:56,780 --> 00:26:59,964
Lopulta teet, todellakin,
silti tuottaa kohdekoodilla.

589
00:26:59,964 --> 00:27:02,630
Mutta toimenpiteet, jotka ovat todella
jatkunut alla huppu

590
00:27:02,630 --> 00:27:04,180
näyttää hieman enemmän kuin tämä.

591
00:27:04,180 --> 00:27:08,390
Lähdekoodi tulee kokoonpano koodi,
joka sitten tulee kohdekoodin,

592
00:27:08,390 --> 00:27:11,930
ja operatiiviset sanat tässä on että,
kun käännät lähdekoodin,

593
00:27:11,930 --> 00:27:16,300
ulos tulee kokoonpano koodi, ja sitten
kun Kokoa kokoonpano koodi,

594
00:27:16,300 --> 00:27:17,800
ulos tulee kohdekoodilla.

595
00:27:17,800 --> 00:27:20,360
>> Nyt kalahtaa on erittäin hienostunut,
kuten paljon kerääjiä,

596
00:27:20,360 --> 00:27:23,151
ja se tekee kaikki nämä vaiheet
yhdessä, ja se ei välttämättä

597
00:27:23,151 --> 00:27:25,360
ulostulo välivaiheen
tiedostoja, jotka voit jopa nähdä.

598
00:27:25,360 --> 00:27:28,400
Se vain kokoaa asioita,
joka on yleinen termi, joka

599
00:27:28,400 --> 00:27:30,000
kuvaa tätä koko prosessia.

600
00:27:30,000 --> 00:27:32,000
Mutta jos todella haluat
olla erityisesti siellä

601
00:27:32,000 --> 00:27:34,330
paljon enemmän tekeillä myös siellä.

602
00:27:34,330 --> 00:27:38,860
>> Mutta katsotaanpa myös katsovat nyt, että jopa
että super yksinkertainen ohjelma, hello.c,

603
00:27:38,860 --> 00:27:40,540
kutsutaan toimintoa.

604
00:27:40,540 --> 00:27:41,870
Se kutsutaan printf.

605
00:27:41,870 --> 00:27:46,900
Mutta en kirjoita printf, todellakin,
mukana C, niin sanoakseni.

606
00:27:46,900 --> 00:27:51,139
Se on toiminto muistaa, joka on
ilmoitettu standardin io.h, joka

607
00:27:51,139 --> 00:27:53,180
on header-tiedosto, joka
on aihe me oikeastaan

608
00:27:53,180 --> 00:27:55,780
sukeltaa perusteellisemmin ennen pitkää.

609
00:27:55,780 --> 00:27:58,000
Mutta otsikkotiedosto on
tyypillisesti mukana

610
00:27:58,000 --> 00:28:02,920
koodilla tiedoston, lähdekooditiedostoa, joten
paljon kuin on olemassa standardi io.h.

611
00:28:02,920 --> 00:28:05,930
>> Joskus sitten, joku,
tai jonkun, myös kirjoitti

612
00:28:05,930 --> 00:28:11,040
tiedosto nimeltä standardi io.c, vuonna
jonka todellinen määritelmät,

613
00:28:11,040 --> 00:28:15,220
tai toteutukset printf,
ja rypäleterttuja muita toimintoja,

614
00:28:15,220 --> 00:28:16,870
todella kirjoitettu.

615
00:28:16,870 --> 00:28:22,140
Niin sillä, jos me harkita
täällä vasemmalla, hello.c, että kun

616
00:28:22,140 --> 00:28:26,250
koottu, antaa meille hello.s, vaikka
Kalahtaa ei vaivaudu säästö paikka

617
00:28:26,250 --> 00:28:31,360
voimme nähdä sen, ja että assembly
saa kootaan hello.o, joka

618
00:28:31,360 --> 00:28:34,630
on todellakin oletusnimi
annetaan aina käännät lähde

619
00:28:34,630 --> 00:28:39,350
koodi kohdekoodi, mutta eivät
aivan valmis suorittamaan sitä vielä,

620
00:28:39,350 --> 00:28:41,460
koska toinen vaihe
pitää tapahtua, ja on

621
00:28:41,460 --> 00:28:44,440
on tapahtunut muutaman viime
viikkoa, ehkä tietämättään sinua.

622
00:28:44,440 --> 00:28:47,290
>> Erityisesti jonnekin
vuonna CS50 IDE, ja tämä,

623
00:28:47,290 --> 00:28:49,870
Myös, on vähän
yksinkertaistava hetkeksi,

624
00:28:49,870 --> 00:28:54,670
siellä on, tai oli upon a time,
tiedosto nimeltä standardi io.c,

625
00:28:54,670 --> 00:28:58,440
että joku käännetty
standardi io.s tai vastaava,

626
00:28:58,440 --> 00:29:02,010
että joku sitten koottu
standardiin io.o,

627
00:29:02,010 --> 00:29:04,600
tai se kääntyy ulos
hieman erilainen tiedosto

628
00:29:04,600 --> 00:29:07,220
muodossa, joka voi olla erilainen
tiedostopääte kokonaan,

629
00:29:07,220 --> 00:29:11,720
mutta teoriassa ja käsitteellisesti, täsmälleen
nämä toimenpiteet täytyi tapahtua jossain muodossa.

630
00:29:11,720 --> 00:29:14,060
Joka on sanoa, että nyt
kun olen kirjallisesti ohjelma,

631
00:29:14,060 --> 00:29:17,870
hello.c, että vain sanoo, Hello World,
ja olen käyttäen jonkun toisen koodi

632
00:29:17,870 --> 00:29:22,480
kuten printf, joka oli aikoinaan päällä
aika, tiedostossa nimeltä standardi io.c,

633
00:29:22,480 --> 00:29:26,390
sitten jotenkin minun on otettava minun
kohdekoodi, minun nollia ja ykkösiä,

634
00:29:26,390 --> 00:29:29,260
ja että henkilön esine
koodi tai nollia ja ykkösiä,

635
00:29:29,260 --> 00:29:34,970
ja jotenkin yhdistää ne
yksi lopullinen tiedosto, nimeltään Hei, että

636
00:29:34,970 --> 00:29:38,070
on kaikki nollia ja
niistä minun päätehtävä,

637
00:29:38,070 --> 00:29:40,830
ja kaikki nollia
ja ne, printf.

638
00:29:40,830 --> 00:29:44,900
>> Ja todellakin, että viime prosessi on
nimeltään, liität kohdekoodilla.

639
00:29:44,900 --> 00:29:47,490
Jonka lähtö
on suoritettava tiedosto.

640
00:29:47,490 --> 00:29:49,780
Joten tasapuolisuuden on
päivän päätteeksi, ei mitään

641
00:29:49,780 --> 00:29:52,660
on muuttunut viikolla yksi, kun
aloitti kokoamiseen ohjelmia.

642
00:29:52,660 --> 00:29:55,200
Itse asiassa tämä kaikki on ollut
tapahtuu alla huppu,

643
00:29:55,200 --> 00:29:57,241
mutta nyt olemme asemassa
jossa voimme todella

644
00:29:57,241 --> 00:29:58,794
tease lisäksi nämä eri vaiheet.

645
00:29:58,794 --> 00:30:00,710
Ja itse asiassa lopussa
päivä, olemme yhä

646
00:30:00,710 --> 00:30:04,480
jää nollia ja ykkösiä, joka
on todella suuri segue nyt

647
00:30:04,480 --> 00:30:08,620
Toinen ominaisuus C, että
olemme ole tarvinnut hyödyntää todennäköisesti

648
00:30:08,620 --> 00:30:11,250
Tähän mennessä tunnetaan bittioperaatioiden.

649
00:30:11,250 --> 00:30:15,220
Toisin sanoen, toistaiseksi, milloin olemme
Puhuttiin tietojen C tai muuttujiin C,

650
00:30:15,220 --> 00:30:17,660
meillä on ollut asioita, kuten
merkkiä ja kellukkeet ja laajennukset

651
00:30:17,660 --> 00:30:21,990
ja pitkät ja kaksinkertaistuu ja vastaavat, mutta
kaikki nämä ovat vähintään kahdeksan bittiä.

652
00:30:21,990 --> 00:30:25,550
Emme ole koskaan vielä ole voinut
manipuloida yksittäisiä bittejä,

653
00:30:25,550 --> 00:30:28,970
vaikka yksittäisen vähän, me
tietää, voi edustaa 0 ja 1.

654
00:30:28,970 --> 00:30:32,640
Nyt näyttää siltä, ​​että C, sinua
voi päästä käsiksi yksittäisiä bittejä,

655
00:30:32,640 --> 00:30:35,530
jos tiedät syntaksin,
jolla saada niitä.

656
00:30:35,530 --> 00:30:38,010
>> Joten katsomaan
klo bittioperaatioiden.

657
00:30:38,010 --> 00:30:41,700
Joten Kuvassa on muutamia symboleja,
olemme, tavallaan, tavallaan, ennen nähty.

658
00:30:41,700 --> 00:30:45,580
Näen et-merkki, pystysuora
baari, ja jotkut muut samoin,

659
00:30:45,580 --> 00:30:49,430
ja muistuttavat, että et-merkki et-merkki
on jotain olemme nähneet aiemmin.

660
00:30:49,430 --> 00:30:54,060
Looginen AND-operaattori, jossa sinulla on
kaksi niistä yhdessä tai looginen TAI

661
00:30:54,060 --> 00:30:56,300
operaattori, jossa
on kaksi pystypalkkia.

662
00:30:56,300 --> 00:31:00,550
Bittioperaatioiden, joka käymme
katso toimivat bittiä erikseen,

663
00:31:00,550 --> 00:31:03,810
vain käyttää yksi et-merkki,
yksi pystysuora palkki, sirkumfleksi symboli

664
00:31:03,810 --> 00:31:06,620
tulee seuraavaksi, pieni
tilde, ja sitten vasemmalle

665
00:31:06,620 --> 00:31:08,990
kannatin vasen kannatin, tai
oikea kannatin oikea kiinnike.

666
00:31:08,990 --> 00:31:10,770
Kukin näistä on eri merkitykset.

667
00:31:10,770 --> 00:31:11,950
>> Itse asiassa, nyt katsomaan.

668
00:31:11,950 --> 00:31:16,560
Mennään vanhan koulun tänään, ja käyttö
kosketusnäyttö menneiden,

669
00:31:16,560 --> 00:31:18,002
tunnetaan valkoinen levy.

670
00:31:18,002 --> 00:31:19,710
Ja tämä valkoinen lauta
aikoo antaa meille

671
00:31:19,710 --> 00:31:27,360
ilmaista joitakin melko yksinkertaisia ​​symboleita,
tai pikemminkin joitakin melko yksinkertaisia ​​kaavoja,

672
00:31:27,360 --> 00:31:29,560
että voimme lopulta
vipuvaikutus, jotta

673
00:31:29,560 --> 00:31:33,230
pääsyn yksittäisiä
bittiä C-ohjelma.

674
00:31:33,230 --> 00:31:34,480
Toisin sanoen, tehdään tämä.

675
00:31:34,480 --> 00:31:37,080
Katsotaanpa ensin puhua varten
hetki et-merkki,

676
00:31:37,080 --> 00:31:39,560
joka on peiton ja Operaattori.

677
00:31:39,560 --> 00:31:42,130
Toisin sanoen, tämä on
operaattori, jonka avulla

678
00:31:42,130 --> 00:31:45,930
minulle on vasen muuttuja
tyypillisesti, ja oikea muuttuja,

679
00:31:45,930 --> 00:31:50,640
tai yksittäinen arvo, että jos me ja
ne yhteen, antaa minulle lopputulokseen.

680
00:31:50,640 --> 00:31:51,560
Joten mitä minä tarkoitan?

681
00:31:51,560 --> 00:31:54,840
Jos ohjelma, sinulla on muuttuva
että tallentaa yhden näistä arvoista,

682
00:31:54,840 --> 00:31:58,000
tai katsotaanpa pitää asiat yksinkertaisina, ja vain
kirjoittaa nollia ja ykkösiä erikseen,

683
00:31:58,000 --> 00:32:00,940
tässä miten -merkki operaattori toimii.

684
00:32:00,940 --> 00:32:06,400
0 Ampersand 0 tulee yhtä 0.

685
00:32:06,400 --> 00:32:07,210
Nyt Miksi?

686
00:32:07,210 --> 00:32:09,291
>> Se on hyvin samankaltainen
Boolen operaattoreilla,

687
00:32:09,291 --> 00:32:10,540
että olemme keskustelleet tähän asti.

688
00:32:10,540 --> 00:32:15,800
Jos luulet onhan 0 on
väärä, 0 on väärä, väärä ja vääriä

689
00:32:15,800 --> 00:32:18,720
on, kuten olemme keskustelleet
loogisesti, myös väärä.

690
00:32:18,720 --> 00:32:20,270
Jotta saamme 0 myös täällä.

691
00:32:20,270 --> 00:32:24,390
Jos otat 0 ampersand
1, hyvin, että myös

692
00:32:24,390 --> 00:32:29,890
tulee olemaan 0, koska tämä
vasen ilmaisun olevan totta tai 1,

693
00:32:29,890 --> 00:32:32,360
sen pitäisi olla totta ja totta.

694
00:32:32,360 --> 00:32:36,320
Mutta tässä meillä on väärä
ja totta, tai 0 ja 1.

695
00:32:36,320 --> 00:32:42,000
Nyt uudelleen, jos meillä on 1 ampersand
0, sekin tulee olemaan 0,

696
00:32:42,000 --> 00:32:47,240
ja jos meillä on 1 et-merkki 1,
Lopuksi meillä on 1 bit.

697
00:32:47,240 --> 00:32:50,340
Eli toisin sanoen, me emme tee
mitään mielenkiintoista tämän operaattorin

698
00:32:50,340 --> 00:32:51,850
vain vielä, tämä Ampersand operaattori.

699
00:32:51,850 --> 00:32:53,780
Se peiton ja Operaattori.

700
00:32:53,780 --> 00:32:57,290
Mutta nämä ovat ainekset
jonka kautta voimme tehdä

701
00:32:57,290 --> 00:32:59,240
mielenkiintoisia asioita, kuten tulemme pian nähdä.

702
00:32:59,240 --> 00:33:02,790
>> Nyt katsokaamme vain yhden
pystyviiva tänne oikealla.

703
00:33:02,790 --> 00:33:06,710
Jos minulla on 0 vähän ja minä
TAI se, bittivastineen

704
00:33:06,710 --> 00:33:11,030
OR operaattori, toinen 0 bit,
joka tulee antamaan minulle 0.

705
00:33:11,030 --> 00:33:17,540
Jos otan 0 vähän ja OR sen
1 vähän, niin aion saada 1.

706
00:33:17,540 --> 00:33:19,830
Ja itse asiassa, vain
selkeys, anna minun mennä takaisin,

707
00:33:19,830 --> 00:33:23,380
niin että minun pystypalkki
ei erehtynyt 1: n.

708
00:33:23,380 --> 00:33:26,560
Saanen uusia koko
minun 1 on hieman enemmän

709
00:33:26,560 --> 00:33:32,700
selvästi, jotta voimme ensi nähdä, jos en
on 1 tai 0, joka tulee olemaan 1,

710
00:33:32,700 --> 00:33:39,060
ja jos minulla on 1 tai 1 että,
Myös tulee olemaan 1.

711
00:33:39,060 --> 00:33:42,900
Voit siis nähdä loogisesti että TAI
operaattori käyttäytyy hyvin eri tavalla.

712
00:33:42,900 --> 00:33:48,070
Tämä antaa minulle 0 tai 0 antaa minulle 0, mutta
joka toinen yhdistelmä antaa minulle 1.

713
00:33:48,070 --> 00:33:52,480
Niin kauan kuin minulla on yksi 1
kaava, tulos tulee olemaan 1.

714
00:33:52,480 --> 00:33:55,580
>> Toisin JA
operaattori, et-merkki,

715
00:33:55,580 --> 00:34:00,940
vain jos minulla on kaksi 1: n
yhtälö, voin itse saada 1 ulos.

716
00:34:00,940 --> 00:34:02,850
Nyt on olemassa muutamia muita
toimijat samoin.

717
00:34:02,850 --> 00:34:04,810
Yksi niistä on hieman enemmän mukana.

718
00:34:04,810 --> 00:34:07,980
Joten anna minun mennä eteenpäin ja poistaa
tämä vapauttaa levytilaa.

719
00:34:07,980 --> 00:34:13,020

720
00:34:13,020 --> 00:34:16,460
Ja lähdetään katsomaan
caret symboli, vain hetken.

721
00:34:16,460 --> 00:34:18,210
Tämä on tyypillisesti
merkki voit kirjoittaa

722
00:34:18,210 --> 00:34:21,420
näppäimistön SHIFT ja
sitten yksi numerot huipulla oman US

723
00:34:21,420 --> 00:34:22,250
näppäimistö.

724
00:34:22,250 --> 00:34:26,190
>> Joten tämä on yksinomainen
OR operaattori, eksklusiivinen TAI.

725
00:34:26,190 --> 00:34:27,790
Joten me vain näimme tai toiminnanharjoittaja.

726
00:34:27,790 --> 00:34:29,348
Tämä on eksklusiivinen OR operaattori.

727
00:34:29,348 --> 00:34:30,639
Mitä oikeastaan ​​eroa?

728
00:34:30,639 --> 00:34:34,570
No katsotaanpa katsokaa kaava,
ja käyttää tätä ainesosina lopulta.

729
00:34:34,570 --> 00:34:37,690
0 XOR 0.

730
00:34:37,690 --> 00:34:39,650
Aion sanoa on aina 0.

731
00:34:39,650 --> 00:34:41,400
Se määritelmä XOR.

732
00:34:41,400 --> 00:34:47,104
0 XOR 1 tulee olemaan 1.

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 tulee olemaan 1,
ja 1 XOR 1 tulee olemaan?

734
00:34:58,810 --> 00:34:59,890
Väärässä?

735
00:34:59,890 --> 00:35:00,520
Tai oikea?

736
00:35:00,520 --> 00:35:01,860
Minä en tiedä.

737
00:35:01,860 --> 00:35:02,810
0.

738
00:35:02,810 --> 00:35:04,700
Nyt mitä on tekeillä?

739
00:35:04,700 --> 00:35:06,630
No ajattele
Nimi tämän operaattorin.

740
00:35:06,630 --> 00:35:09,980
Eksklusiivinen OR, jotta
nimi, ehdottaa,

741
00:35:09,980 --> 00:35:13,940
vastaus on vain olemaan
1 jos tulot ovat yksin,

742
00:35:13,940 --> 00:35:15,560
yksinomaan eri.

743
00:35:15,560 --> 00:35:18,170
Joten tässä tulot ovat
sama, joten tuotos on 0.

744
00:35:18,170 --> 00:35:20,700
Tässä tulot ovat
sama, joten tuotos on 0.

745
00:35:20,700 --> 00:35:25,640
Tässä ovat lähdöt ovat erilaisia, ne
ovat yksin, ja niin lähtö on 1.

746
00:35:25,640 --> 00:35:28,190
Joten se on hyvin samankaltainen
Ja se on hyvin samankaltainen,

747
00:35:28,190 --> 00:35:32,760
tai pikemminkin se on hyvin samankaltainen
TAI, mutta vain yksinomainen tavalla.

748
00:35:32,760 --> 00:35:36,210
Tämä ei ole enää 1,
koska meillä on kaksi 1 n,

749
00:35:36,210 --> 00:35:38,621
ja ei yksinomaan, vain yksi niistä.

750
00:35:38,621 --> 00:35:39,120
Selvä.

751
00:35:39,120 --> 00:35:40,080
Entä muut?

752
00:35:40,080 --> 00:35:44,220
No tilde puolestaan ​​on
todella mukava ja yksinkertainen, onneksi.

753
00:35:44,220 --> 00:35:46,410
Ja tämä on unary
operaattorin, joka tarkoittaa

754
00:35:46,410 --> 00:35:50,400
se on sovellettu ainoastaan ​​yhteen tulo,
yksi operandi, niin sanoakseni.

755
00:35:50,400 --> 00:35:51,800
Ei vasemmalle ja oikealle.

756
00:35:51,800 --> 00:35:56,050
Toisin sanoen, jos otat tilde of
0, vastaus on päinvastainen.

757
00:35:56,050 --> 00:35:59,710
Ja jos otat tilde 1,
vastaus tulee olemaan päinvastainen.

758
00:35:59,710 --> 00:36:02,570
Joten tilde operaattori on
tapa tyhjäksi hieman,

759
00:36:02,570 --> 00:36:06,000
tai käännetään verran
0-1 tai 1-0.

760
00:36:06,000 --> 00:36:09,820
>> Ja että jättää meidät vihdoin
vain kaksi viimeistä toimijoiden,

761
00:36:09,820 --> 00:36:13,840
ns vasemmalla muutos, ja
ns oikealla shift operaattori.

762
00:36:13,840 --> 00:36:16,620
Katsotaanpa katsomaan miten nämä työssä.

763
00:36:16,620 --> 00:36:20,780
Vasemmalle siirtyminen operaattori, kirjallinen
kaksi kulmakiinnikkeet niin,

764
00:36:20,780 --> 00:36:22,110
toimii seuraavasti.

765
00:36:22,110 --> 00:36:27,390
Jos minun panos, tai minun operandi, vasemmalle
shift operaattori on yksinkertaisesti 1.

766
00:36:27,390 --> 00:36:33,750
Ja minä sitten kertoa tietokoneen
vasen shift että 1, sanovat seitsemän paikkoja,

767
00:36:33,750 --> 00:36:37,150
tulos on kuin olisin
ottaa tämän 1, ja siirrä se

768
00:36:37,150 --> 00:36:40,160
seitsemän paikkoja yli
vasemmalle, ja oletuksena,

769
00:36:40,160 --> 00:36:42,270
aiomme olettaa, että
tilaa oikealle

770
00:36:42,270 --> 00:36:44,080
aiotaan nollilla.

771
00:36:44,080 --> 00:36:50,316
Toisin sanoen, 1 vasen muutos 7 on menossa
antaa minulle, että 1, jonka jälkeen 1, 2, 3,

772
00:36:50,316 --> 00:36:54,060
4, 5, 6, 7 nollia.

773
00:36:54,060 --> 00:36:57,380
Joten tavallaan, sen avulla voit
ottaa pieni määrä kuten 1,

774
00:36:57,380 --> 00:37:00,740
ja selvästi on paljon
paljon, paljon suurempi tällä tavalla,

775
00:37:00,740 --> 00:37:06,460
mutta me todella tulee nähdä
viisaampi lähestymistapoja se

776
00:37:06,460 --> 00:37:08,080
sen sijaan, samoin,

777
00:37:08,080 --> 00:37:08,720
>> Selvä.

778
00:37:08,720 --> 00:37:10,060
Se on siinä viikolla kolme.

779
00:37:10,060 --> 00:37:11,400
Tulemme näkemään ensi kerralla.

780
00:37:11,400 --> 00:37:12,770
Tämä oli CS50.

781
00:37:12,770 --> 00:37:17,270

782
00:37:17,270 --> 00:37:22,243
>> [Musiikkia]

783
00:37:22,243 --> 00:37:25,766
>> SPEAKER 1: Hän oli välipala
baari syöminen kuuma tuhertaa jäätelöannos.

784
00:37:25,766 --> 00:37:28,090
Hänellä oli se koko hänen kasvonsa.

785
00:37:28,090 --> 00:37:30,506
Hän on päällään, että suklaa kuten parta

786
00:37:30,506 --> 00:37:31,756
SPEAKER 2: Mitä sinä teet?

787
00:37:31,756 --> 00:37:32,422
SPEAKER 3: Hmmm?

788
00:37:32,422 --> 00:37:33,500
Mitä?

789
00:37:33,500 --> 00:37:36,800
>> SPEAKER 2: Oletko juuri double dip?

790
00:37:36,800 --> 00:37:38,585
Voit kaksinkertainen kastetaan siru.

791
00:37:38,585 --> 00:37:39,460
SPEAKER 3: Anteeksi.

792
00:37:39,460 --> 00:37:44,440
SPEAKER 2: Sinä kastettu siru, sinä
otti purra, ja te kastetaan uudelleen.

793
00:37:44,440 --> 00:37:44,940
SPEAKER 3:

794
00:37:44,940 --> 00:37:48,440
SPEAKER 2: Niin, että kuin laittaisi
koko suu aivan dip.

795
00:37:48,440 --> 00:37:52,400
Seuraavan kerran otat siru,
vain kasta se kerran, ja lopettaa sen.

796
00:37:52,400 --> 00:37:53,890
>> SPEAKER 3: Tiedätkö mitä, Dan?

797
00:37:53,890 --> 00:37:58,006
Voit pulahtaa tavalla haluat pulahtaa.

798
00:37:58,006 --> 00:38:01,900
Minä dip tapa, että haluan notkahdus.

799
00:38:01,900 --> 00:38:03,194