1
00:00:00,000 --> 00:00:11,904
>> [Muusika mängib]

2
00:00:11,904 --> 00:00:12,910
>> PROFESSOR: Okei.

3
00:00:12,910 --> 00:00:16,730
See on CS50 ja see on
nädala lõpuks kolm.

4
00:00:16,730 --> 00:00:20,230
Nii et me oleme täna siin, mitte Sanders
Teater, selle asemel Weidner raamatukogu.

5
00:00:20,230 --> 00:00:23,170
Mille sees on stuudio
tuntakse Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
või ütleme Studio H, või esitab
me say-- Kui teile meeldis see nali,

7
00:00:28,310 --> 00:00:30,540
see on tegelikult pärit
klassivend, Mark, online,

8
00:00:30,540 --> 00:00:32,420
kes soovitas nii palju kaudu Twitter.

9
00:00:32,420 --> 00:00:34,270
Nüüd sellest, mis on lahe umbes
on siin stuudios

10
00:00:34,270 --> 00:00:38,410
on, et ma olen ümbritsetud need rohelised
seinad, roheline ekraan või chromakey,

11
00:00:38,410 --> 00:00:43,290
niiöelda, mis tähendab, et CS50 on
tootmise meeskond, teadmata mind

12
00:00:43,290 --> 00:00:47,380
just nüüd, võiks panna
mulle kõige kõikjal maailmas,

13
00:00:47,380 --> 00:00:48,660
paremaks või halvemaks.

14
00:00:48,660 --> 00:00:51,800
>> Nüüd, mis ees ootab, probleem seatud
kaks on teie kätes sel nädalal,

15
00:00:51,800 --> 00:00:53,830
kuid probleem seatud
kolm tuleval nädalal

16
00:00:53,830 --> 00:00:56,600
siis tuleb väljakutse koos
nn mängu 15

17
00:00:56,600 --> 00:00:58,960
vana poole kasuks, et
sa võiks meenutada, saavad

18
00:00:58,960 --> 00:01:02,030
nagu laps, et on terve hunnik
Numbrite mida saab libistada üles, alla,

19
00:01:02,030 --> 00:01:05,790
vasakule ja paremale, ja seal on üks lõhe
jooksul puzzle, millesse tõlgitakse

20
00:01:05,790 --> 00:01:07,840
võib tegelikult lükake need puzzle tükid.

21
00:01:07,840 --> 00:01:11,150
Lõppkokkuvõttes saate seda
puzzle mõnel pool juhuslikus järjekorras,

22
00:01:11,150 --> 00:01:12,940
ja eesmärgiks on
sortida, ülevalt alla,

23
00:01:12,940 --> 00:01:16,310
vasakult paremale, ühest
kõik teed üles läbi 15.

24
00:01:16,310 --> 00:01:19,360
>> Kahjuks rakendamist
sul on käepärast

25
00:01:19,360 --> 00:01:21,590
läheb tarkvara
põhineb mitte füüsiliselt.

26
00:01:21,590 --> 00:01:25,280
Sa oled tegelikult läheb on kirjutada
kood, mis üliõpilane või saab kasutaja

27
00:01:25,280 --> 00:01:26,760
mängu mängida 15.

28
00:01:26,760 --> 00:01:29,030
Ja tegelikult häkker
väljaanne mängu 15

29
00:01:29,030 --> 00:01:32,155
Teil on väljakutse rakendada,
mitte ainult mängides seda vana kooli

30
00:01:32,155 --> 00:01:35,010
mängu, vaid lahendamine
sellest, rakendades jumal režiimis

31
00:01:35,010 --> 00:01:38,280
niiöelda, et tegelikult
lahendab puzzle inimese,

32
00:01:38,280 --> 00:01:41,080
pakkudes neile vihje,
pärast vihje peale vihje.

33
00:01:41,080 --> 00:01:42,280
Nii rohkem, et järgmisel nädalal.

34
00:01:42,280 --> 00:01:43,720
Aga see, mis ees ootab.

35
00:01:43,720 --> 00:01:47,610
>> Praegu meenutavad, et varem sel nädalal
meil oli see pinge, kui soovite,

36
00:01:47,610 --> 00:01:52,560
kusjuures parim, mida me teeme sorteerimine
tark oli ülemine piir suur o n

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

38
00:01:53,210 --> 00:01:56,520
Teisisõnu, mull sorteerida,
valikut sorteerida, sisestamise sorteerida,

39
00:01:56,520 --> 00:01:59,120
Kõigi nende kui erinevad
nende rakendamisel,

40
00:01:59,120 --> 00:02:03,480
detsentraliseeritud arvesse n ruudus töötab
aega väga halvimat.

41
00:02:03,480 --> 00:02:06,010
Ja me üldiselt eeldada, et
väga halvimal juhul sorteerimine

42
00:02:06,010 --> 00:02:08,814
on selline, et oma sisendid
on täiesti tagurpidi.

43
00:02:08,814 --> 00:02:11,980
Ja tõepoolest, see võttis üsna vähe samme
rakendada kõigis neis algoritme.

44
00:02:11,980 --> 00:02:15,110
>> Nüüd päris lõpus klassi
Meenuta, me võrreldes mull omamoodi

45
00:02:15,110 --> 00:02:19,390
valikukriteeriumide omamoodi vastu üks teine
et me kutsusime ühendamine omamoodi ajal,

46
00:02:19,390 --> 00:02:22,120
ja ma teen ettepaneku, et see võtab
ära õppetund nädalas

47
00:02:22,120 --> 00:02:24,060
null, jaga ja valitse.

48
00:02:24,060 --> 00:02:28,810
Ja kuidagi saavutada mingi
logaritmiline sõiduaega lõpuks

49
00:02:28,810 --> 00:02:31,024
selle asemel, et midagi
see on puhtalt ruutu.

50
00:02:31,024 --> 00:02:33,440
Ja see ei ole päris logaritmiline
see on natuke rohkem.

51
00:02:33,440 --> 00:02:36,520
Aga kui te mäletate klassi,
see oli palju, palju kiiremini.

52
00:02:36,520 --> 00:02:38,210
Võtame pilk, kus pooleli jäime.

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

54
00:02:41,880 --> 00:02:45,370
>> Bubble omamoodi versus valikut
Sorteeri versus ühendamine omamoodi.

55
00:02:45,370 --> 00:02:47,700
Nüüd on nad kõik töötavad, on
Teoreetiliselt samaaegselt.

56
00:02:47,700 --> 00:02:50,510
Protsessor töötab sama kiirusega.

57
00:02:50,510 --> 00:02:54,990
Aga sa võid tunda, kuidas igav see
on väga kiiresti hakkab muutuma,

58
00:02:54,990 --> 00:02:58,790
ja lihtsalt, kui kiiresti, kui me süstida
natuke nädalal null algoritmid,

59
00:02:58,790 --> 00:03:00,080
saame asju kiirendada.

60
00:03:00,080 --> 00:03:01,630
>> Nii mark omamoodi näeb välja hämmastav.

61
00:03:01,630 --> 00:03:05,220
Kuidas me saame võimendada seda, et
sorteeri numbrid kiiremini.

62
00:03:05,220 --> 00:03:07,140
Noh olgem mõelda tagasi
koostisosale et me

63
00:03:07,140 --> 00:03:10,380
oli juba nädal null, mis
otsides keegi telefoniraamatust,

64
00:03:10,380 --> 00:03:12,380
ja meelde tuletama, et
pseudokoodi et tegime ettepaneku,

65
00:03:12,380 --> 00:03:14,560
mille kaudu saame teada
keegi nagu Mike Smith,

66
00:03:14,560 --> 00:03:16,310
Vaatasin natuke midagi sellist.

67
00:03:16,310 --> 00:03:20,820
>> Nüüd vaatleme eriti
real 7 ja 8, ning 10 ja 11,

68
00:03:20,820 --> 00:03:25,240
mis tekitavad selle kontuuri, millega me hoida
naasmine line 3 uuesti ja uuesti,

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

70
00:03:26,520 --> 00:03:31,790
Selgub aga, et meil on võimalik vaadata
See algoritm, siin pseudokoodi,

71
00:03:31,790 --> 00:03:33,620
natuke rohkem terviklikult.

72
00:03:33,620 --> 00:03:35,960
Tegelikult, mida ma otsin
kell siin ekraanil,

73
00:03:35,960 --> 00:03:41,180
on algoritm otsimiseks
Mike Smith hulgast mõned lehekülgede hulk.

74
00:03:41,180 --> 00:03:45,520
Ja tõepoolest, me võiks seda lihtsustada
algoritmi need read 7 ja 8,

75
00:03:45,520 --> 00:03:49,860
10 ja 11 lihtsalt öelda seda,
mis ma olen siin esitatud kollane.

76
00:03:49,860 --> 00:03:52,210
Teisisõnu, kui Mike
Smith on varem broneerida,

77
00:03:52,210 --> 00:03:55,004
Me ei vaja täpsustada sammu
sammult nüüd, kuidas edasi minna teda leida.

78
00:03:55,004 --> 00:03:56,920
Me ei pea täpsustada
minna tagasi line 3,

79
00:03:56,920 --> 00:03:58,960
Miks me ei lihtsalt selle asemel,
ütleme üldisemalt

80
00:03:58,960 --> 00:04:01,500
otsida Mike on
Vasakul pool raamatut.

81
00:04:01,500 --> 00:04:03,960
>> Vastupidisel juhul, kui Mike on
tegelikult hiljem raamatus,

82
00:04:03,960 --> 00:04:07,540
miks me lihtsalt ei tsiteerida lõppeb otsing
Mike õiges poole raamatu.

83
00:04:07,540 --> 00:04:11,030
Teisisõnu, miks me lihtsalt ei
omamoodi punt endale öelda,

84
00:04:11,030 --> 00:04:13,130
otsida Mike selles
alagrupis raamat

85
00:04:13,130 --> 00:04:16,279
ja jätke meie olemasolevate
algoritmi ütle meile

86
00:04:16,279 --> 00:04:18,750
kuidas otsida Mike
et vasakul pool raamatut.

87
00:04:18,750 --> 00:04:20,750
Teisisõnu, meie
algoritm töötab, kas see on

88
00:04:20,750 --> 00:04:24,670
telefoniraamat selle paksus, selle
paksus, või mis tahes paksusega üldse.

89
00:04:24,670 --> 00:04:27,826
Nii saame rekursiivselt
määratleda selle algoritmi.

90
00:04:27,826 --> 00:04:29,950
Teisisõnu, Euroopa
ekraan siin on algoritm

91
00:04:29,950 --> 00:04:33,130
otsimiseks Mike Smith
hulgast lehekülge telefoniraamat.

92
00:04:33,130 --> 00:04:37,410
Nii line 7 ja 10, olgem
lihtsalt öelda, just nii.

93
00:04:37,410 --> 00:04:40,250
Ja ma kasutan seda mõistet hetkeks
tagasi, ja tõepoolest, recursion

94
00:04:40,250 --> 00:04:42,450
on sõnakõlks nüüd,
ja see on selle protsessi

95
00:04:42,450 --> 00:04:47,210
teha midagi tsükliline kuidagi
kasutades kood, mis sul on juba,

96
00:04:47,210 --> 00:04:49,722
ja nimetades seda uuesti,
ja uuesti ja uuesti.

97
00:04:49,722 --> 00:04:51,930
Nüüd saab olema oluline
et me kuidagi alt

98
00:04:51,930 --> 00:04:53,821
välja, ja ei tee seda lõputult kaua.

99
00:04:53,821 --> 00:04:56,070
Muidu me ei kavatse
on tõesti lõputu silmuse.

100
00:04:56,070 --> 00:04:59,810
Aga vaatame, kas me saame seda laenata idee
on recursion, midagi jälle

101
00:04:59,810 --> 00:05:03,600
ja ikka ja jälle, et lahendada
sorteerimise probleem kaudu ühendada

102
00:05:03,600 --> 00:05:05,900
sorteerida kõiki tõhusamalt.

103
00:05:05,900 --> 00:05:06,970
>> Nii et ma annan sulle liita omamoodi.

104
00:05:06,970 --> 00:05:07,920
Võtame pilk.

105
00:05:07,920 --> 00:05:10,850
Nii et siin on pseudokoodi koos
mida me võiksime rakendada sorteerimise,

106
00:05:10,850 --> 00:05:12,640
kasutades seda algoritmi nimetatakse ühendamine omamoodi.

107
00:05:12,640 --> 00:05:13,880
Ja see on lihtsalt see.

108
00:05:13,880 --> 00:05:15,940
On sisend n elementi,
Teisisõnu, kui sa oled

109
00:05:15,940 --> 00:05:18,830
antud n elementi ja numbrite
tähed või mis iganes sisend on,

110
00:05:18,830 --> 00:05:22,430
kui sa oled andnud n elementi, kui
n on alla 2, lihtsalt tagasi.

111
00:05:22,430 --> 00:05:22,930
Õigus?

112
00:05:22,930 --> 00:05:26,430
Sest kui n on alla 2, et
tähendab, et minu elementide nimekirja

113
00:05:26,430 --> 00:05:30,446
on kumbki suurusega 0 või 1 ja
nii nende triviaalne juhtudel,

114
00:05:30,446 --> 00:05:31,570
nimekiri on juba järjestatud.

115
00:05:31,570 --> 00:05:32,810
Kui ei ole nimekirjas, siis on järjestatud.

116
00:05:32,810 --> 00:05:35,185
Ja kui seal on nimekiri pikkus
1, siis on ilmselt järjestatud.

117
00:05:35,185 --> 00:05:38,280
Nii algoritm vajab ainult
tõesti midagi huvitavat,

118
00:05:38,280 --> 00:05:40,870
kui meil on kaks või enam
elemendid meile antud.

119
00:05:40,870 --> 00:05:42,440
Nii saab vaadata magic siis.

120
00:05:42,440 --> 00:05:47,500
Else sorteerida vasakul poolel elemendid,
siis sorteerida õige pool elemente,

121
00:05:47,500 --> 00:05:49,640
Seejärel ühendada järjestatud pooleks.

122
00:05:49,640 --> 00:05:52,440
Ja mis on omamoodi meeles painutamine
siin on see, et ma tõesti ei

123
00:05:52,440 --> 00:05:56,190
tundub, et on teile rääkinud
midagi lihtsalt veel, eks?

124
00:05:56,190 --> 00:05:59,560
Kõik, mida ma olen öelnud on, antud nimekiri
n elementi, sorteerida vasakul pool,

125
00:05:59,560 --> 00:06:01,800
siis paremal pool, siis
ühendada järjestatud pooleks,

126
00:06:01,800 --> 00:06:03,840
aga kus on tegelik saladus kaste?

127
00:06:03,840 --> 00:06:05,260
Kus on algoritm?

128
00:06:05,260 --> 00:06:09,150
Noh selgub, et need kaks rida
Esimene, omamoodi vasakule poole elemente,

129
00:06:09,150 --> 00:06:13,970
ja omamoodi õigus pooled elemendid,
on rekursiivne kõned, kui nii võib öelda.

130
00:06:13,970 --> 00:06:16,120
>> Lõppude lõpuks on see
ajahetkel, ma pean

131
00:06:16,120 --> 00:06:18,950
algoritmi, mille abil saaks
sorteeri terve hulk elemente?

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

133
00:06:19,450 --> 00:06:20,620
See on siinsamas.

134
00:06:20,620 --> 00:06:25,180
See on siinsamas ekraanil, ja
nii et ma ei kasuta, et samad sammud

135
00:06:25,180 --> 00:06:28,500
sorteeri vasakul pool,
kui saan õige poole.

136
00:06:28,500 --> 00:06:30,420
Ja tõepoolest, uuesti ja uuesti.

137
00:06:30,420 --> 00:06:34,210
Nii ühel või teisel moel, ja me varsti
vaata seda, maagia ühendamine omamoodi

138
00:06:34,210 --> 00:06:37,967
on põimitud väga lõplik
line, ühendades sorteeritud pooleks.

139
00:06:37,967 --> 00:06:39,300
Ja see tundub üsna intuitiivne.

140
00:06:39,300 --> 00:06:41,050
Võtad kaks poolt, ja sa,
kuidagi, liita need kokku,

141
00:06:41,050 --> 00:06:43,260
ja me näeme seda
konkreetselt ühe hetkega.

142
00:06:43,260 --> 00:06:45,080
>> Kuid see on täielik algoritm.

143
00:06:45,080 --> 00:06:46,640
Vaatame, miks.

144
00:06:46,640 --> 00:06:50,912
Noh oletame, et me antud needsamad
Kaheksa tegurid, ekraanil üks

145
00:06:50,912 --> 00:06:53,120
läbi kaheksa, kuid nad
näiliselt juhuslikus järjekorras.

146
00:06:53,120 --> 00:06:55,320
Ja eesmärk käepärast on
sorteeri need elemendid.

147
00:06:55,320 --> 00:06:58,280
Noh, kuidas ma saan minna
tee seda kasutades jällegi

148
00:06:58,280 --> 00:07:00,407
liita omamoodi, vastavalt sellele pseudokoodi?

149
00:07:00,407 --> 00:07:02,740
Ja jälle, sünnipärane seda
meelt, et üks hetk.

150
00:07:02,740 --> 00:07:05,270
Esimesel juhul on päris
triviaalne, kui see on väiksem kui 2,

151
00:07:05,270 --> 00:07:07,060
lihtsalt tagasi, ei ole tööd teha.

152
00:07:07,060 --> 00:07:09,290
Nii et tõesti seal on vaid kolm
samme tõesti meeles pidada.

153
00:07:09,290 --> 00:07:11,081
Taas ja jälle, ma olen
läheb tahtnud

154
00:07:11,081 --> 00:07:13,980
sorteeri vasakul pool,
sorteeri paremal pool,

155
00:07:13,980 --> 00:07:15,890
ja siis, kui nende
kaheks pooleks on järjestatud,

156
00:07:15,890 --> 00:07:18,710
Ma tahan, et liita need kokku
üheks sorteeritud nimekirja.

157
00:07:18,710 --> 00:07:19,940
Nii et hoidke seda silmas pidades.

158
00:07:19,940 --> 00:07:21,310
>> Nii et siin on originaal nimekirja.

159
00:07:21,310 --> 00:07:23,510
Olgem käsitleda seda kui
massiiv, kui hakkasime

160
00:07:23,510 --> 00:07:25,800
nädalal kaks, mis on
külgnevas ploki mälu.

161
00:07:25,800 --> 00:07:28,480
Sel juhul sisaldavad kaheksa
numbrid, seljad tagasi.

162
00:07:28,480 --> 00:07:30,700
Ja olgem nüüd taotleda ühendamine omamoodi.

163
00:07:30,700 --> 00:07:33,300
Nii et ma esimest soovite sortida
Vasakul pool sellest nimekirjast,

164
00:07:33,300 --> 00:07:37,370
ja olgem seetõttu
keskenduda 4, 8, 6 ja 2.

165
00:07:37,370 --> 00:07:41,000
>> Nüüd, kui ma minna
sorteerimine nimekirja size 4?

166
00:07:41,000 --> 00:07:45,990
Noh ma pean nüüd kaaluma
sorteerimine vasakul vasakul poolel.

167
00:07:45,990 --> 00:07:47,720
Jällegi, olgem kerida hetkeks.

168
00:07:47,720 --> 00:07:51,010
Kui pseudokoodi on see,
ja ma olen andnud kaheksa elemente,

169
00:07:51,010 --> 00:07:53,230
8 on ilmselgelt suurem
kui või võrdne 2.

170
00:07:53,230 --> 00:07:54,980
Nii esimese puhul ei kehti.

171
00:07:54,980 --> 00:07:58,120
Nii et sorteerida kaheksa elemente, ma esimest korda
sorteeri vasakul pool elemente,

172
00:07:58,120 --> 00:08:01,930
siis ma sorteerida õige poole, siis ma ühineda
Kahe sorditud poolitatud Kõik size 4.

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

174
00:08:02,470 --> 00:08:07,480
>> Aga kui sa oled mulle öelnud, sorteerida
vasakul poolel, mis on nüüd of size 4,

175
00:08:07,480 --> 00:08:09,350
kuidas ma sorteerida vasakule poole?

176
00:08:09,350 --> 00:08:11,430
Noh, kui mul on
input neljast elemendist,

177
00:08:11,430 --> 00:08:14,590
Ma sorteeritakse vasakul
kaks, siis kaks viimast,

178
00:08:14,590 --> 00:08:16,210
ja siis ma ühendada neid koos.

179
00:08:16,210 --> 00:08:18,700
Nii jälle, see muutub veidi
on meeles painutamine mängu siin,

180
00:08:18,700 --> 00:08:21,450
sest sina, selline, pea
mäletan, kuhu on lugu,

181
00:08:21,450 --> 00:08:23,620
kuid lõpus päeval,
antud mis tahes mitmeid elemente,

182
00:08:23,620 --> 00:08:25,620
kõigepealt tahan sorteerida
vasakul pool, siis paremal pool,

183
00:08:25,620 --> 00:08:26,661
siis liita need kokku.

184
00:08:26,661 --> 00:08:28,630
Alustame teha just nii.

185
00:08:28,630 --> 00:08:30,170
Siin on sisend kaheksa elemente.

186
00:08:30,170 --> 00:08:31,910
Nüüd me vaatame vasakul pool siin.

187
00:08:31,910 --> 00:08:33,720
Kuidas sorteerida neli elementi?

188
00:08:33,720 --> 00:08:35,610
Noh ma sorteeritakse vasakule poole.

189
00:08:35,610 --> 00:08:37,720
Nüüd, kui ma sorteerida vasakule poole?

190
00:08:37,720 --> 00:08:39,419
Noh ma olen saanud kaks elementi.

191
00:08:39,419 --> 00:08:41,240
Nii saab sortida need kaks elementi.

192
00:08:41,240 --> 00:08:44,540
2 on suurem või
võrdub 2, muidugi.

193
00:08:44,540 --> 00:08:46,170
Nii et esimese puhul ei kehti.

194
00:08:46,170 --> 00:08:49,010
>> Nii et ma nüüd sorteerida vasakul
pooled nendest kahest elemendist.

195
00:08:49,010 --> 00:08:50,870
Vasakul pool, muidugi, on vaid 4.

196
00:08:50,870 --> 00:08:54,020
Niisiis, kuidas ma sortida nimekirja üks element?

197
00:08:54,020 --> 00:08:57,960
Noh nüüd, et erilist aluspõhimõtted
up top, nii et rääkida, kehtib.

198
00:08:57,960 --> 00:09:01,470
1 on alla 2, ja mu
nimekiri on tõepoolest suurus 1.

199
00:09:01,470 --> 00:09:02,747
Nii et ma lihtsalt tagasi.

200
00:09:02,747 --> 00:09:03,580
Ma ei saa midagi teha.

201
00:09:03,580 --> 00:09:06,770
Ja tõepoolest, vaadata, mida ma olen
tehtud, 4 on juba järjestatud.

202
00:09:06,770 --> 00:09:09,220
Nagu ma olen juba
osaliselt edukas siin.

203
00:09:09,220 --> 00:09:11,750
>> Nüüd tundub tobe
punktile, kuid see on tõsi.

204
00:09:11,750 --> 00:09:13,700
4 on loetelu size 1.

205
00:09:13,700 --> 00:09:15,090
See on juba järjestatud.

206
00:09:15,090 --> 00:09:16,270
See on vasakul pool.

207
00:09:16,270 --> 00:09:18,010
Nüüd ma sorteerida õige pool.

208
00:09:18,010 --> 00:09:22,310
Minu panus on üks element, 8
Sarnaselt juba järjestatud.

209
00:09:22,310 --> 00:09:25,170
Stupid ka, aga jällegi,
antud põhimõte

210
00:09:25,170 --> 00:09:28,310
läheb võimaldab meil nüüd ehitada
Selle peale edukalt.

211
00:09:28,310 --> 00:09:32,260
4 järjestatud, 8 järjestatud nüüd
mis see oli viimane samm?

212
00:09:32,260 --> 00:09:35,330
Nii kolmas ja viimane etapp, mis tahes
aega sa sorteerimine nimekirja, meenutada,

213
00:09:35,330 --> 00:09:38,310
eesmärk oli ühendada kaheks pooleks,
vasakule ja paremale.

214
00:09:38,310 --> 00:09:39,900
Nii saab teha just nii.

215
00:09:39,900 --> 00:09:41,940
Minu vasakul pool on muidugi 4.

216
00:09:41,940 --> 00:09:43,310
Minu paremal pool on 8.

217
00:09:43,310 --> 00:09:44,100
>> Nii teeme seda.

218
00:09:44,100 --> 00:09:46,410
Esiteks ma lähen eraldada
täiendavat mälu

219
00:09:46,410 --> 00:09:48,680
et ma esindan,
lihtsalt teisejärguline massiiv,

220
00:09:48,680 --> 00:09:49,660
see on piisavalt suur, et mahtuda seda.

221
00:09:49,660 --> 00:09:52,243
Aga te võite ette kujutada laiendada
ristkülik kogu pikkuses,

222
00:09:52,243 --> 00:09:53,290
Kui meil on vaja rohkem hiljem.

223
00:09:53,290 --> 00:09:58,440
Kuidas võtta 4 ja 8 ning ühendada
Nende kahe nimekirjad suurus 1 koos?

224
00:09:58,440 --> 00:10:00,270
Ka siin üsna lihtne.

225
00:10:00,270 --> 00:10:03,300
4 saabub varem, siis tuleb 8.

226
00:10:03,300 --> 00:10:07,130
Sest kui ma tahan sorteerida
vasakul pool, siis paremal pool,

227
00:10:07,130 --> 00:10:09,900
ja siis liita need kaks poolt
koos, sorteeritud järjekorras

228
00:10:09,900 --> 00:10:11,940
4 saabub varem, siis tuleb 8.

229
00:10:11,940 --> 00:10:15,810
>> Nii me tundub, et edu, isegi
kuigi ma ei ole teinud ühtegi tegelikku tööd.

230
00:10:15,810 --> 00:10:17,800
Kuid pidage meeles, kus me oleme selles loos.

231
00:10:17,800 --> 00:10:19,360
Me algselt võttis kaheksa elemente.

232
00:10:19,360 --> 00:10:21,480
Me järjestatud vasakult poole, mis on 4.

233
00:10:21,480 --> 00:10:24,450
Siis me järjestatud vasakul pool
Vasaku poole, mis oli 2.

234
00:10:24,450 --> 00:10:25,270
Ja siin me läheme.

235
00:10:25,270 --> 00:10:26,920
Me teha, et samm.

236
00:10:26,920 --> 00:10:29,930
>> Nii et kui me oleme sorteeritud
vasak pool 2, nüüd

237
00:10:29,930 --> 00:10:32,130
on sorteerida õige pool 2.

238
00:10:32,130 --> 00:10:35,710
Nii et õige pool 2 on
Nende kahe väärtuse siin, 6 ja 2.

239
00:10:35,710 --> 00:10:40,620
Nii saab nüüd astuma sisend suurus
2 ja sortida vasakul pool, ja siis

240
00:10:40,620 --> 00:10:42,610
paremal pool, ja siis
liita need kokku.

241
00:10:42,610 --> 00:10:45,722
Noh, kuidas ma sortida nimekirja suurus
1, mis sisaldab ainult number 6?

242
00:10:45,722 --> 00:10:46,430
Ma olen juba teinud.

243
00:10:46,430 --> 00:10:48,680
See nimekiri suurus 1 sorteeritakse.

244
00:10:48,680 --> 00:10:52,140
>> Kuidas sorteerida teise nimekirja
size 1, niinimetatud paremal poolel.

245
00:10:52,140 --> 00:10:54,690
Aga see, liiga, on juba järjestatud.

246
00:10:54,690 --> 00:10:56,190
Number 2 on üksi.

247
00:10:56,190 --> 00:11:00,160
Nüüd mul on kaks poolt, vasakpoolne ja
õige, ma pean liita need kokku.

248
00:11:00,160 --> 00:11:01,800
Annan endale mõned ekstra ruumi.

249
00:11:01,800 --> 00:11:05,580
Ja panna 2 sinna,
siis 6 seal, seega

250
00:11:05,580 --> 00:11:10,740
sorteerimine selles nimekirjas, vasakule ja paremale,
ja ühinevad selle kokku lõpuks.

251
00:11:10,740 --> 00:11:12,160
Nii et ma olen veidi paremas seisus.

252
00:11:12,160 --> 00:11:16,250
Ma ei teinud, sest selgesti 4, 8, 2,
6 ei ole lõplik tellimine mida ma tahan.

253
00:11:16,250 --> 00:11:20,640
Aga mul on nüüd kaks nimekirjad suurus 2, et
on nii vastavalt sorteeritud.

254
00:11:20,640 --> 00:11:24,580
Nüüd, kui teil kerida oma vaimusilmas
silma, kust see jäta meid?

255
00:11:24,580 --> 00:11:28,520
Hakkasin kaheksa elemente, siis ma
whittled selle alla vasakule poole 4

256
00:11:28,520 --> 00:11:31,386
Seejärel vasakul poolel 2 ja
siis paremal pool 2,

257
00:11:31,386 --> 00:11:34,510
I lõppenud, seega sorteerimine vasakul
pool 2 ja paremal pool 2,

258
00:11:34,510 --> 00:11:37,800
Mis siis kolmas ja viimane etapp siin?

259
00:11:37,800 --> 00:11:41,290
Mul on ühendada kokku
kaks nimekirjad suurus 2.

260
00:11:41,290 --> 00:11:42,040
Nii lähme edasi.

261
00:11:42,040 --> 00:11:43,940
Ja ekraani siin anna
mulle lisamälu

262
00:11:43,940 --> 00:11:47,170
kuigi tehniliselt, märkate, et ma olen
on terve hunnik tühja ruumi up top

263
00:11:47,170 --> 00:11:47,670
seal.

264
00:11:47,670 --> 00:11:50,044
Kui ma tahan olla eriti
tõhusa ruumi tark,

265
00:11:50,044 --> 00:11:52,960
Ma võiks lihtsalt hakata liikuma elemendid
edasi-tagasi, üleval ja all.

266
00:11:52,960 --> 00:11:55,460
Aga just visuaalne selgus,
Ma panen ta allapoole,

267
00:11:55,460 --> 00:11:56,800
hoida asjad kena ja puhas.

268
00:11:56,800 --> 00:11:58,150
>> Nii et ma sain kaks nimekirjad suurus 2.

269
00:11:58,150 --> 00:11:59,770
Esimene nimekiri on 4 ja 8.

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

271
00:12:01,500 --> 00:12:03,950
Olgem ühendada need
koos sorteeritud järjekorras.

272
00:12:03,950 --> 00:12:09,910
2, muidugi, on esimene,
siis 4, siis 6, siis 8.

273
00:12:09,910 --> 00:12:12,560
Ja nüüd me tundume
mõnes huvitavas.

274
00:12:12,560 --> 00:12:15,720
Nüüd olen järjestatud poole
nimekirja ja juhuslikult, see on

275
00:12:15,720 --> 00:12:18,650
kõik paarisarvud, kuid et
on tõesti lihtsalt kokkusattumus.

276
00:12:18,650 --> 00:12:22,220
Ja mul on nüüd järjestatud vasakult
poole, nii et see 2, 4, 6 ja 8.

277
00:12:22,220 --> 00:12:23,430
Midagi on korrast ära.

278
00:12:23,430 --> 00:12:24,620
See tunne edusamme.

279
00:12:24,620 --> 00:12:26,650
>> Nüüd tundub, nagu ma olen
rääkinud igavesti nüüd,

280
00:12:26,650 --> 00:12:29,850
mis siis jääb üle oodata, kui see
algoritm on tõesti tõhusam.

281
00:12:29,850 --> 00:12:31,766
Aga me läheme läbi
see super metoodiliselt.

282
00:12:31,766 --> 00:12:34,060
Arvuti muidugi
teeksin seda niimoodi.

283
00:12:34,060 --> 00:12:34,840
Nii et kui me oleme?

284
00:12:34,840 --> 00:12:36,180
Alustasime kaheksa elemente.

285
00:12:36,180 --> 00:12:37,840
Ma järjestatud vasakul pool 4.

286
00:12:37,840 --> 00:12:39,290
I tunduvad olevat teinud sellega.

287
00:12:39,290 --> 00:12:42,535
Nüüd on järgmiseks sammuks
sorteeri paremal pool 4.

288
00:12:42,535 --> 00:12:44,410
Ja selles osas saame minna
kaudu veidi rohkem

289
00:12:44,410 --> 00:12:47,140
kiiresti, kuigi sa oled
Tere tulemast tagasi kerida või peatada, lihtsalt

290
00:12:47,140 --> 00:12:49,910
läbi mõelda seda
omas tempos, kuid mida

291
00:12:49,910 --> 00:12:53,290
meil nüüd on võimalus
teha täpselt sama algoritmi neljale

292
00:12:53,290 --> 00:12:54,380
erinevate numbrite puhul.

293
00:12:54,380 --> 00:12:57,740
>> Nii lähme edasi, ja keskendub
paremal pool, mida me oleme siin.

294
00:12:57,740 --> 00:13:01,260
Vasakpoolne pool sellest
paremal pool, ja nüüd

295
00:13:01,260 --> 00:13:04,560
vasakul poolel vasakul
poole, et õige pool,

296
00:13:04,560 --> 00:13:08,030
ja kuidas ma sortida nimekirja suurus
1, mis sisaldab ainult number 1?

297
00:13:08,030 --> 00:13:09,030
See on juba tehtud.

298
00:13:09,030 --> 00:13:11,830
Kuidas teha sama nimekirja
suurus 1, mis sisaldab ainult 7?

299
00:13:11,830 --> 00:13:12,840
See on juba tehtud.

300
00:13:12,840 --> 00:13:16,790
Kolmas etapp selle poole, siis
on ühendada need kaks elementi

301
00:13:16,790 --> 00:13:20,889
uude nimekirja suurus 2, 1 ja 7.

302
00:13:20,889 --> 00:13:23,180
Kas ei tundu, et on teinud kõik
et palju huvitavat tööd.

303
00:13:23,180 --> 00:13:24,346
Vaatame, mis juhtub järgmisena.

304
00:13:24,346 --> 00:13:29,210
Ma lihtsalt järjestatud vasakul pool
paremal pool minu originaal sisend.

305
00:13:29,210 --> 00:13:32,360
Nüüd on omamoodi õigus
poole, mis sisaldab 5 ja 3.

306
00:13:32,360 --> 00:13:35,740
Lähme jälle vaatama vasakule
poole, sorteeritud, õige pool, sorteeritud,

307
00:13:35,740 --> 00:13:39,120
ja ühendada need kaks kokku,
mõningaid lisaruumi,

308
00:13:39,120 --> 00:13:41,670
3 esikohal, siis tuleb 5.

309
00:13:41,670 --> 00:13:46,190
Ja nii nüüd oleme sorteeritud
Vasakul pool paremal pool

310
00:13:46,190 --> 00:13:49,420
algse probleem ja
paremal pool õige poole

311
00:13:49,420 --> 00:13:50,800
algse probleemi.

312
00:13:50,800 --> 00:13:52,480
Mis on kolmas ja viimane etapp?

313
00:13:52,480 --> 00:13:54,854
Noh, et ühendada need kaks poolt kokku.

314
00:13:54,854 --> 00:13:57,020
Nii et lubage mul saada endale mõned
lisaruumi, kuid jällegi, ma

315
00:13:57,020 --> 00:13:58,699
võiks kasutada, et vaba ruumi up top.

316
00:13:58,699 --> 00:14:00,490
Aga me ei kavatse hoida
see lihtsalt visuaalselt.

317
00:14:00,490 --> 00:14:07,070
Lubage mul ühinevad nüüd 1 ja
Seejärel 3 ja seejärel 5 ja seejärel 7.

318
00:14:07,070 --> 00:14:10,740
Jättes mulle nüüd koos
paremal pool originaal probleem

319
00:14:10,740 --> 00:14:12,840
see on täiesti järjestatud.

320
00:14:12,840 --> 00:14:13,662
>> Mis jääb?

321
00:14:13,662 --> 00:14:16,120
Ma tunnen, et mul hoida öeldes
samu asju uuesti ja uuesti,

322
00:14:16,120 --> 00:14:18,700
kuid see peegeldab
Asjaolu, et me kasutame recursion.

323
00:14:18,700 --> 00:14:21,050
Protsessi kasutades
algoritmi jälle ja jälle

324
00:14:21,050 --> 00:14:23,940
väiksemate alajaotused
algne probleem.

325
00:14:23,940 --> 00:14:27,580
Nii et ma nüüd on vasak järjestatud
poolel esialgse probleemiga.

326
00:14:27,580 --> 00:14:30,847
Mul on õigus sorteeritud poole
algse probleemi.

327
00:14:30,847 --> 00:14:32,180
Mis on kolmas ja viimane samm?

328
00:14:32,180 --> 00:14:33,590
Oh, see on ühinevate.

329
00:14:33,590 --> 00:14:34,480
Nii teeme seda.

330
00:14:34,480 --> 00:14:36,420
Olgem eraldada täiendavat
mälu, kuid mu Jumal, me

331
00:14:36,420 --> 00:14:37,503
võiks panna seda kõikjal nüüd.

332
00:14:37,503 --> 00:14:40,356
Meil on nii palju ruumi
meile, aga me hoiame seda lihtne.

333
00:14:40,356 --> 00:14:42,730
Selle asemel, et minna tagasi
edasi meie originaal mälu

334
00:14:42,730 --> 00:14:44,480
Lihtsalt tee seda
visuaalselt siia alla,

335
00:14:44,480 --> 00:14:47,240
et lõpetada ühendamine
vasakul pool ja paremal pool.

336
00:14:47,240 --> 00:14:49,279
>> Nii ühendades, mida ma pean tegema?

337
00:14:49,279 --> 00:14:50,820
Ma tahan elementide järjekorda.

338
00:14:50,820 --> 00:14:53,230
Nii vaadates vasakul pool,
Näen esimene number on 2.

339
00:14:53,230 --> 00:14:55,230
Ma vaatan paremale poole,
Ma näen esimest number

340
00:14:55,230 --> 00:14:58,290
on 1, nii ilmselt mille
number ma tahan kiskuda,

341
00:14:58,290 --> 00:15:00,430
ja pane esimene minu lõplik nimekiri?

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

343
00:15:01,449 --> 00:15:02,990
Nüüd ma tahan küsida, et sama küsimus.

344
00:15:02,990 --> 00:15:05,040
Vasakul pool, ma olen
ikka sai number 2.

345
00:15:05,040 --> 00:15:07,490
Paremal pool,
Mul arv 3.

346
00:15:07,490 --> 00:15:08,930
Kumba ma tahan valida?

347
00:15:08,930 --> 00:15:11,760
Muidugi, number 2 ja
Nüüd märkate kandidaadid

348
00:15:11,760 --> 00:15:13,620
on 4 vasakule, 3 paremale.

349
00:15:13,620 --> 00:15:15,020
Olgem muidugi valida 3.

350
00:15:15,020 --> 00:15:18,020
Nüüd kandidaadid on 4
Vasakul 5 paremale.

351
00:15:18,020 --> 00:15:19,460
Me muidugi valida 4.

352
00:15:19,460 --> 00:15:21,240
6 vasakule, 5 paremale.

353
00:15:21,240 --> 00:15:22,730
Me muidugi valida 5.

354
00:15:22,730 --> 00:15:25,020
6 vasakule, 7 paremale.

355
00:15:25,020 --> 00:15:29,320
Valisime 6, ja siis me
vali 7, ja siis me valime 8.

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

357
00:15:30,100 --> 00:15:34,370
>> Nii suur hulk sõnu hiljem, me
on järjestatud selles nimekirjas kaheksa elemendid

358
00:15:34,370 --> 00:15:38,450
loendisse ühe läbi kaheksa,
see on kasvav iga samm,

359
00:15:38,450 --> 00:15:40,850
kuid kui palju aega
see meid seda tegema.

360
00:15:40,850 --> 00:15:43,190
Noh ma olen teadlikult
laid asju piltlikult

361
00:15:43,190 --> 00:15:46,330
siin, et saaksime sellist
vaata või hindame jagunemine

362
00:15:46,330 --> 00:15:49,060
vallutavad, mis on juhtunud.

363
00:15:49,060 --> 00:15:52,830
>> Tõepoolest, kui sa vaatad tagasi pärast,
Ma jätsin kõik need kriipsjoontega

364
00:15:52,830 --> 00:15:55,660
olemas omanikud, saad,
selline, vaata, vastupidises järjekorras,

365
00:15:55,660 --> 00:15:58,800
kui sa selline tagasi vaadata
ajalugu nüüd, mu esialgne nimekiri

366
00:15:58,800 --> 00:16:00,250
on muidugi suuruse 8.

367
00:16:00,250 --> 00:16:03,480
Ja siis varem olin
tegelevad kahe loetelu size 4,

368
00:16:03,480 --> 00:16:08,400
ja seejärel neli nimekirja suurusega 2,
ja siis kaheksa nimekirjad suurus 1.

369
00:16:08,400 --> 00:16:10,151
>> Mida see,
selline, tuletavad meelde?

370
00:16:10,151 --> 00:16:11,858
Noh, tegelikult, ükskõik
algoritme me oleme

371
00:16:11,858 --> 00:16:14,430
vaatasin siiani, kus me
lõhe ja lõhe, ja lõhe

372
00:16:14,430 --> 00:16:19,500
hoida võttes asju uuesti ja
omakorda toob kaasa selle üldine idee.

373
00:16:19,500 --> 00:16:23,100
Ja nii on midagi
logaritmiline siin toimub.

374
00:16:23,100 --> 00:16:26,790
Ja see ei ole päris log n, kuid
seal on logaritmiline osa

375
00:16:26,790 --> 00:16:28,280
mida oleme lihtsalt teha.

376
00:16:28,280 --> 00:16:31,570
>> Nüüd Vaatleme, kuidas see tegelikult on.

377
00:16:31,570 --> 00:16:34,481
Nii logida n, jälle oli
suur sõiduaega,

378
00:16:34,481 --> 00:16:36,980
kui me tegime midagi
Kahendotsingupuu, nagu me nüüd nimetame seda,

379
00:16:36,980 --> 00:16:40,090
lõhe ja vallutada strateegia
mille kaudu leidsime Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Nüüd tehniliselt.

381
00:16:41,020 --> 00:16:43,640
See on samamoodi baasi 2 n, isegi
kuigi enamikus matemaatika klassi,

382
00:16:43,640 --> 00:16:45,770
10 Tavaliselt on aluseks, et sa oletad.

383
00:16:45,770 --> 00:16:48,940
Aga arvuti teadlased peaaegu alati
mõelda ja rääkida nii base 2,

384
00:16:48,940 --> 00:16:52,569
nii me tavaliselt lihtsalt öelda logi
n asemel log baasi 2 n,

385
00:16:52,569 --> 00:16:55,110
kuid nad on täpselt üks ja
Sama maailmas arvutis

386
00:16:55,110 --> 00:16:57,234
Teaduse ja kui kõrvale,
seal on konstandiks

387
00:16:57,234 --> 00:17:01,070
Erinevus nende kahe vahel, nii et see on
vaieldav niikuinii rohkem formaalsetel põhjustel.

388
00:17:01,070 --> 00:17:04,520
>> Aga nüüd, mida me hoolime
umbes on see näide.

389
00:17:04,520 --> 00:17:08,520
Nii et ärme tõestada eeskuju, kuid
vähemalt kasutada näide numbrid

390
00:17:08,520 --> 00:17:10,730
käepärast kui mõistuse kontrolli, kui soovite.

391
00:17:10,730 --> 00:17:14,510
Nii varem valem oli samamoodi alus
2 n, aga mis on n sel juhul.

392
00:17:14,510 --> 00:17:18,526
Mul oli n originaal numbrite või 8
originaal number konkreetselt.

393
00:17:18,526 --> 00:17:20,359
Nüüd on see olnud natuke
samas, aga ma olen päris

394
00:17:20,359 --> 00:17:25,300
Veenduge, et samamoodi baasi 2
väärtusest 8 on 3,

395
00:17:25,300 --> 00:17:29,630
ja tõepoolest, mis on tore, et on
et 3 on täpselt, mitu korda

396
00:17:29,630 --> 00:17:33,320
et saate jagada nimekirja
8-se pikkusega jälle ja jälle

397
00:17:33,320 --> 00:17:36,160
ja jälle, kuni sa oled jäänud
nimekirjad lihtsalt suurus 1.

398
00:17:36,160 --> 00:17:36,660
Õigus?

399
00:17:36,660 --> 00:17:40,790
8 läheb 4, läheb 2,
läheb 1, ja see on

400
00:17:40,790 --> 00:17:43,470
kajastavad täpselt, et
Pildil oli just hetk tagasi.

401
00:17:43,470 --> 00:17:47,160
Nii vähe meelerahu vaadata, kuhu
logaritm on tegelikult seotud.

402
00:17:47,160 --> 00:17:50,180
>> Nüüd, mida veel siin on tegemist? n.

403
00:17:50,180 --> 00:17:53,440
Nii märkate, et iga
kord, kui ma lahku nimekirja,

404
00:17:53,440 --> 00:17:58,260
kuigi vastupidises järjekorras ajalugu
siin, ma olin ikka teed n asju.

405
00:17:58,260 --> 00:18:02,320
See ühinevad samm vajalik, et
Ma puutuda igaüks numbrid,

406
00:18:02,320 --> 00:18:05,060
et lükake
Oma sobivas kohas.

407
00:18:05,060 --> 00:18:10,760
Nii et kuigi kõrgus käesoleva
skeem on suuruse log n n või 3,

408
00:18:10,760 --> 00:18:13,860
Konkreetsemalt teisisõnu
Ma tegin kolm osakonda siin.

409
00:18:13,860 --> 00:18:18,800
Kui palju tööd ma tegin horisontaalselt
mööda seda tabelit iga kord?

410
00:18:18,800 --> 00:18:21,110
>> Noh, ma tegin n sammud
töötada, sest kui ma olen

411
00:18:21,110 --> 00:18:24,080
sain nelja elemendi ja nelja elementi,
ja mul on vaja liita need kokku.

412
00:18:24,080 --> 00:18:26,040
Ma pean minema läbi
Nende nelja ja need neli,

413
00:18:26,040 --> 00:18:28,123
lõpuks liita need
tagasi kaheksa elemente.

414
00:18:28,123 --> 00:18:32,182
Kui vastupidi mul kaheksa sõrme
siin, mida ma ei ole, ja kaheksa

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- Kui ma olen
sain nelja sõrme siin,

416
00:18:34,390 --> 00:18:37,380
mis ma teen, neli sõrme
siin, mis ma teen,

417
00:18:37,380 --> 00:18:40,590
siis see on sama
Näiteks kui enne, kui ma

418
00:18:40,590 --> 00:18:44,010
on kaheksa sõrme kuigi
kokku, mida ma võib sellist, mida teha.

419
00:18:44,010 --> 00:18:47,950
Võin täpselt teha siin,
siis saan kindlasti

420
00:18:47,950 --> 00:18:50,370
ühendada kõik need nimekirjad
suurus 1 koos.

421
00:18:50,370 --> 00:18:54,050
Aga ma kindlasti vaatama
igal element täpselt üks kord.

422
00:18:54,050 --> 00:18:59,640
Nii kõrgus see protsess on log n,
laius selles protsessis, nii et rääkida,

423
00:18:59,640 --> 00:19:02,490
on n, siis mida me ilmselt
on lõppkokkuvõttes on

424
00:19:02,490 --> 00:19:06,470
käigu aja suuruse n korda sisse n.

425
00:19:06,470 --> 00:19:08,977
>> Teisisõnu, jaotasime
nimekirja, log n korda,

426
00:19:08,977 --> 00:19:11,810
kuid iga kord, kui me tegime seda, pidime
puudutada iga üks elemente

427
00:19:11,810 --> 00:19:13,560
et liita need
kõik koos, mis

428
00:19:13,560 --> 00:19:18,120
oli n samm, nii et meil on n korda sisse n,
või kui arvuti teadlane ütleks,

429
00:19:18,120 --> 00:19:20,380
asymptotically, mis
Oleks suur sõna

430
00:19:20,380 --> 00:19:22,810
kirjeldamiseks ülemise
seotud kohta sõiduaega,

431
00:19:22,810 --> 00:19:28,010
töötab meil on suur o
log n korda, kui nii võib öelda.

432
00:19:28,010 --> 00:19:31,510
>> Nüüd on see märkimisväärne, sest
meenutada, mida töötab ajad olid

433
00:19:31,510 --> 00:19:34,120
mull sorteerida, ja valik
sorteerida ja sisestamise sorteerida,

434
00:19:34,120 --> 00:19:38,200
ja isegi mõned teised, mis on olemas,
n ruudus oli, kus me olime.

435
00:19:38,200 --> 00:19:39,990
Ja saate, millist vaata seda siin.

436
00:19:39,990 --> 00:19:45,720
Kui n ruudus on ilmselt n korda
n, kuid siin on meil n korda sisse n,

437
00:19:45,720 --> 00:19:48,770
ja me teame juba nädal
null, et log n, logaritmiline,

438
00:19:48,770 --> 00:19:50,550
on parem kui midagi lineaarne.

439
00:19:50,550 --> 00:19:52,930
Lõppude lõpuks meelde pilt
punane ja kollane

440
00:19:52,930 --> 00:19:56,500
ja rohelised jooned, mida me juhtis, siis
roheline logaritmiline line oli palju väiksem.

441
00:19:56,500 --> 00:20:00,920
Ja seetõttu palju paremini ja kiiremini
kui otse kollast ja punast joont,

442
00:20:00,920 --> 00:20:05,900
n korda sisse n on tõepoolest parem
kui n korda n või n ruudus.

443
00:20:05,900 --> 00:20:09,110
>> Nii näib, et oleme
tuvastatud algoritmi ühendamine

444
00:20:09,110 --> 00:20:11,870
Sorteeri et töötab palju
kiirem aeg, ja tõepoolest,

445
00:20:11,870 --> 00:20:16,560
Sellepärast, varem sel nädalal, kui
nägime, et võistlus mull

446
00:20:16,560 --> 00:20:20,750
Sorteeri valiku sorteerida ning ühendada
sorteerida, liita omamoodi tõesti võitis.

447
00:20:20,750 --> 00:20:23,660
Ja tõepoolest, me isegi ei oodata
mull sorteerida ning valikut omamoodi

448
00:20:23,660 --> 00:20:24,790
lõpetama.

449
00:20:24,790 --> 00:20:27,410
>> Nüüd võtame ühe teise pass
selles, alates veidi

450
00:20:27,410 --> 00:20:31,030
ametliku perspektiivis ainult
Juhul, see kõlab paremini

451
00:20:31,030 --> 00:20:33,380
kui kõrgema arutelu.

452
00:20:33,380 --> 00:20:34,880
Nii et siin on algoritm uuesti.

453
00:20:34,880 --> 00:20:36,770
Palume end,
mida sõiduaega

454
00:20:36,770 --> 00:20:39,287
on selle algoritmi erinevate etappide?

455
00:20:39,287 --> 00:20:41,620
Olgem jagada see esimene
juhul ja teisel juhul.

456
00:20:41,620 --> 00:20:46,280
IF ja mujal IF juhul,
IF n on alla 2, lihtsalt tagasi.

457
00:20:46,280 --> 00:20:47,580
Tunne konstantset aega.

458
00:20:47,580 --> 00:20:50,970
See, millist, nagu kaks sammu,
IF n on alla 2, siis tagasi.

459
00:20:50,970 --> 00:20:54,580
Aga kui me ütles esmaspäeval,
konstantset aega, või suur o 1,

460
00:20:54,580 --> 00:20:57,130
võib olla kahe sammu, kolm
sammud, isegi 1000 sammu.

461
00:20:57,130 --> 00:20:59,870
Oluline on, et see on
pidev mitmeid samme.

462
00:20:59,870 --> 00:21:03,240
Nii kollane rõhutas pseudokoodi
Siin jookseb, siis me nimetame seda,

463
00:21:03,240 --> 00:21:04,490
konstantset aega.

464
00:21:04,490 --> 00:21:06,780
Nii ametlikumalt ja
me läheme mina-- seda

465
00:21:06,780 --> 00:21:09,910
saab millisel määral me
vormistama selle õiguse now-- T n,

466
00:21:09,910 --> 00:21:15,030
Tööaja probleem
mis võtab n midagid sisendiks

467
00:21:15,030 --> 00:21:19,150
võrdub suur o ühe,
IF n on alla 2.

468
00:21:19,150 --> 00:21:20,640
Nii et see on tingimuseks, et.

469
00:21:20,640 --> 00:21:24,150
Nii olevat selge, IF n on väiksem kui
2, meil on väga lühike nimekiri, siis

470
00:21:24,150 --> 00:21:29,151
jooksva aja, T n, kus n on
1 või 0, selles väga konkreetsel juhul

471
00:21:29,151 --> 00:21:30,650
see on lihtsalt saab olema pidev aega.

472
00:21:30,650 --> 00:21:32,691
See saab olla üks
samm, kaks sammu, mida iganes.

473
00:21:32,691 --> 00:21:33,950
See on kindel arv samme.

474
00:21:33,950 --> 00:21:38,840
>> Nii mahlane osa peab kindlasti olema
Teisel juhul on pseudokoodi.

475
00:21:38,840 --> 00:21:40,220
Else puhul.

476
00:21:40,220 --> 00:21:44,870
Sorteeri vasakul pool elemente, sorteerida õige
pool elemendid, ühendada sorteeritud pooleks.

477
00:21:44,870 --> 00:21:46,800
Kui kaua kõik need sammud võtta?

478
00:21:46,800 --> 00:21:49,780
Noh, kui jooksmine
aega, et sortida n elemendid

479
00:21:49,780 --> 00:21:53,010
on, olgem kutsuvad seda väga
üldmõistena, T n,

480
00:21:53,010 --> 00:21:55,500
Seejärel sorteerimine vasakul
poolel elemendid

481
00:21:55,500 --> 00:21:59,720
on selline, nagu öelda,
T n jagatuna 2,

482
00:21:59,720 --> 00:22:03,000
ja sarnaselt sorteerimine paremal pool
elementide on selline, nagu öelda,

483
00:22:03,000 --> 00:22:06,974
T n jagatuna 2 ja seejärel
liitmise järjestatud pooleks.

484
00:22:06,974 --> 00:22:08,890
Noh, kui mul on mõned
elementide arv siin

485
00:22:08,890 --> 00:22:11,230
nagu neli, ja mõned number
elementide siin, nagu neli,

486
00:22:11,230 --> 00:22:14,650
ja mul on ühendada kõik need neli
in, ja iga nimetatud neli, üks

487
00:22:14,650 --> 00:22:17,160
teise järel, nii et
lõppkokkuvõttes Mul on kaheksa elemente.

488
00:22:17,160 --> 00:22:20,230
Tundub nagu see on suur o n sammud?

489
00:22:20,230 --> 00:22:23,500
Kui mul n sõrmed ja iga
neid on kavas liita koht,

490
00:22:23,500 --> 00:22:25,270
see on nagu teine ​​n samme.

491
00:22:25,270 --> 00:22:27,360
>> Nii tõesti formulaically,
saame väljendada seda,

492
00:22:27,360 --> 00:22:29,960
kuigi veidi scarily esimesel
lühidalt, kuid see on midagi,

493
00:22:29,960 --> 00:22:31,600
mis lööb täpselt, et loogika.

494
00:22:31,600 --> 00:22:35,710
Jooksuaeg, T n, IF n
on suurem või võrdne 2.

495
00:22:35,710 --> 00:22:42,500
Sel juhul ELSE juhul on T n
jagatuna 2 pluss T N jagatuna 2,

496
00:22:42,500 --> 00:22:45,320
plus big o n, mõned
lineaarne mitmeid samme,

497
00:22:45,320 --> 00:22:51,630
võibolla täpselt n, võibolla 2 korda
n, kuid see on umbes, et n.

498
00:22:51,630 --> 00:22:54,060
Nii et on ka see, kuidas me suudame
väljendada seda formulaically.

499
00:22:54,060 --> 00:22:56,809
Nüüd sa ei tea seda, kui
olete salvestatud seda meelt,

500
00:22:56,809 --> 00:22:58,710
või otsida see üles
tagasi õpik, mis

501
00:22:58,710 --> 00:23:00,501
võib-olla natuke
petma lehte lõpus,

502
00:23:00,501 --> 00:23:03,940
aga see on tõesti läheb
anna meile suur o n log n,

503
00:23:03,940 --> 00:23:06,620
sest kordumise et
näed siin ekraanil,

504
00:23:06,620 --> 00:23:09,550
kui sa tegelikult tegi seda välja, kus
lõpmatu hulk näiteid,

505
00:23:09,550 --> 00:23:13,000
või sa tegid seda formulaically, siis oleks
näha, et see, sest see valem

506
00:23:13,000 --> 00:23:17,100
ise on rekursiivne, kus t
n üle midagi õigus,

507
00:23:17,100 --> 00:23:21,680
ja t N üle otsustada, seda saab
tegelikult väljendatakse lõppkokkuvõttes

508
00:23:21,680 --> 00:23:24,339
kui suur go n log n.

509
00:23:24,339 --> 00:23:26,130
Kui ei ole veendunud, et see
trahvi nüüd, lihtsalt

510
00:23:26,130 --> 00:23:28,960
võtma usu, et see on tõepoolest
mida see kordub viib,

511
00:23:28,960 --> 00:23:31,780
aga see on lihtsalt natuke rohkem
matemaatilist lähenemist otsin

512
00:23:31,780 --> 00:23:36,520
kell töötamise aeg ühendada omamoodi
põhineb selle pseudokoodi üksi.

513
00:23:36,520 --> 00:23:39,030
>> Võtame nüüd natuke
hingetõmbeaeg kõik see,

514
00:23:39,030 --> 00:23:41,710
ja võtta pilk
Teatud endine senaator, kes

515
00:23:41,710 --> 00:23:44,260
võiks vaadata veidi tuttav,
kes istus Google'i Eric

516
00:23:44,260 --> 00:23:48,410
Schmidt, mõni aeg tagasi, intervjuu
laval ees terve hunnik

517
00:23:48,410 --> 00:23:53,710
inimesed, rääkides lõppkokkuvõttes
teema, mis on päris nüüd tuttav.

518
00:23:53,710 --> 00:23:54,575
Võtame pilk.

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

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt: Nüüd senaator,
sa oled siin Google,

521
00:24:03,890 --> 00:24:09,490
ja mulle meeldib mõelda
eesistujariik tööintervjuu.

522
00:24:09,490 --> 00:24:11,712
Nüüd on raske tööd saada presidendiks.

523
00:24:11,712 --> 00:24:12,670
President Obama: Right.

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt: Ja sa oled
kavatseb teha [kuuldamatu] nüüd.

525
00:24:13,940 --> 00:24:15,523
Samuti on raske saada tööd Google.

526
00:24:15,523 --> 00:24:17,700
President Obama: Right.

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt: Meil ​​on küsimusi,
ja küsime meie kandidaatide küsimusi,

528
00:24:21,330 --> 00:24:24,310
ja see on Larry Schwimmer.

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

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

531
00:24:27,005 --> 00:24:28,130
Te arvan, et ma nalja?

532
00:24:28,130 --> 00:24:30,590
See on siinsamas.

533
00:24:30,590 --> 00:24:33,490
Mis on kõige tõhusam viis
sorteerima miljonit 32- täisarvud?

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

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

536
00:24:38,979 --> 00:24:41,020
Eric Schmidt: Mõnikord
võibolla ma vabandan, maybe--

537
00:24:41,020 --> 00:24:42,750
President Obama: Ei, ei,
ei, ei, ei, ma think--

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt: See ei ole see--

539
00:24:43,240 --> 00:24:45,430
President Obama: ma
arvan, ma arvan, et mull

540
00:24:45,430 --> 00:24:46,875
Sorteeri oleks vale tee.

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
Kes ütles talle seda?

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

545
00:24:54,020 --> 00:24:55,590
Ma ei arvutiteaduse nüüd--

546
00:24:55,590 --> 00:24:58,986
>> President Obama: Me oleme
sai meie spioonid seal.

547
00:24:58,986 --> 00:24:59,860
PROFESSOR: Okei.

548
00:24:59,860 --> 00:25:03,370
Jätkem meil nüüd
teoreetiline maailma algoritme

549
00:25:03,370 --> 00:25:06,520
in asümptootiliseks analüüs
selle, ja tagasi mõned teemad

550
00:25:06,520 --> 00:25:09,940
nädalast null ja üks, ja algus
eemaldada mõned abirattad,

551
00:25:09,940 --> 00:25:10,450
kui soovite.

552
00:25:10,450 --> 00:25:13,241
Nii et sa tõesti aru
lõpuks maast üles, mis on

553
00:25:13,241 --> 00:25:16,805
toimub all kapuuts, kui sa
kirjutada, koostada ja täita programme.

554
00:25:16,805 --> 00:25:19,680
Meenuta eelkõige, et see oli
Esimeses C programmi me vaatasime,

555
00:25:19,680 --> 00:25:22,840
kanooniline, lihtne programm
kehvasti, on suhteliselt

556
00:25:22,840 --> 00:25:24,620
kus see prindib, Hello World.

557
00:25:24,620 --> 00:25:27,610
Ja meenub, et ma ütlesin, protsessi
et lähtekoodi läbib

558
00:25:27,610 --> 00:25:28,430
on täpselt see.

559
00:25:28,430 --> 00:25:31,180
Te võtate oma lähtekoodi, edasi
see läbi koostaja, nagu rõkkama,

560
00:25:31,180 --> 00:25:34,650
ja välja tuleb objekti kood, mis
tunduda see, ühtede ja nullide

561
00:25:34,650 --> 00:25:37,880
et arvuti protsessor, tsentraalne
töötlemise üksus või aju,

562
00:25:37,880 --> 00:25:39,760
lõpuks aru.

563
00:25:39,760 --> 00:25:42,460
>> Selgub, et see on
natuke järeleandmisi,

564
00:25:42,460 --> 00:25:44,480
et me oleme nüüd on
positsiooni tease peale

565
00:25:44,480 --> 00:25:46,720
mõista, mida on tõesti olnud
toimub all kapuuts

566
00:25:46,720 --> 00:25:48,600
Iga kord, kui sa jooksed
Rõkkama, või üldisemalt,

567
00:25:48,600 --> 00:25:53,040
Iga kord, kui programmi,
kasutades Mark ja CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
Eelkõige asju
see on esimene loodud,

569
00:25:56,760 --> 00:25:58,684
kui te esimest kompileerida programmi.

570
00:25:58,684 --> 00:26:00,600
Teisisõnu, kui
võtta oma lähtekoodi

571
00:26:00,600 --> 00:26:04,390
ja kompileerida, mis on esimene
seda poolt väljastatav rõkkama

572
00:26:04,390 --> 00:26:06,370
on midagi, mida tuntakse kokkupanek koodi.

573
00:26:06,370 --> 00:26:08,990
Ja tegelikult, see näeb välja täpselt nagu see.

574
00:26:08,990 --> 00:26:11,170
>> Jooksin käsk
käsurea varem.

575
00:26:11,170 --> 00:26:16,260
Rõkkama kriips kapitali s hello.c,
ja see on loodud faili

576
00:26:16,260 --> 00:26:19,490
minu nimega hello.s,
mille sees olid täpselt

577
00:26:19,490 --> 00:26:22,290
Nende sisu ning veidi rohkem
ülespoole ja veidi allpool

578
00:26:22,290 --> 00:26:25,080
aga ma panin juiciest
info siin ekraanil.

579
00:26:25,080 --> 00:26:29,190
Ja kui sa vaatad tähelepanelikult, siis näete
vähemalt paar tuttav märksõnu.

580
00:26:29,190 --> 00:26:31,330
Meil on peamine tipus.

581
00:26:31,330 --> 00:26:35,140
Oleme printf alla keskele.

582
00:26:35,140 --> 00:26:38,670
Ja meil on ka tere
kurakriips n jutumärkides allapoole.

583
00:26:38,670 --> 00:26:42,450
>> Ja kõik muu siin
väga madal juhiseid

584
00:26:42,450 --> 00:26:45,500
et arvuti protsessor saab aru.

585
00:26:45,500 --> 00:26:50,090
CPU juhiseid, et liikuda mälu
ümber, et koormus stringid mälust,

586
00:26:50,090 --> 00:26:52,750
ja lõpuks, print
asjad ekraanil.

587
00:26:52,750 --> 00:26:56,780
Nüüd, mis juhtub, kuigi pärast
Selle kokkupanek kood genereeritakse?

588
00:26:56,780 --> 00:26:59,964
Lõppkokkuvõttes sa tõepoolest
veel luua objekti kood.

589
00:26:59,964 --> 00:27:02,630
Aga sammud, mis on tõesti
kestnud all kapuuts

590
00:27:02,630 --> 00:27:04,180
otsida veidi rohkem niimoodi.

591
00:27:04,180 --> 00:27:08,390
Lähtekood muutub montaaž koodi
mis siis saab objekti kood,

592
00:27:08,390 --> 00:27:11,930
ja operatiivne sõna on siin, et
kui sa kompileerida lähtekoodist,

593
00:27:11,930 --> 00:27:16,300
välja tuleb kokkupanek kood ja seejärel
kui sa koguda oma kokkupanek koodi

594
00:27:16,300 --> 00:27:17,800
välja tuleb objekti kood.

595
00:27:17,800 --> 00:27:20,360
>> Nüüd rõkkama on super kogenud,
nagu palju koostajad,

596
00:27:20,360 --> 00:27:23,151
ja ta teeb kõik need sammud
kokku ja ei tähenda see tingimata

597
00:27:23,151 --> 00:27:25,360
väljund mõni vahepealne
faile, mida saate isegi näha.

598
00:27:25,360 --> 00:27:28,400
See lihtsalt kogub asju,
mis on üldine termin, mis

599
00:27:28,400 --> 00:27:30,000
kirjeldab kogu seda protsessi.

600
00:27:30,000 --> 00:27:32,000
Aga kui sa tõesti tahad
olema eelkõige seal

601
00:27:32,000 --> 00:27:34,330
palju läheb seal hästi.

602
00:27:34,330 --> 00:27:38,860
>> Aga olgem kaaluma ka nüüd, et isegi
et super lihtne programm, hello.c,

603
00:27:38,860 --> 00:27:40,540
nimetatakse funktsiooni.

604
00:27:40,540 --> 00:27:41,870
Ta kutsus printf.

605
00:27:41,870 --> 00:27:46,900
Aga ma ei kirjuta printf, tõepoolest,
mis kaasas c, nii rääkida.

606
00:27:46,900 --> 00:27:51,139
See funktsioon meelde tuletada, et on
deklareeritud standard io.h, mis

607
00:27:51,139 --> 00:27:53,180
on päisefailist, mis
on teema me tegelikult

608
00:27:53,180 --> 00:27:55,780
sukelduda põhjalikumalt enne pikk.

609
00:27:55,780 --> 00:27:58,000
Aga päisefailist on
Tavaliselt kaasneb

610
00:27:58,000 --> 00:28:02,920
koodi abil faili lähtekoodi faili, nii et
palju nagu on olemas standard io.h.

611
00:28:02,920 --> 00:28:05,930
>> Millalgi tagasi, keegi,
või kellegi, kirjutas ka

612
00:28:05,930 --> 00:28:11,040
fail nimega standard io.c, in
mille tegelik mõisted,

613
00:28:11,040 --> 00:28:15,220
või rakenduste printf,
ja kobarad muid funktsioone,

614
00:28:15,220 --> 00:28:16,870
tegelikult kirjutatud.

615
00:28:16,870 --> 00:28:22,140
Nii, arvestades, et juhul, kui arvame, võttes
siin vasakul, hello.c, et kui

616
00:28:22,140 --> 00:28:26,250
koostatud, annab meile hello.s, isegi kui
Rõkkama ei viitsinud kokkuhoid kohas

617
00:28:26,250 --> 00:28:31,360
Me näeme seda, ja et montaaži koodi
saab kokku võtta hello.o, mis

618
00:28:31,360 --> 00:28:34,630
on tõepoolest vaikenimetus
antakse alati kompileerida allikas

619
00:28:34,630 --> 00:28:39,350
kood objekti kood, kuid ei ole
päris valmis täitma seda veel,

620
00:28:39,350 --> 00:28:41,460
sest järjekordne samm
peab juhtuma, ja on

621
00:28:41,460 --> 00:28:44,440
toimunud viimastel
nädalat, võib-olla teadmata teid.

622
00:28:44,440 --> 00:28:47,290
>> Täpsemalt kusagil
in CS50 IDE, ja see,

623
00:28:47,290 --> 00:28:49,870
Ka on natuke
järeleandmisi hetkeks,

624
00:28:49,870 --> 00:28:54,670
seal on, või oli ammu,
fail nimega standard io.c,

625
00:28:54,670 --> 00:28:58,440
et keegi kompileeritud
standard io.s või samaväärne,

626
00:28:58,440 --> 00:29:02,010
et keegi siis kokku pandud
kirjakeele io.o,

627
00:29:02,010 --> 00:29:04,600
või selgub sisse
veidi erinev faili

628
00:29:04,600 --> 00:29:07,220
vormi, mis võib olla erinev
faililaiend kokku,

629
00:29:07,220 --> 00:29:11,720
kuid teoreetiliselt ja põhimõtteliselt täpselt
need sammud pidi juhtuma mingi.

630
00:29:11,720 --> 00:29:14,060
Mis tähendab, et nüüd
kui ma kirjutan programmi

631
00:29:14,060 --> 00:29:17,870
hello.c, et lihtsalt ütleb, tere,
ja ma kasutan kellegi koodi

632
00:29:17,870 --> 00:29:22,480
nagu printf, mis oli Ükskord
ajal, fail nimega standard io.c,

633
00:29:22,480 --> 00:29:26,390
siis kuidagi pean võtma minu
objekti kood, minu ühtede ja nullide,

634
00:29:26,390 --> 00:29:29,260
ja et inimese objekti
kood või ühtede ja nullide,

635
00:29:29,260 --> 00:29:34,970
ja kuidagi siduda need kokku ühte
üks lõplik fail nimega hello, et

636
00:29:34,970 --> 00:29:38,070
on kõik nullid ja
need on minu peamine funktsioon,

637
00:29:38,070 --> 00:29:40,830
ja kõik nullid
ja need, printf.

638
00:29:40,830 --> 00:29:44,900
>> Ja tõepoolest, et viimane protsess on
nimetatakse, sidudes oma objekti kood.

639
00:29:44,900 --> 00:29:47,490
Mille väljundiks
on käivitatav fail.

640
00:29:47,490 --> 00:29:49,780
Nii õiglus, kell
Lõppkokkuvõttes, midagi

641
00:29:49,780 --> 00:29:52,660
muutunud nädalal üks, kui me
hakkas koostamise programme.

642
00:29:52,660 --> 00:29:55,200
Tõepoolest, kõik see on olnud
toimub all kapuuts,

643
00:29:55,200 --> 00:29:57,241
kuid nüüd oleme olukorras
kus me saame tegelikult

644
00:29:57,241 --> 00:29:58,794
tease peale nende erinevate etappide.

645
00:29:58,794 --> 00:30:00,710
Ja tõepoolest, lõpus
Päeva oleme endiselt

646
00:30:00,710 --> 00:30:04,480
jäänud ühtede ja nullide, mis
on tegelikult suur Segue nüüd

647
00:30:04,480 --> 00:30:08,620
teisele võime C, et
meil ei olnud võimendada tõenäoliselt

648
00:30:08,620 --> 00:30:11,250
siiani tuntud bitwise ettevõtjad.

649
00:30:11,250 --> 00:30:15,220
Teisisõnu, seni, millal me oleme
käsitletud andmete C või muutujate C,

650
00:30:15,220 --> 00:30:17,660
oleme olnud asjad
tähemärki ja ujukite ja ins

651
00:30:17,660 --> 00:30:21,990
ja pikad ja kahekordistab jms, kuid
Kõigil neil on vähemalt kaheksa biti.

652
00:30:21,990 --> 00:30:25,550
Me pole kunagi veel suutnud
manipuleerida üksikute bittide,

653
00:30:25,550 --> 00:30:28,970
kuigi üksikute natuke, me
teate, ei kujuta endast 0 ja 1.

654
00:30:28,970 --> 00:30:32,640
Nüüd selgub, et C, siis
ei pääse individuaalsete bitti,

655
00:30:32,640 --> 00:30:35,530
kui sa tead, süntaks,
millega saada neid.

656
00:30:35,530 --> 00:30:38,010
>> Võtame pilk
kell bitwise ettevõtjad.

657
00:30:38,010 --> 00:30:41,700
Nii pildil siin on mõned sümbolid,
oleme, selline, justkui, näinud.

658
00:30:41,700 --> 00:30:45,580
Näen ampersand, vertikaalne
baari, ja mõned teised ka,

659
00:30:45,580 --> 00:30:49,430
ja meelde tuletada, et ampersand ampersand
on midagi, mida me varem näinud.

660
00:30:49,430 --> 00:30:54,060
Loogiline JA operaator, kus teil on
kahes kokku või loogilise OR

661
00:30:54,060 --> 00:30:56,300
operaator, kus te
on püsttriipudele.

662
00:30:56,300 --> 00:31:00,550
Bitikaupa ettevõtjad, mida me tulen
vaata tegutseda bitti individuaalselt,

663
00:31:00,550 --> 00:31:03,810
lihtsalt kasutada ühte ampersand, et
vertikaalse riba, katus sümbolit

664
00:31:03,810 --> 00:31:06,620
tuleb järgmisena, väike
tilde ja seejärel vasakule

665
00:31:06,620 --> 00:31:08,990
sulg Vasaksulg või
õige sulg õigus sulg.

666
00:31:08,990 --> 00:31:10,770
Igaüks neist on erinev tähendus.

667
00:31:10,770 --> 00:31:11,950
>> Tegelikult võtame pilk.

668
00:31:11,950 --> 00:31:16,560
Lähme vana kooli täna ja kasutamine
puutetundlik alates Läinud,

669
00:31:16,560 --> 00:31:18,002
tuntud kui valge tahvel.

670
00:31:18,002 --> 00:31:19,710
Ja see valge tahvel
läheb võimaldab meil

671
00:31:19,710 --> 00:31:27,360
väljendada mõned üsna lihtne sümboleid,
või pigem mõned üsna lihtne valemeid,

672
00:31:27,360 --> 00:31:29,560
et siis saame lõpuks
finantsvõimendus, et

673
00:31:29,560 --> 00:31:33,230
juurdepääsu üksikisiku
bittide C programmi.

674
00:31:33,230 --> 00:31:34,480
Teisisõnu, teeme seda.

675
00:31:34,480 --> 00:31:37,080
Vaatame kõigepealt rääkida jaoks
hetkel umbes ampersand,

676
00:31:37,080 --> 00:31:39,560
mis on bitwise ja operaatorist.

677
00:31:39,560 --> 00:31:42,130
Teisisõnu, see on
operaator, mis võimaldab

678
00:31:42,130 --> 00:31:45,930
mind on vasakpoolne muutuja
tavaliselt ja parempoolne muutuja,

679
00:31:45,930 --> 00:31:50,640
või üksikisiku väärtus, et kui me ise
need kokku, annab mulle lõpptulemus.

680
00:31:50,640 --> 00:31:51,560
Mida ma mõtlen?

681
00:31:51,560 --> 00:31:54,840
Kui programm, teil on muutuv
mis talletab üks nendest väärtustest,

682
00:31:54,840 --> 00:31:58,000
või olgem hoida lihtsa ja lihtsalt
kirjutada ühtede ja nullide individuaalselt,

683
00:31:58,000 --> 00:32:00,940
Siin on, kuidas ampersand operaator töötab.

684
00:32:00,940 --> 00:32:06,400
0-märgiga 0 läheb võrdne 0.

685
00:32:06,400 --> 00:32:07,210
Nüüd, miks see nii on?

686
00:32:07,210 --> 00:32:09,291
>> See on väga sarnane
Loogiline väljendeid,

687
00:32:09,291 --> 00:32:10,540
et me oleme arutanud siiani.

688
00:32:10,540 --> 00:32:15,800
Kui te arvate, ju 0 on
vale, 0 on väär, vale ja vale

689
00:32:15,800 --> 00:32:18,720
on, nagu me oleme arutanud
loogiliselt ka vale.

690
00:32:18,720 --> 00:32:20,270
Nii saame 0 ka siin.

691
00:32:20,270 --> 00:32:24,390
Kui te võtate 0 ampersand
1 hästi, et ka

692
00:32:24,390 --> 00:32:29,890
saab olema 0, sest sel
vasakul väljendus, et olla tõsi või 1,

693
00:32:29,890 --> 00:32:32,360
oleks vaja, et olla tõsi ja tõsi.

694
00:32:32,360 --> 00:32:36,320
Aga meil on siin vale
ja tõsi, või 0 ja 1.

695
00:32:36,320 --> 00:32:42,000
Nüüd jälle, kui meil on 1 ampersand
0, et ka saab olema 0,

696
00:32:42,000 --> 00:32:47,240
ja kui meil on 1 ampersand 1
Lõpuks on meil 1 bit.

697
00:32:47,240 --> 00:32:50,340
Nii teisisõnu, me ei tee
midagi huvitavat selle operaatoriga

698
00:32:50,340 --> 00:32:51,850
lihtsalt veel, see ampersand operaator.

699
00:32:51,850 --> 00:32:53,780
See on bitwise ja operaatorist.

700
00:32:53,780 --> 00:32:57,290
Kuid need on koostisained
mille kaudu me saame teha

701
00:32:57,290 --> 00:32:59,240
huvitavaid asju, nagu me varsti näha.

702
00:32:59,240 --> 00:33:02,790
>> Nüüd vaatame ainult ühe
püstribale siin paremal.

703
00:33:02,790 --> 00:33:06,710
Kui mul on 0 natuke ja ma
VÕI seda, BitWise

704
00:33:06,710 --> 00:33:11,030
Või käitaja muu 0 natuke,
mis läheb mulle 0.

705
00:33:11,030 --> 00:33:17,540
Kui ma võtan 0 natuke ja OR seda
1 bit, siis ma lähen 1.

706
00:33:17,540 --> 00:33:19,830
Ja tegelikult, lihtsalt
selgus, lubage mul tagasi minna,

707
00:33:19,830 --> 00:33:23,380
nii et minu püstribade
ei eksi 1 s.

708
00:33:23,380 --> 00:33:26,560
Kirjutan kõik
minu 1 on natuke rohkem

709
00:33:26,560 --> 00:33:32,700
selgelt, et me kõrval näha, kui ma
on 1 või 0, et see saab olema 1,

710
00:33:32,700 --> 00:33:39,060
ja kui mul on 1 või 1, et
Ka see saab olema 1.

711
00:33:39,060 --> 00:33:42,900
Nii et näete, loogiliselt, et OR
operaator käitub väga erinevalt.

712
00:33:42,900 --> 00:33:48,070
See annab mulle 0 või 0 annab mulle 0, kuid
Iga muu kombinatsioon annab mulle 1.

713
00:33:48,070 --> 00:33:52,480
Nii kaua, kui mul on üks 1
valem, tulemus saab olema 1.

714
00:33:52,480 --> 00:33:55,580
>> Erinevalt JA
operaator, ampersand,

715
00:33:55,580 --> 00:34:00,940
ainult siis, kui mul on kaks 1-aasta
võrrand, ma tegelikult saada 1 out.

716
00:34:00,940 --> 00:34:02,850
Nüüd on mõned muud
ettevõtjad samuti.

717
00:34:02,850 --> 00:34:04,810
Üks neist on veidi rohkem kaasatud.

718
00:34:04,810 --> 00:34:07,980
Nii et lubage mul minna ja kustutada
Selle vabastada ruumi.

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

720
00:34:13,020 --> 00:34:16,460
Ja võtame pilk
Katus tähendab, et üks hetk.

721
00:34:16,460 --> 00:34:18,210
See on tavaliselt
iseloomu saab kirjutada

722
00:34:18,210 --> 00:34:21,420
klaviatuuril Shift all hoides ja
siis üks arvudest atop oma USA

723
00:34:21,420 --> 00:34:22,250
klaviatuuri.

724
00:34:22,250 --> 00:34:26,190
>> Nii et see on eksklusiivne
Või käitaja välistav VÕI.

725
00:34:26,190 --> 00:34:27,790
Nii et me lihtsalt nägin OR operaatoriga.

726
00:34:27,790 --> 00:34:29,348
See on ainus või operaator.

727
00:34:29,348 --> 00:34:30,639
Mis tegelikult vahet seal on?

728
00:34:30,639 --> 00:34:34,570
Noh olgem lihtsalt vaadata valem,
ja kasutada seda kui koostisosad lõpuks.

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

730
00:34:37,690 --> 00:34:39,650
Ma ütlen alati 0.

731
00:34:39,650 --> 00:34:41,400
See määratlus XOR.

732
00:34:41,400 --> 00:34:47,104
0 XOR 1 läheb 1.

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 saab olema 1,
ja 1 XOR 1 läheb?

734
00:34:58,810 --> 00:34:59,890
Vale?

735
00:34:59,890 --> 00:35:00,520
Või eks?

736
00:35:00,520 --> 00:35:01,860
Ma ei tea.

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

738
00:35:02,810 --> 00:35:04,700
Nüüd sellest, mis siin toimub?

739
00:35:04,700 --> 00:35:06,630
Noh mõelda
nimi see operaator.

740
00:35:06,630 --> 00:35:09,980
Exclusive OR, nii nagu
nimi, selline, näitab,

741
00:35:09,980 --> 00:35:13,940
Vastus on ainult kavatse olla
1, kui sisendid on eksklusiivne,

742
00:35:13,940 --> 00:35:15,560
ainult erinevad.

743
00:35:15,560 --> 00:35:18,170
Nii et siin sisendid on
sama, nii väljund on 0.

744
00:35:18,170 --> 00:35:20,700
Siin sisendid on
sama, nii väljund on 0.

745
00:35:20,700 --> 00:35:25,640
Siin on väljundid on erinevad,
on eksklusiivne, seega väljund on 1.

746
00:35:25,640 --> 00:35:28,190
Nii et see on väga sarnane
Ja see on väga sarnane,

747
00:35:28,190 --> 00:35:32,760
või pigem on see väga sarnane
OR, kuid ainult eksklusiivne viis.

748
00:35:32,760 --> 00:35:36,210
See üks ei ole enam 1,
sest meil on kaks 1-,

749
00:35:36,210 --> 00:35:38,621
ja mitte ainult, vaid üks neist.

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

751
00:35:39,120 --> 00:35:40,080
Aga teised?

752
00:35:40,080 --> 00:35:44,220
Noh tilde, vahepeal on
tegelikult kena ja lihtne õnneks.

753
00:35:44,220 --> 00:35:46,410
Ja see on unaarse
operaatori, mis tähendab

754
00:35:46,410 --> 00:35:50,400
see on rakendatud ainult üks sisend,
üks operand, kui nii võib öelda.

755
00:35:50,400 --> 00:35:51,800
Mitte vasakule ja paremale.

756
00:35:51,800 --> 00:35:56,050
Teisisõnu, kui te võtate tilde kohta
0, siis vastus on vastupidine.

757
00:35:56,050 --> 00:35:59,710
Ja kui te võtate tilde of 1
Vastus tekib vastupidine.

758
00:35:59,710 --> 00:36:02,570
Nii tilde operaator
viis nullides natuke,

759
00:36:02,570 --> 00:36:06,000
või flipping natuke
0-1 või 1-0.

760
00:36:06,000 --> 00:36:09,820
>> Ja mis jätab meid lõpuks
vaid kaks viimast ettevõtjad,

761
00:36:09,820 --> 00:36:13,840
niinimetatud nihutamist vasakule ja
Niinimetatud õigus vahetuse operaator.

762
00:36:13,840 --> 00:36:16,620
Võtame pilk kuidas need tööd.

763
00:36:16,620 --> 00:36:20,780
Vasakpoolne vahetuse operaator, kirjutatud
kahe noolsulgudes niimoodi,

764
00:36:20,780 --> 00:36:22,110
toimib järgnevalt.

765
00:36:22,110 --> 00:36:27,390
Kui minu sisend, või minu operandi, vasakule
vahetuse operaator on lihtsalt 1.

766
00:36:27,390 --> 00:36:33,750
Ja ma siis ütlen, et arvuti
vasakule nihe, et 1, ütleme seitsme koha,

767
00:36:33,750 --> 00:36:37,150
tulemus on nii, nagu ma
võtta, et 1 ja liigutada

768
00:36:37,150 --> 00:36:40,160
seitsme koha üle
Vasakul ja vaikimisi

769
00:36:40,160 --> 00:36:42,270
me läheme eeldada, et
ruumi paremale

770
00:36:42,270 --> 00:36:44,080
läheb polsterdatud nulli.

771
00:36:44,080 --> 00:36:50,316
Teisisõnu, 1 vasakule nihe 7 läheb
mulle, et 1, millele järgnes 1, 2, 3,

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

773
00:36:54,060 --> 00:36:57,380
Nii nii, siis saab
võtta väike number nagu 1,

774
00:36:57,380 --> 00:37:00,740
ja selgelt oleks palju
palju, palju suurem sel viisil,

775
00:37:00,740 --> 00:37:06,460
aga me tegelikult näeme
targem lähenemisviise see

776
00:37:06,460 --> 00:37:08,080
asemel, samuti,

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

778
00:37:08,720 --> 00:37:10,060
Ongi nädal kolm.

779
00:37:10,060 --> 00:37:11,400
Me näeme järgmine kord.

780
00:37:11,400 --> 00:37:12,770
See oli CS50.

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

782
00:37:17,270 --> 00:37:22,243
>> [Muusika mängib]

783
00:37:22,243 --> 00:37:25,766
>> SPEAKER 1: Ta oli suupiste
baaris süüa kuuma sepitsus plombiir.

784
00:37:25,766 --> 00:37:28,090
Tal oli kõik üle tema näo.

785
00:37:28,090 --> 00:37:30,506
Ta kannab, et šokolaad nagu habe

786
00:37:30,506 --> 00:37:31,756
SPEAKER 2: Mida sa teed?

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

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

789
00:37:33,500 --> 00:37:36,800
>> SPEAKER 2: Kas sa lihtsalt topelt dip?

790
00:37:36,800 --> 00:37:38,585
Sa topelt kasta kiip.

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

792
00:37:39,460 --> 00:37:44,440
SPEAKER 2: Sa kasta kiip, siis
võttis hammustada, ja sa kasta uuesti.

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

794
00:37:44,940 --> 00:37:48,440
SPEAKER 2: Nii et nagu paneb
kogu oma suu õige dip.

795
00:37:48,440 --> 00:37:52,400
Järgmine kord, kui te võtate chip,
lihtsalt pane see kord, ja seda lõpetada.

796
00:37:52,400 --> 00:37:53,890
>> SPEAKER 3: Tead mis, Dan?

797
00:37:53,890 --> 00:37:58,006
Sa pane nii, et sa tahad pane.

798
00:37:58,006 --> 00:38:01,900
Ma kasta nii, et ma tahan pane.

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