1
00:00:00,000 --> 00:00:11,904
>> [MUSIC JOC]

2
00:00:11,904 --> 00:00:12,910
>> PROFESORUL: Bine.

3
00:00:12,910 --> 00:00:16,730
Aceasta este CS50 și acest lucru este
la sfârșitul săptămânii trei.

4
00:00:16,730 --> 00:00:20,230
Deci suntem astăzi aici, nu-Sanders în
Teatru, în schimb în Weidner Library.

5
00:00:20,230 --> 00:00:23,170
In interiorul care este un studio
cunoscut sub numele de Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
sau să spunem Studio H, sau trebuie
noi say-- Dacă va plăcut că gluma,

7
00:00:28,310 --> 00:00:30,540
este de fapt de la
coleg de clasa, Mark, on-line,

8
00:00:30,540 --> 00:00:32,420
care a sugerat ca mai mult prin intermediul Twitter.

9
00:00:32,420 --> 00:00:34,270
Acum, ce e cool despre
fiind aici, într-un studio

10
00:00:34,270 --> 00:00:38,410
este că eu sunt înconjurat de acestea verde
pereți, un ecran verde sau chromakey,

11
00:00:38,410 --> 00:00:43,290
ca să spunem așa, ceea ce înseamnă că este CS50
echipa de producție, fără știrea mine

12
00:00:43,290 --> 00:00:47,380
acum, ar putea fi punerea
ma mai oriunde în lume,

13
00:00:47,380 --> 00:00:48,660
pentru bine și la rău.

14
00:00:48,660 --> 00:00:51,800
>> Acum, ceea ce se află în perspectivă, problema set
două este în mâinile tale pentru această săptămână,

15
00:00:51,800 --> 00:00:53,830
dar cu problema set
trei în această săptămână vine,

16
00:00:53,830 --> 00:00:56,600
va fi contestată cu
așa-numitul joc de 15,

17
00:00:56,600 --> 00:00:58,960
o parte favoarea vechi, care
s-ar putea aminti ce a primit

18
00:00:58,960 --> 00:01:02,030
ca un copil care are o grămadă
de numere care pot aluneca în sus, în jos,

19
00:01:02,030 --> 00:01:05,790
stânga și la dreapta, și există un decalaj
în puzzle, în care aveți

20
00:01:05,790 --> 00:01:07,840
poate aluneca de fapt aceste piese de puzzle.

21
00:01:07,840 --> 00:01:11,150
În cele din urmă veți primi acest
puzzle în unele ordine aleatorie semi,

22
00:01:11,150 --> 00:01:12,940
iar scopul este de a
sortare-l, de sus în jos,

23
00:01:12,940 --> 00:01:16,310
la stânga la dreapta, de la unul
tot drumul până prin 15.

24
00:01:16,310 --> 00:01:19,360
>> Din păcate, implementarea
veți avea la îndemână

25
00:01:19,360 --> 00:01:21,590
va fi software-ul
bazat, nu fizic.

26
00:01:21,590 --> 00:01:25,280
Esti de fapt va trebui să scrie
cod cu care un student sau utilizator poate

27
00:01:25,280 --> 00:01:26,760
juca acest joc de 15.

28
00:01:26,760 --> 00:01:29,030
Și, de fapt, în hacker
ediție de joc de 15,

29
00:01:29,030 --> 00:01:32,155
vei fi o provocare pentru a pune în aplicare,
nu doar redarea acestei școli vechi

30
00:01:32,155 --> 00:01:35,010
joc, ci mai degrabă rezolvarea
de ea, de punere în aplicare modul Dumnezeu,

31
00:01:35,010 --> 00:01:38,280
ca să spunem așa, că, de fapt
rezolvă puzzle pentru om,

32
00:01:38,280 --> 00:01:41,080
oferindu-le cu aluzie,
după indiciu, după indiciu.

33
00:01:41,080 --> 00:01:42,280
Cu atât mai mult cu privire la acest săptămâna viitoare.

34
00:01:42,280 --> 00:01:43,720
Dar asta e ceea ce se află în fața.

35
00:01:43,720 --> 00:01:47,610
>> Pentru moment amintesc că la începutul acestei săptămâni
am avut acest Cliffhanger, dacă vreți,

36
00:01:47,610 --> 00:01:52,560
prin care cele mai bune faceam de sortare
înțelept a fost o limită superioară de mare o de n

37
00:01:52,560 --> 00:01:53,210
pătrat.

38
00:01:53,210 --> 00:01:56,520
Cu alte cuvinte, cu bule de sortare,
fel de selecție, sortare prin inserție,

39
00:01:56,520 --> 00:01:59,120
toate acestea, în timp ce diferite
în punerea lor în aplicare,

40
00:01:59,120 --> 00:02:03,480
involuat intr-o n pătrat rulează
timp în cel mai rău caz foarte.

41
00:02:03,480 --> 00:02:06,010
Și, în general, vom presupune că
cel mai rău caz pentru sortarea foarte

42
00:02:06,010 --> 00:02:08,814
este una care intrările dvs.
sunt complet înapoi.

43
00:02:08,814 --> 00:02:11,980
Și într-adevăr, a fost nevoie de destul de câțiva pași
să pună în aplicare fiecare dintre aceste algoritmi.

44
00:02:11,980 --> 00:02:15,110
>> Acum, la sfârșitul clasei
Reamintim, am comparat cu bule fel

45
00:02:15,110 --> 00:02:19,390
împotriva selecție fel împotriva unui alt
că am numit merge sort la momentul respectiv,

46
00:02:19,390 --> 00:02:22,120
și propunem o durează
Beneficiază de o lecție de la săptămână

47
00:02:22,120 --> 00:02:24,060
la zero, divide și cuceri.

48
00:02:24,060 --> 00:02:28,810
Și atingerea într-un fel un fel de
logaritmică timp de funcționare în cele din urmă,

49
00:02:28,810 --> 00:02:31,024
în loc de ceva
asta e pur pătratică.

50
00:02:31,024 --> 00:02:33,440
Și nu e destul de logaritmică,
e un pic mai mult decât atât.

51
00:02:33,440 --> 00:02:36,520
Dar dacă vă amintiți de la clasă,
a fost mult, mult mai repede.

52
00:02:36,520 --> 00:02:38,210
Să aruncăm o privire la unde am rămas.

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

54
00:02:41,880 --> 00:02:45,370
>> Bubble sort versus selecție
fel versus merge sort.

55
00:02:45,370 --> 00:02:47,700
Acum toate acestea sunt difuzate, în
teorie, în același timp.

56
00:02:47,700 --> 00:02:50,510
Procesorul rulează la aceeași viteză.

57
00:02:50,510 --> 00:02:54,990
Dar puteti simti cat de plictisitor această
este foarte repede va deveni,

58
00:02:54,990 --> 00:02:58,790
și cât de repede, atunci când ne-am injecta
un pic de algoritmi săptămâni la zero, a

59
00:02:58,790 --> 00:03:00,080
putem accelera lucrurile.

60
00:03:00,080 --> 00:03:01,630
>> Deci, un fel marcă arată uimitor.

61
00:03:01,630 --> 00:03:05,220
Cum putem parghie, pentru
Pentru a sorta numerele mai rapid.

62
00:03:05,220 --> 00:03:07,140
Ei bine, sa ne gandim din nou
la un ingredient pe care le

63
00:03:07,140 --> 00:03:10,380
a avut din nou în săptămâna de zero, ca de
căutarea cineva într-o carte de telefon,

64
00:03:10,380 --> 00:03:12,380
și reamintească faptul că
pseudocod că ne-am propus,

65
00:03:12,380 --> 00:03:14,560
prin care putem găsi
cineva ca Mike Smith,

66
00:03:14,560 --> 00:03:16,310
uitat un pic ceva de genul asta.

67
00:03:16,310 --> 00:03:20,820
>> Acum, ia o privire, în special,
la linia 7 și 8, precum și 10 și 11,

68
00:03:20,820 --> 00:03:25,240
care induc că bucla, prin care ne-am păstrat
merge înapoi la linia 3 din nou, și din nou,

69
00:03:25,240 --> 00:03:26,520
și din nou.

70
00:03:26,520 --> 00:03:31,790
Dar se pare că putem vedea
acest algoritm, aici, în pseudocod,

71
00:03:31,790 --> 00:03:33,620
un pic mai mult holistic.

72
00:03:33,620 --> 00:03:35,960
De fapt, ceea ce caut
la aici pe ecran,

73
00:03:35,960 --> 00:03:41,180
este un algoritm pentru căutarea
Mike Smith printre unele set de pagini.

74
00:03:41,180 --> 00:03:45,520
Și într-adevăr, am putea simplifica acest
algoritm în acele linii 7 și 8,

75
00:03:45,520 --> 00:03:49,860
și 10 și 11 să spun doar acest lucru,
care am prezentat aici, în galben.

76
00:03:49,860 --> 00:03:52,210
Cu alte cuvinte, dacă Mike
Smith este mai devreme în carte,

77
00:03:52,210 --> 00:03:55,004
nu avem nevoie să specificați pas
cu pas acum cum sa-l găsesc.

78
00:03:55,004 --> 00:03:56,920
Noi nu trebuie să specificați
pentru a reveni la linia 3,

79
00:03:56,920 --> 00:03:58,960
de ce nu ne-am în schimb,
să zicem, mai general,

80
00:03:58,960 --> 00:04:01,500
caută Mike în
jumătate din stânga a cărții.

81
00:04:01,500 --> 00:04:03,960
>> În schimb, în ​​cazul în care Mike este
de fapt, mai târziu în carte,

82
00:04:03,960 --> 00:04:07,540
de ce nu ne-am cita doar de căutare încheiat citatul
pentru Mike în jumătatea din dreapta a cărții.

83
00:04:07,540 --> 00:04:11,030
Cu alte cuvinte, de ce nu ne-am
un fel de a ne spune punt,

84
00:04:11,030 --> 00:04:13,130
căuta Mike în acest
subset de carte,

85
00:04:13,130 --> 00:04:16,279
și lăsați-l să existent nostru
algoritm pentru a ne spune

86
00:04:16,279 --> 00:04:18,750
cum pentru a căuta Mike în
că jumătate din stânga a cărții.

87
00:04:18,750 --> 00:04:20,750
Cu alte cuvinte, ne
Algoritmul funcționează dacă este

88
00:04:20,750 --> 00:04:24,670
o carte de telefon a acestui grosime, de această
grosime, sau orice fel de grosime.

89
00:04:24,670 --> 00:04:27,826
Deci, putem recursiv
defini acest algoritm.

90
00:04:27,826 --> 00:04:29,950
Cu alte cuvinte, pe
ecran aici, este un algoritm

91
00:04:29,950 --> 00:04:33,130
pentru căutarea Mike Smith
printre paginile unei cărți de telefon.

92
00:04:33,130 --> 00:04:37,410
Deci, în conformitate 7 și 10, să
doar spun exact asta.

93
00:04:37,410 --> 00:04:40,250
Și am folosi acest termen un moment
Acum, și într-adevăr, recursivitate

94
00:04:40,250 --> 00:04:42,450
este buzzword pentru acum,
și este acest proces

95
00:04:42,450 --> 00:04:47,210
de a face ceva ciclice de cumva
folosind codul pe care le au deja,

96
00:04:47,210 --> 00:04:49,722
și de asteptare din nou,
și din nou, și din nou.

97
00:04:49,722 --> 00:04:51,930
Acum va fi important
pe care le într-un fel de jos

98
00:04:51,930 --> 00:04:53,821
afară, și nu face asta infinit de mult.

99
00:04:53,821 --> 00:04:56,070
În caz contrar, vom
au într-adevăr o buclă infinită.

100
00:04:56,070 --> 00:04:59,810
Dar să vedem dacă putem împrumuta această idee
de o recursivitate, a face ceva nou

101
00:04:59,810 --> 00:05:03,600
și din nou și din nou, pentru a rezolva
problema de sortare prin îmbinare

102
00:05:03,600 --> 00:05:05,900
sort, cu atât mai eficient.

103
00:05:05,900 --> 00:05:06,970
>> Deci, eu vă dau merge sort.

104
00:05:06,970 --> 00:05:07,920
Hai să aruncăm o privire.

105
00:05:07,920 --> 00:05:10,850
Deci, aici este pseudocod, cu
pe care am putea pune în aplicare de sortare,

106
00:05:10,850 --> 00:05:12,640
folosind acest algoritm numit merge sort.

107
00:05:12,640 --> 00:05:13,880
Și e destul de simplu acest lucru.

108
00:05:13,880 --> 00:05:15,940
Pe de intrare a n elemente,
Cu alte cuvinte, dacă sunteți

109
00:05:15,940 --> 00:05:18,830
dat n elemente și numerele și
litere sau indiferent de intrare este,

110
00:05:18,830 --> 00:05:22,430
dacă ți se dă elemente n, dacă
n este mai mic de 2, doar reveni.

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

112
00:05:22,930 --> 00:05:26,430
Pentru că dacă n este mai mic decât 2, care
înseamnă că lista mea de elemente

113
00:05:26,430 --> 00:05:30,446
este fie de dimensiuni 0 sau 1, și
în ambele aceste cazuri triviale,

114
00:05:30,446 --> 00:05:31,570
lista este deja sortate.

115
00:05:31,570 --> 00:05:32,810
Dacă nu există nici o listă, este sortate.

116
00:05:32,810 --> 00:05:35,185
Și dacă există o listă de lungime
1, este evident sortate.

117
00:05:35,185 --> 00:05:38,280
Deci algoritmul are nevoie doar să
într-adevăr ceva interesant,

118
00:05:38,280 --> 00:05:40,870
dacă avem două sau mai multe
elemente ne-a dat.

119
00:05:40,870 --> 00:05:42,440
Deci, să ne uităm la magia atunci.

120
00:05:42,440 --> 00:05:47,500
Sorta altceva jumătatea stângă a elementelor,
apoi sorta jumătatea dreaptă de elemente,

121
00:05:47,500 --> 00:05:49,640
apoi merge jumătățile sortate.

122
00:05:49,640 --> 00:05:52,440
Si ceea ce este un fel de spirit îndoire
aici, este că nu prea

123
00:05:52,440 --> 00:05:56,190
par să ți-am spus
nimic încă, nu?

124
00:05:56,190 --> 00:05:59,560
Tot ce am spus este, având în vedere o listă de
n elemente, sorta jumătatea stângă,

125
00:05:59,560 --> 00:06:01,800
apoi jumătatea din dreapta, apoi
fuziona jumatati sortate,

126
00:06:01,800 --> 00:06:03,840
dar în cazul în care este sos de secrete real?

127
00:06:03,840 --> 00:06:05,260
În cazul în care este algoritmul?

128
00:06:05,260 --> 00:06:09,150
Ei bine, se pare că cele două linii
în primul rând, jumătate fel stânga de elemente,

129
00:06:09,150 --> 00:06:13,970
și un fel dreptul de jumătate din elemente,
apeluri recursive, ca să spunem așa.

130
00:06:13,970 --> 00:06:16,120
>> La urma urmei, la acest
moment, nu am

131
00:06:16,120 --> 00:06:18,950
un algoritm cu care sa
sorta o grămadă de elemente?

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

133
00:06:19,450 --> 00:06:20,620
E chiar aici.

134
00:06:20,620 --> 00:06:25,180
E chiar aici pe ecran, și
așa că am putea folosi același set de pași

135
00:06:25,180 --> 00:06:28,500
pentru a sorta jumătatea stângă,
ca pot jumătatea din dreapta.

136
00:06:28,500 --> 00:06:30,420
Și într-adevăr, din nou, și din nou.

137
00:06:30,420 --> 00:06:34,210
Deci, într-un fel sau altul, și vom curând
vezi aceasta, magia de îmbinare fel

138
00:06:34,210 --> 00:06:37,967
este încorporat în acea finală
line, care fuzionează jumătățile sortate.

139
00:06:37,967 --> 00:06:39,300
Și asta pare destul de intuitiv.

140
00:06:39,300 --> 00:06:41,050
Iei două jumătăți, și tu,
într-un fel, merge împreună,

141
00:06:41,050 --> 00:06:43,260
si vom vedea acest lucru
concret într-o clipă.

142
00:06:43,260 --> 00:06:45,080
>> Dar acest lucru este un algoritm complet.

143
00:06:45,080 --> 00:06:46,640
Și să vedem exact de ce.

144
00:06:46,640 --> 00:06:50,912
Ei bine, să presupunem că suntem dat aceste aceeași
opt elemente aici pe ecran, una

145
00:06:50,912 --> 00:06:53,120
prin opt, dar sunt
în ordine aleatorie aparent.

146
00:06:53,120 --> 00:06:55,320
Și obiectivul la îndemână este
pentru a sorta aceste elemente.

147
00:06:55,320 --> 00:06:58,280
Ei bine, cum pot merge despre
face asta folosind, din nou,

148
00:06:58,280 --> 00:07:00,407
merge sort, ca pe acest pseudocod?

149
00:07:00,407 --> 00:07:02,740
Și din nou, fixa acest lucru în
mintea ta, doar pentru o clipă.

150
00:07:02,740 --> 00:07:05,270
Primul caz este destul de
banal, dacă e mai mică de 2,

151
00:07:05,270 --> 00:07:07,060
doar întoarce, nu e nici o lucrare de făcut.

152
00:07:07,060 --> 00:07:09,290
Deci, într-adevăr există doar trei
măsuri pentru a păstra într-adevăr în minte.

153
00:07:09,290 --> 00:07:11,081
Din nou, și din nou, eu sunt
va doresc să aibă

154
00:07:11,081 --> 00:07:13,980
pentru a sorta jumătatea stângă,
sorta jumătatea din dreapta,

155
00:07:13,980 --> 00:07:15,890
și apoi o dată lor
două jumătăți sunt sortate,

156
00:07:15,890 --> 00:07:18,710
Vreau să le fuzioneze împreună
într-o singură listă sortată.

157
00:07:18,710 --> 00:07:19,940
Astfel încât să păstreze în minte.

158
00:07:19,940 --> 00:07:21,310
>> Deci, aici e lista inițială.

159
00:07:21,310 --> 00:07:23,510
Să tratăm acest lucru ca pe un
matrice, așa cum am început să

160
00:07:23,510 --> 00:07:25,800
în săptămâna doua, care este o
bloc contiguu de memorie.

161
00:07:25,800 --> 00:07:28,480
In acest caz, conținând de opt
numere, spate în spate în spate.

162
00:07:28,480 --> 00:07:30,700
Și să aplice acum merge sort.

163
00:07:30,700 --> 00:07:33,300
Deci, vreau mai întâi pentru a sorta
jumătatea stângă a acestei liste,

164
00:07:33,300 --> 00:07:37,370
și să, prin urmare,
se concentreze pe 4, 8, 6, și 2.

165
00:07:37,370 --> 00:07:41,000
>> Acum, cum pot să merg despre
sortare o listă de dimensiuni 4?

166
00:07:41,000 --> 00:07:45,990
Ei bine, am să ia în considerare acum
sortare în stânga jumătatea stângă.

167
00:07:45,990 --> 00:07:47,720
Din nou, să înapoi pentru un moment.

168
00:07:47,720 --> 00:07:51,010
Dacă Pseudocodul este aceasta,
și am dat opt ​​elemente,

169
00:07:51,010 --> 00:07:53,230
8 este evident mai mare
mare sau egal cu 2.

170
00:07:53,230 --> 00:07:54,980
Deci, cu primul caz nu se aplică.

171
00:07:54,980 --> 00:07:58,120
Deci, pentru a sorta opt elemente, am mai întâi
sorta jumătatea stângă de elemente,

172
00:07:58,120 --> 00:08:01,930
apoi m-am sorta jumătatea dreaptă, apoi m-am merge
cele două jumătăți sortate, fiecare dintre dimensiuni 4.

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

174
00:08:02,470 --> 00:08:07,480
>> Dar dacă ați mi-a spus, sorta
jumătate din stânga, care este acum de mărime 4,

175
00:08:07,480 --> 00:08:09,350
cum pot sorta jumătatea stângă?

176
00:08:09,350 --> 00:08:11,430
Ei bine, dacă am un
intrare din patru elemente,

177
00:08:11,430 --> 00:08:14,590
Am sorta primul din stânga
doi, apoi la dreapta cei doi,

178
00:08:14,590 --> 00:08:16,210
și apoi le merge împreună.

179
00:08:16,210 --> 00:08:18,700
Deci, din nou, acesta devine un pic
de o minte îndoire joc aici,

180
00:08:18,700 --> 00:08:21,450
pentru că, un fel de, trebuie să
amintiți-vă unde vă aflați în poveste,

181
00:08:21,450 --> 00:08:23,620
dar la sfârșitul zilei,
dat orice număr de elemente,

182
00:08:23,620 --> 00:08:25,620
vrei mai întâi să sorta
jumătate din stânga, apoi jumătatea din dreapta,

183
00:08:25,620 --> 00:08:26,661
apoi merge le împreună.

184
00:08:26,661 --> 00:08:28,630
Să începem să facă exact acest lucru.

185
00:08:28,630 --> 00:08:30,170
Aici e intrarea opt elemente.

186
00:08:30,170 --> 00:08:31,910
Acum ne uităm la jumătatea stângă aici.

187
00:08:31,910 --> 00:08:33,720
Cum pot sorta patru elemente?

188
00:08:33,720 --> 00:08:35,610
Ei bine, am sorta prima jumătatea stângă.

189
00:08:35,610 --> 00:08:37,720
Acum, cum pot sorta jumătatea stângă?

190
00:08:37,720 --> 00:08:39,419
Ei bine, eu am dat două elemente.

191
00:08:39,419 --> 00:08:41,240
Deci, haideți să sorteze aceste două elemente.

192
00:08:41,240 --> 00:08:44,540
2 este mai mare decât sau
egal cu 2, desigur.

193
00:08:44,540 --> 00:08:46,170
Așa că primul caz nu se aplică.

194
00:08:46,170 --> 00:08:49,010
>> Așa că am acum pentru a sorta stânga
jumătate din aceste două elemente.

195
00:08:49,010 --> 00:08:50,870
Jumătatea stângă, desigur, este la doar 4.

196
00:08:50,870 --> 00:08:54,020
Deci, cum am sorta o listă de un element?

197
00:08:54,020 --> 00:08:57,960
Ei bine, acum, acest caz de bază special
până sus, ca să spunem așa, se aplică.

198
00:08:57,960 --> 00:09:01,470
1 este mai mică de 2, și mi
Lista este într-adevăr de dimensiuni 1.

199
00:09:01,470 --> 00:09:02,747
Așa că mă întorc.

200
00:09:02,747 --> 00:09:03,580
Eu nu fac nimic.

201
00:09:03,580 --> 00:09:06,770
Și într-adevăr, uita-te la ceea ce am
făcut, 4 este deja sortate.

202
00:09:06,770 --> 00:09:09,220
Ca eu sunt deja
parțial de succes aici.

203
00:09:09,220 --> 00:09:11,750
>> Acum, care pare un fel de prost
a pretinde, dar este adevărat.

204
00:09:11,750 --> 00:09:13,700
4 este o listă de dimensiuni 1.

205
00:09:13,700 --> 00:09:15,090
E deja sortate.

206
00:09:15,090 --> 00:09:16,270
Asta e jumătatea stângă.

207
00:09:16,270 --> 00:09:18,010
Acum am sorta jumătatea din dreapta.

208
00:09:18,010 --> 00:09:22,310
Intrare mea este un element, 8
În mod similar, sortate deja.

209
00:09:22,310 --> 00:09:25,170
Prost, de asemenea, dar, din nou,
acest principiu de bază

210
00:09:25,170 --> 00:09:28,310
este de gând să ne permite să construim acum
pe partea de sus a acestui succes.

211
00:09:28,310 --> 00:09:32,260
4 sortate, 8 este sortată, acum
ceea ce a fost ultimul pas?

212
00:09:32,260 --> 00:09:35,330
Deci a treia și ultima etapă, orice
timp ce te sortare o listă, rechemare,

213
00:09:35,330 --> 00:09:38,310
a fost de a fuziona cele două jumătăți,
stânga și dreapta.

214
00:09:38,310 --> 00:09:39,900
Deci, haideți să facă exact acest lucru.

215
00:09:39,900 --> 00:09:41,940
Jumătate meu stâng este, desigur, 4.

216
00:09:41,940 --> 00:09:43,310
Jumătate meu drept este de 8.

217
00:09:43,310 --> 00:09:44,100
>> Deci, hai sa facem acest lucru.

218
00:09:44,100 --> 00:09:46,410
În primul rând am de gând să aloce
unele memorie suplimentară,

219
00:09:46,410 --> 00:09:48,680
ca voi reprezenta aici,
ca doar o gamă secundar,

220
00:09:48,680 --> 00:09:49,660
care este destul de mare pentru a se potrivi acest lucru.

221
00:09:49,660 --> 00:09:52,243
Dar vă puteți imagina de extindere
că dreptunghi întreaga lungime,

222
00:09:52,243 --> 00:09:53,290
dacă avem nevoie de mai mult mai târziu.

223
00:09:53,290 --> 00:09:58,440
Cum fac 4 și 8, și îmbinarea
cele două liste de mărime 1 împreună?

224
00:09:58,440 --> 00:10:00,270
Aici, de asemenea, destul de simplu.

225
00:10:00,270 --> 00:10:03,300
4 este pe primul loc, apoi vine 8.

226
00:10:03,300 --> 00:10:07,130
Pentru că dacă vreau să sorta
jumătate din stânga, apoi jumătatea din dreapta,

227
00:10:07,130 --> 00:10:09,900
și apoi merge cele două jumătăți
împreună, în ordine sortate,

228
00:10:09,900 --> 00:10:11,940
4 este pe primul loc, apoi vine 8.

229
00:10:11,940 --> 00:10:15,810
>> Deci, se pare că face progrese, chiar
deși nu am făcut nici o lucrare actuale.

230
00:10:15,810 --> 00:10:17,800
Dar amintiți-vă unde suntem în poveste.

231
00:10:17,800 --> 00:10:19,360
Am luat inițial opt elemente.

232
00:10:19,360 --> 00:10:21,480
Am sortat jumătatea stângă, care este de 4.

233
00:10:21,480 --> 00:10:24,450
Apoi ne-am sortat jumătatea stângă
din jumătatea stângă, care era 2.

234
00:10:24,450 --> 00:10:25,270
Și aici vom merge.

235
00:10:25,270 --> 00:10:26,920
Am terminat cu acest pas.

236
00:10:26,920 --> 00:10:29,930
>> Deci, dacă am sortează
stânga jumătate de 2, acum ne-am

237
00:10:29,930 --> 00:10:32,130
au pentru a sorta jumătatea dreaptă a 2.

238
00:10:32,130 --> 00:10:35,710
Deci jumătatea dreaptă a 2 este
aceste două valori de aici, 6 și 2.

239
00:10:35,710 --> 00:10:40,620
Așa că haideți să luăm acum o intrare de dimensiune
2, și sortați jumătatea stângă, și apoi

240
00:10:40,620 --> 00:10:42,610
jumătatea dreaptă, și apoi
le merge împreună.

241
00:10:42,610 --> 00:10:45,722
Ei bine, cum a face I a sorta o listă de dimensiuni
1, care conține doar numărul 6?

242
00:10:45,722 --> 00:10:46,430
Am făcut deja.

243
00:10:46,430 --> 00:10:48,680
Este sortata Această listă de dimensiuni 1.

244
00:10:48,680 --> 00:10:52,140
>> Cum pot sorta o altă listă de
Dimensiunea 1, așa-numitul jumătatea din dreapta.

245
00:10:52,140 --> 00:10:54,690
Ei bine,, de asemenea, este deja sortate.

246
00:10:54,690 --> 00:10:56,190
Numărul 2 este singur.

247
00:10:56,190 --> 00:11:00,160
Deci, acum am două jumătăți, la stânga și la
Bine, am nevoie pentru a le îmbina împreună.

248
00:11:00,160 --> 00:11:01,800
Permiteți-mi să mă dau un spațiu suplimentar.

249
00:11:01,800 --> 00:11:05,580
Și a pus acolo 2,
apoi 6 acolo, astfel

250
00:11:05,580 --> 00:11:10,740
sortare această listă, stânga și la dreapta,
și fuzionează împreună, în cele din urmă.

251
00:11:10,740 --> 00:11:12,160
Așa că eu sunt într-o formă puțin mai bună.

252
00:11:12,160 --> 00:11:16,250
Nu am terminat, pentru că în mod clar 4, 8, 2,
6 nu este ordinea finală pe care vreau.

253
00:11:16,250 --> 00:11:20,640
Dar am acum două liste de dimensiuni 2, care
ambele au, respectiv, a fost sortate.

254
00:11:20,640 --> 00:11:24,580
Deci, acum, dacă vă înapoi în mintea ta
ochi, în cazul în care au ca ne lase?

255
00:11:24,580 --> 00:11:28,520
Am început cu opt elemente, apoi m-am
diminuate în jos la jumătatea stângă a 4,

256
00:11:28,520 --> 00:11:31,386
apoi jumătatea stângă a 2, și
apoi jumătatea dreaptă a 2,

257
00:11:31,386 --> 00:11:34,510
Am terminat, prin urmare, sortare stânga
jumătate din 2, și jumătatea dreaptă a 2,

258
00:11:34,510 --> 00:11:37,800
Deci, ce este de-a treia și ultima etapă de aici?

259
00:11:37,800 --> 00:11:41,290
Trebuie să fuzioneze împreună
două liste de dimensiuni 2.

260
00:11:41,290 --> 00:11:42,040
Așa că hai să mergem mai departe.

261
00:11:42,040 --> 00:11:43,940
Și pe ecran aici, da
mi ceva memorie suplimentară,

262
00:11:43,940 --> 00:11:47,170
deși punct de vedere tehnic, observați că Am
a primit o grămadă de spațiu până gol top

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

264
00:11:47,670 --> 00:11:50,044
Dacă vreau să fie deosebit de
spațiu eficient înțelept,

265
00:11:50,044 --> 00:11:52,960
Am putea începe doar în mișcare elementele
înainte și înapoi, sus și de jos.

266
00:11:52,960 --> 00:11:55,460
Dar doar pentru claritate vizuală,
Am de gând să-l pună jos,

267
00:11:55,460 --> 00:11:56,800
pentru a menține lucrurile frumos si curat.

268
00:11:56,800 --> 00:11:58,150
>> Așa că am două liste de dimensiuni 2.

269
00:11:58,150 --> 00:11:59,770
Prima listă are 4 și 8.

270
00:11:59,770 --> 00:12:01,500
A doua listă are 2 și 6.

271
00:12:01,500 --> 00:12:03,950
Să fuziona cele
împreună pentru sortat.

272
00:12:03,950 --> 00:12:09,910
2, desigur, este pe primul loc,
apoi 4, apoi 6, apoi 8.

273
00:12:09,910 --> 00:12:12,560
Și acum se pare a fi mai
undeva interesant.

274
00:12:12,560 --> 00:12:15,720
Jumătate acum am extrase din
lista, și coincidență, e

275
00:12:15,720 --> 00:12:18,650
toate numerele pare, dar asta
este, într-adevăr, doar o coincidență.

276
00:12:18,650 --> 00:12:22,220
Și eu acum am sortat stânga
jumătate, astfel încât este 2, 4, 6, 8 și.

277
00:12:22,220 --> 00:12:23,430
Nimic nu e în ordine.

278
00:12:23,430 --> 00:12:24,620
Care se simte ca un progres.

279
00:12:24,620 --> 00:12:26,650
>> Acum se simte ca am
vorbit pentru totdeauna acum,

280
00:12:26,650 --> 00:12:29,850
astfel încât ceea ce rămâne de văzut dacă această
Algoritmul este, într-adevăr, mult mai eficient.

281
00:12:29,850 --> 00:12:31,766
Dar vom prin
o super-metodic.

282
00:12:31,766 --> 00:12:34,060
Un computer, desigur,
ar face așa.

283
00:12:34,060 --> 00:12:34,840
Deci, unde suntem?

284
00:12:34,840 --> 00:12:36,180
Am început cu opt elemente.

285
00:12:36,180 --> 00:12:37,840
Am sortat jumătatea stângă a 4.

286
00:12:37,840 --> 00:12:39,290
Am par a fi terminat cu asta.

287
00:12:39,290 --> 00:12:42,535
Deci, acum următorul pas este de a
sorta jumătatea dreaptă a 4.

288
00:12:42,535 --> 00:12:44,410
Și această parte putem merge
printr-un pic mai mult

289
00:12:44,410 --> 00:12:47,140
repede, deși ești
Bine ați venit pentru a derula sau a întrerupe, doar

290
00:12:47,140 --> 00:12:49,910
cred prin ea la
propriul ritm, dar ceea ce

291
00:12:49,910 --> 00:12:53,290
avem acum este o oportunitate de a
face același algoritm exact pe patru

292
00:12:53,290 --> 00:12:54,380
numere diferite.

293
00:12:54,380 --> 00:12:57,740
>> Deci, să mergem mai departe, și să se concentreze asupra
jumătatea dreaptă, care suntem aici.

294
00:12:57,740 --> 00:13:01,260
Jumătatea stângă a care
jumătate dreapta, iar acum

295
00:13:01,260 --> 00:13:04,560
jumătatea stângă a stânga
jumătate din care jumătate drept,

296
00:13:04,560 --> 00:13:08,030
și cum pot sorta o listă de dimensiuni
1 conține doar numărul 1?

297
00:13:08,030 --> 00:13:09,030
E deja făcut.

298
00:13:09,030 --> 00:13:11,830
Cum pot face același lucru pentru o listă
de dimensiuni 1 conține doar 7?

299
00:13:11,830 --> 00:13:12,840
E deja făcut.

300
00:13:12,840 --> 00:13:16,790
Pasul trei pentru această jumătate, apoi
este să fuzioneze aceste două elemente

301
00:13:16,790 --> 00:13:20,889
într-o nouă listă de dimensiuni 2, 1 și 7.

302
00:13:20,889 --> 00:13:23,180
Nu par să fi făcut toate
că de mult de lucru interesant.

303
00:13:23,180 --> 00:13:24,346
Să vedem ce se întâmplă în continuare.

304
00:13:24,346 --> 00:13:29,210
Am sortat doar jumătatea stângă a
jumătatea dreaptă a de intrare meu original.

305
00:13:29,210 --> 00:13:32,360
Acum, haideți să sorteze dreapta
jumătate, care conține 5 și 3.

306
00:13:32,360 --> 00:13:35,740
Să ne uităm la nou stânga
jumătate, sortate, pe jumătate dreptate, sortate,

307
00:13:35,740 --> 00:13:39,120
și îmbinarea celor două împreună,
în unele spațiu suplimentar,

308
00:13:39,120 --> 00:13:41,670
3 este pe primul loc, apoi vine 5.

309
00:13:41,670 --> 00:13:46,190
Și așa acum, ne-am sortează
jumătatea stângă a jumătatea din dreapta

310
00:13:46,190 --> 00:13:49,420
problemei originale, și
jumătatea dreaptă a jumătatea din dreapta

311
00:13:49,420 --> 00:13:50,800
a problemei inițiale.

312
00:13:50,800 --> 00:13:52,480
Care este a treia și ultima pas?

313
00:13:52,480 --> 00:13:54,854
Ei bine, să fuzioneze cele două jumătăți împreună.

314
00:13:54,854 --> 00:13:57,020
Deci lasă-mă să-mi iau niște
spațiu suplimentar, dar, din nou, am

315
00:13:57,020 --> 00:13:58,699
ar putea fi, folosind ca spatiul liber până sus.

316
00:13:58,699 --> 00:14:00,490
Dar vom continua să
simplu vizual.

317
00:14:00,490 --> 00:14:07,070
Lasă-mă să fuzioneze acum 1, și
apoi 3, apoi 5, apoi 7.

318
00:14:07,070 --> 00:14:10,740
Mă lăsând acum cu
jumătate din dreapta a problemei originale

319
00:14:10,740 --> 00:14:12,840
care este perfect sortate.

320
00:14:12,840 --> 00:14:13,662
>> Deci, ceea ce rămâne?

321
00:14:13,662 --> 00:14:16,120
Mă simt ca și cum aș ține spunând
aceleași lucruri din nou, și din nou,

322
00:14:16,120 --> 00:14:18,700
dar asta e de reflexie a
fapt pe care îl utilizăm recursivitate.

323
00:14:18,700 --> 00:14:21,050
Procesul de a folosi un
algoritm nou, și din nou,

324
00:14:21,050 --> 00:14:23,940
pe subseturi mai mici de
problema originală.

325
00:14:23,940 --> 00:14:27,580
Așa că acum am un stânga sortate
jumătate din problema originală.

326
00:14:27,580 --> 00:14:30,847
Am o jumătate de sortat drept
a problemei inițiale.

327
00:14:30,847 --> 00:14:32,180
Care este a treia și ultima etapă?

328
00:14:32,180 --> 00:14:33,590
Oh, e absorbit.

329
00:14:33,590 --> 00:14:34,480
Așa că hai să facem asta.

330
00:14:34,480 --> 00:14:36,420
Să aloce unele suplimentare
memorie, dar Dumnezeul meu, ne-am

331
00:14:36,420 --> 00:14:37,503
ar putea pune-l oriunde acum.

332
00:14:37,503 --> 00:14:40,356
Avem atât de mult spațiu disponibil
pentru noi, dar vom păstrați-l simplu.

333
00:14:40,356 --> 00:14:42,730
În loc de a merge înapoi și
mai departe cu memoria noastră originală,

334
00:14:42,730 --> 00:14:44,480
hai sa o facem
vizual aici de mai jos,

335
00:14:44,480 --> 00:14:47,240
pentru a termina fuzionarea
jumătate stânga și jumătatea din dreapta.

336
00:14:47,240 --> 00:14:49,279
>> Deci, prin fuziunea, ce trebuie să fac?

337
00:14:49,279 --> 00:14:50,820
Vreau sa iau elementele în ordine.

338
00:14:50,820 --> 00:14:53,230
Deci uita la jumătatea stângă,
Văd primul număr este 2.

339
00:14:53,230 --> 00:14:55,230
Mă uit la jumătatea din dreapta,
Văd primul număr

340
00:14:55,230 --> 00:14:58,290
este 1, deci evident care
Numărul vreau să smulge,

341
00:14:58,290 --> 00:15:00,430
și a pus pe primul loc în lista mea finală?

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

343
00:15:01,449 --> 00:15:02,990
Acum vreau să întreb aceeași întrebare.

344
00:15:02,990 --> 00:15:05,040
Pe jumătatea stângă, am
Încă mai am numărul 2.

345
00:15:05,040 --> 00:15:07,490
Pe jumătatea din dreapta,
Am numărul 3.

346
00:15:07,490 --> 00:15:08,930
Care unul vreau să aleg?

347
00:15:08,930 --> 00:15:11,760
Desigur, numărul 2 și
acum observa candidații

348
00:15:11,760 --> 00:15:13,620
sunt 4 pe stânga, 3 pe dreapta.

349
00:15:13,620 --> 00:15:15,020
Să, desigur, alege 3.

350
00:15:15,020 --> 00:15:18,020
Acum candidații sunt 4 pe
stânga, 5 la dreapta.

351
00:15:18,020 --> 00:15:19,460
Noi, desigur, pentru a alege 4.

352
00:15:19,460 --> 00:15:21,240
6 din stânga, 5 la dreapta.

353
00:15:21,240 --> 00:15:22,730
Noi, desigur, alege 5.

354
00:15:22,730 --> 00:15:25,020
6 din stânga, 7 pe dreapta.

355
00:15:25,020 --> 00:15:29,320
Am ales 6, și apoi ne
alege 7, iar apoi alegem 8.

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

357
00:15:30,100 --> 00:15:34,370
>> Deci, un număr foarte mare de cuvinte mai târziu, am
au sortat această listă de opt elemente

358
00:15:34,370 --> 00:15:38,450
într-o listă de una prin opt,
care este în creștere cu fiecare pas,

359
00:15:38,450 --> 00:15:40,850
dar cât de mult timp a făcut
ne lua pentru a face asta.

360
00:15:40,850 --> 00:15:43,190
Ei bine, în mod deliberat Am
lucrurile prevăzute pictural

361
00:15:43,190 --> 00:15:46,330
aici, astfel încât să putem fel de
vezi sau apreciati divizia

362
00:15:46,330 --> 00:15:49,060
în cucerire că sa întâmplat.

363
00:15:49,060 --> 00:15:52,830
>> Într-adevăr, dacă te uiți înapoi la urma,
Am lăsat toate aceste linii punctate

364
00:15:52,830 --> 00:15:55,660
în titularilor loc, puteți,
un fel de, a se vedea, în ordine inversă,

365
00:15:55,660 --> 00:15:58,800
dacă un fel de privi înapoi în
istorie acum, lista mea inițială

366
00:15:58,800 --> 00:16:00,250
este, desigur, de dimensiunea 8.

367
00:16:00,250 --> 00:16:03,480
Și apoi Anterior, am fost
a face cu doua liste de mărime 4,

368
00:16:03,480 --> 00:16:08,400
și apoi patru liste de dimensiuni 2,
și apoi opt liste de dimensiune 1.

369
00:16:08,400 --> 00:16:10,151
>> Deci, ce face acest lucru,
un fel de, vă reamintesc de?

370
00:16:10,151 --> 00:16:11,858
Ei bine, într-adevăr, oricare dintre
algoritmii care le-am

371
00:16:11,858 --> 00:16:14,430
sa uitat la până în prezent în cazul în care ne-am
divide, și divide, și divide,

372
00:16:14,430 --> 00:16:19,500
păstra cu lucrurile din nou, și
din nou, ca rezultat această idee generală.

373
00:16:19,500 --> 00:16:23,100
Și deci nu e ceva
logaritmică se întâmplă aici.

374
00:16:23,100 --> 00:16:26,790
Și nu e destul de jurnal de n, dar
există o componentă logaritmică

375
00:16:26,790 --> 00:16:28,280
a ceea ce tocmai am făcut.

376
00:16:28,280 --> 00:16:31,570
>> Acum, haideți să ia în considerare modul, care de fapt este.

377
00:16:31,570 --> 00:16:34,481
Deci, jurnal de n, din nou a fost
un timp de funcționare mare,

378
00:16:34,481 --> 00:16:36,980
când am făcut ceva de genul
căutare binară, așa cum am acum o numim,

379
00:16:36,980 --> 00:16:40,090
strategia divide și cuceri
prin care am găsit Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Punct de vedere tehnic acum.

381
00:16:41,020 --> 00:16:43,640
Asta e jurnal de bază 2 de n, chiar
deși în cele mai multe clase de matematica,

382
00:16:43,640 --> 00:16:45,770
10 este, de obicei de bază pe care le presupune.

383
00:16:45,770 --> 00:16:48,940
Dar oamenii de stiinta de calculator aproape întotdeauna
gândesc și vorbesc în termeni de bază 2,

384
00:16:48,940 --> 00:16:52,569
astfel, în general, spunem doar jurnal de
n, în loc de log in baza 2 a n,

385
00:16:52,569 --> 00:16:55,110
dar sunt exact unul și
aceeași în lumea de calculator

386
00:16:55,110 --> 00:16:57,234
știință, și, ca o paranteză,
există un factor constant

387
00:16:57,234 --> 00:17:01,070
diferență între cele două, așa că
pune în dezbatere oricum, din motive mai mult formale.

388
00:17:01,070 --> 00:17:04,520
>> Dar pentru acum, ceea ce ne pasă
despre este acest exemplu.

389
00:17:04,520 --> 00:17:08,520
Așa că haideți să nu se dovedesc de exemplu, dar la
puțin utiliza un exemplu de numere

390
00:17:08,520 --> 00:17:10,730
la îndemână ca o verificare bun-simț, dacă vreți.

391
00:17:10,730 --> 00:17:14,510
Deci anterior formula a fost de bază log
2 de n, dar ceea ce este n în acest caz.

392
00:17:14,510 --> 00:17:18,526
Am avut numerele n originale, sau 8
de numărul inițial specific.

393
00:17:18,526 --> 00:17:20,359
Acum că a fost un pic
în timp ce, dar eu sunt destul de

394
00:17:20,359 --> 00:17:25,300
sigur că log bază 2
din valoarea 8 este 3,

395
00:17:25,300 --> 00:17:29,630
și într-adevăr, ceea ce este frumos despre care este
că 3 este exact numărul de ori

396
00:17:29,630 --> 00:17:33,320
pe care le puteți împărți o listă
de nou, și din nou lungime 8,

397
00:17:33,320 --> 00:17:36,160
și din nou, până când rămâi
cu liste de mărime doar 1.

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

399
00:17:36,660 --> 00:17:40,790
8 merge la 4, se duce la 2,
merge la 1, și asta e

400
00:17:40,790 --> 00:17:43,470
reflecta exact acest lucru
imagine am avut în urmă cu doar un moment.

401
00:17:43,470 --> 00:17:47,160
Deci, un pic de bun-simț verifica de unde
logaritm este, de fapt implicat.

402
00:17:47,160 --> 00:17:50,180
>> Deci, acum, ce altceva este vorba aici? n.

403
00:17:50,180 --> 00:17:53,440
Deci observăm că fiecare
timp am împărțit lista,

404
00:17:53,440 --> 00:17:58,260
chiar dacă în ordine inversă în istorie
aici, am fost mai faci n lucruri.

405
00:17:58,260 --> 00:18:02,320
Acest pas fuzionează necesar ca
Ating fiecare dintre numerele,

406
00:18:02,320 --> 00:18:05,060
în scopul de a glisați-l în
locația sa corespunzătoare.

407
00:18:05,060 --> 00:18:10,760
Deci, chiar dacă înălțimea acestei
Diagrama este de mărime log n n sau 3,

408
00:18:10,760 --> 00:18:13,860
în mod specific, cu alte cuvinte,
Am făcut trei divizii aici.

409
00:18:13,860 --> 00:18:18,800
Cât de mult de lucru am făcut orizontal
de-a lungul această diagramă de fiecare dată?

410
00:18:18,800 --> 00:18:21,110
>> Ei bine, am făcut-o n trepte de
locul de muncă, pentru că dacă am

411
00:18:21,110 --> 00:18:24,080
Trebuie patru elemente și patru elemente,
și am nevoie pentru a le îmbina împreună.

412
00:18:24,080 --> 00:18:26,040
Am nevoie pentru a merge prin
aceste patru și aceste patru,

413
00:18:26,040 --> 00:18:28,123
în cele din urmă pentru a le îmbina
înapoi în opt elemente.

414
00:18:28,123 --> 00:18:32,182
Dacă dimpotrivă Am opt degete
aici, ceea ce nu face, și opt

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- Dacă am
Trebuie patru degete aici,

416
00:18:34,390 --> 00:18:37,380
care fac, de patru degete
aici, pe care o fac,

417
00:18:37,380 --> 00:18:40,590
atunci asta e la fel
exemplu ca și mai înainte, în cazul în care fac

418
00:18:40,590 --> 00:18:44,010
au opt degete deși, în
totală, pe care eu pot fel de, nu,.

419
00:18:44,010 --> 00:18:47,950
Eu pot face exact aici,
Atunci pot siguranță

420
00:18:47,950 --> 00:18:50,370
fuzioneze toate aceste liste
de dimensiune 1 împreună.

421
00:18:50,370 --> 00:18:54,050
Dar am avea cu siguranță să te uiți
la fiecare element de exact o dată.

422
00:18:54,050 --> 00:18:59,640
Deci înălțimea acestui proces este log n,
lățimea acestui proces, ca să spunem așa,

423
00:18:59,640 --> 00:19:02,490
este N, asa ca ceea ce am par
de a avea, în cele din urmă, este

424
00:19:02,490 --> 00:19:06,470
un timp de funcționare de mărime n ori log n.

425
00:19:06,470 --> 00:19:08,977
>> Cu alte cuvinte, ne-am impartit
lista, jurnalul de n ori,

426
00:19:08,977 --> 00:19:11,810
dar de fiecare dată am făcut asta, am avut
pentru a atinge fiecare dintre elementele

427
00:19:11,810 --> 00:19:13,560
în scopul de a le îmbina
toate împreună, care

428
00:19:13,560 --> 00:19:18,120
a fost n pas, așa că avem de n ori log n,
sau ca un om de stiinta de calculator ar spune,

429
00:19:18,120 --> 00:19:20,380
asimptotic, care
ar fi cuvântul mare

430
00:19:20,380 --> 00:19:22,810
pentru a descrie partea superioară
legat la un timp de funcționare,

431
00:19:22,810 --> 00:19:28,010
ne se execută într-o o mare
log n timp, ca să spunem așa.

432
00:19:28,010 --> 00:19:31,510
>> Acum, acest lucru este important, deoarece
amintesc care au fost ori de funcționare

433
00:19:31,510 --> 00:19:34,120
cu bule de sortare, și de selecție
sortare, și sortare prin inserție,

434
00:19:34,120 --> 00:19:38,200
și chiar un alte câteva care există,
n pătrat a fost în cazul în care am fost la.

435
00:19:38,200 --> 00:19:39,990
Și puteți, un fel de, a se vedea acest lucru aici.

436
00:19:39,990 --> 00:19:45,720
Dacă n pătrat este, evident, de n ori
n, dar aici avem de n ori log n,

437
00:19:45,720 --> 00:19:48,770
si stim deja de la săptămână
la zero, că log n, logaritmică,

438
00:19:48,770 --> 00:19:50,550
este mai bine decât ceva liniar.

439
00:19:50,550 --> 00:19:52,930
La urma urmei, amintesc imaginea
cu roșu și galben

440
00:19:52,930 --> 00:19:56,500
și liniile verzi pe care le scoteau,
line logaritmică verde a fost mult mai mic.

441
00:19:56,500 --> 00:20:00,920
Și, prin urmare, mult mai bine și mai repede
decât drepte linii galbene și roșii,

442
00:20:00,920 --> 00:20:05,900
de n ori log n este, într-adevăr, mai bine
decât de n ori n, sau n pătrat.

443
00:20:05,900 --> 00:20:09,110
>> Deci, se pare că avem
a identificat o îmbinare algoritm

444
00:20:09,110 --> 00:20:11,870
fel care se execută în mare
timp mai rapid, și într-adevăr,

445
00:20:11,870 --> 00:20:16,560
de aceea, la începutul acestei săptămâni, atunci când
am văzut că concurs între bule

446
00:20:16,560 --> 00:20:20,750
sortare, selectare fel, și îmbinarea
sort, merge sort foarte, foarte castigat.

447
00:20:20,750 --> 00:20:23,660
Și într-adevăr, ne-am nici măcar nu așteptați
pentru bule de sortare și selecție de sortare

448
00:20:23,660 --> 00:20:24,790
a termina.

449
00:20:24,790 --> 00:20:27,410
>> Acum să luăm un alt trecere
la această, la o puțin mai

450
00:20:27,410 --> 00:20:31,030
perspectivă formală, doar în
caz, acest rezonează mai bine

451
00:20:31,030 --> 00:20:33,380
decât că discuția nivel mai ridicat.

452
00:20:33,380 --> 00:20:34,880
Deci, aici e din nou algoritmul.

453
00:20:34,880 --> 00:20:36,770
Să ne întrebăm,
ce timpul de rulare

454
00:20:36,770 --> 00:20:39,287
este de acest algoritmi diferite etape?

455
00:20:39,287 --> 00:20:41,620
Să-l împartă în primul
caz și al doilea caz.

456
00:20:41,620 --> 00:20:46,280
IF și altcineva în cazul dacă,
Dacă N este mai mică de 2, doar reveni.

457
00:20:46,280 --> 00:20:47,580
Se simte ca constantă de timp.

458
00:20:47,580 --> 00:20:50,970
E, un fel de, cum ar fi două etape,
IF n este mai mic de 2, apoi să se întoarcă.

459
00:20:50,970 --> 00:20:54,580
Dar, așa cum am spus, luni,
constantă de timp, sau de mare o de 1,

460
00:20:54,580 --> 00:20:57,130
pot fi două etape, trei
pași, chiar 1.000 de trepte.

461
00:20:57,130 --> 00:20:59,870
Ceea ce contează este faptul că este
un număr constant de pași.

462
00:20:59,870 --> 00:21:03,240
Deci galben evidențiat pseudocod
aici se execută în, vom numi,

463
00:21:03,240 --> 00:21:04,490
constantă de timp.

464
00:21:04,490 --> 00:21:06,780
Deci mai formal, și
vom sa-- acest

465
00:21:06,780 --> 00:21:09,910
va fi măsura în care ne
formaliza acest drept now-- T de n,

466
00:21:09,910 --> 00:21:15,030
timpul de rulare a unei probleme
care ia n ceva de ca intrare,

467
00:21:15,030 --> 00:21:19,150
este egal cu mare o de unul,
IF n este mai mică de 2.

468
00:21:19,150 --> 00:21:20,640
Deci, este condiționată de asta.

469
00:21:20,640 --> 00:21:24,150
Deci, pentru a fi clar, dacă N este mai mică de
2, avem o listă foarte scurtă, apoi

470
00:21:24,150 --> 00:21:29,151
timpul de rulare, T de n, unde n este
1 sau 0, în acest caz foarte specific,

471
00:21:29,151 --> 00:21:30,650
este doar de gând să fie constantă de timp.

472
00:21:30,650 --> 00:21:32,691
Se va lua o
pas, doi pași, indiferent.

473
00:21:32,691 --> 00:21:33,950
Este un număr fix de pași.

474
00:21:33,950 --> 00:21:38,840
>> Deci partea suculent trebuie să fie cu siguranță în
alt caz în pseudocod.

475
00:21:38,840 --> 00:21:40,220
Cazul altceva.

476
00:21:40,220 --> 00:21:44,870
Un fel de jumătate din stânga de elemente, un fel dreptul
jumătate din elemente, îmbinare jumătăți sortate.

477
00:21:44,870 --> 00:21:46,800
Cât timp durează fiecare dintre aceste etape să ia?

478
00:21:46,800 --> 00:21:49,780
Ei bine, în cazul în care derularea
timp pentru a sorta n elemente

479
00:21:49,780 --> 00:21:53,010
este, să-i zicem foarte
generic, T de n,

480
00:21:53,010 --> 00:21:55,500
apoi de sortare stânga
jumătate din elementele

481
00:21:55,500 --> 00:21:59,720
este, un fel de, cum ar fi zis:
T de n împărțit la 2,

482
00:21:59,720 --> 00:22:03,000
și sortarea în mod similar jumătatea din dreapta
de elemente este, un fel de, cum ar fi zis:

483
00:22:03,000 --> 00:22:06,974
T de n divizat 2, și apoi
fuzionarea jumatati sortate.

484
00:22:06,974 --> 00:22:08,890
Ei bine, dacă am niște
Numărul de elemente aici,

485
00:22:08,890 --> 00:22:11,230
cum ar fi patru, iar unele numărul
de elemente aici, cum ar fi patru,

486
00:22:11,230 --> 00:22:14,650
și am să fuzioneze fiecare dintre aceste patru
în, și fiecare dintre aceste patru în, unul

487
00:22:14,650 --> 00:22:17,160
după altul, astfel încât
în cele din urmă am opt elemente.

488
00:22:17,160 --> 00:22:20,230
Se simte ca e mare o de n pași?

489
00:22:20,230 --> 00:22:23,500
Dacă am n degete și fiecare dintre
ei are să fie integrate în loc,

490
00:22:23,500 --> 00:22:25,270
asta e ca un alt n pași.

491
00:22:25,270 --> 00:22:27,360
>> Deci, într-adevăr formulaically,
putem exprima acest lucru,

492
00:22:27,360 --> 00:22:29,960
deși un pic scarily la prima
vedere, dar este ceva

493
00:22:29,960 --> 00:22:31,600
care surprinde exact această logică.

494
00:22:31,600 --> 00:22:35,710
Timpul de funcționare, T de n, n IF
este mai mare sau egal cu 2.

495
00:22:35,710 --> 00:22:42,500
În acest caz, cazul altceva, este T de n
împărțit la 2, plus T de n împărțit la 2,

496
00:22:42,500 --> 00:22:45,320
mare plus o de n, unele
Numărul liniar de etape,

497
00:22:45,320 --> 00:22:51,630
, poate exact n, poate de 2 ori
n, dar e aproximativ, ordinea n.

498
00:22:51,630 --> 00:22:54,060
Așa că, de asemenea, este modul în care putem
exprima acest formulaically.

499
00:22:54,060 --> 00:22:56,809
Acum, tu nu ar ști acest lucru, cu excepția cazului
l-ai înregistrat în mintea ta,

500
00:22:56,809 --> 00:22:58,710
sau căutați-l în sus în
din spate a unui manual, care

501
00:22:58,710 --> 00:23:00,501
ar putea avea un pic de
trișeze foaie la sfârșitul anului,

502
00:23:00,501 --> 00:23:03,940
dar acest lucru este, într-adevăr, o să
să ne dea o mare o de n log n,

503
00:23:03,940 --> 00:23:06,620
deoarece recurența care
vedeți aici, pe ecran,

504
00:23:06,620 --> 00:23:09,550
dacă tu de fapt făcut-o, cu
un număr infinit de exemple,

505
00:23:09,550 --> 00:23:13,000
sau ai făcut formulaically, ar trebui să
vedea că acest lucru, pentru că această formulă

506
00:23:13,000 --> 00:23:17,100
în sine este recursiv, cu t
n peste ceva pe dreapta,

507
00:23:17,100 --> 00:23:21,680
și T de n pe stânga, acest lucru poate
de fapt este exprimată, în cele din urmă,

508
00:23:21,680 --> 00:23:24,339
la fel de mare du-te de n log n.

509
00:23:24,339 --> 00:23:26,130
Dacă nu convins, asta e
amendă pentru acum, doar

510
00:23:26,130 --> 00:23:28,960
ia pe credință, că e, într-adevăr,
ce care duce la reapariția,

511
00:23:28,960 --> 00:23:31,780
dar acest lucru este doar un pic mai mult de un
Abordarea matematică să caute

512
00:23:31,780 --> 00:23:36,520
la momentul de funcționare a merge fel
pe baza pseudocod sa numai.

513
00:23:36,520 --> 00:23:39,030
>> Acum, haideți să ia un pic de un
aerisire din toate astea,

514
00:23:39,030 --> 00:23:41,710
și să ia o privire la o
anumite fostul senator, care a

515
00:23:41,710 --> 00:23:44,260
s-ar putea uita-te un pic familiar,
care se așeză cu Eric Google

516
00:23:44,260 --> 00:23:48,410
Schmidt, ceva timp în urmă, pentru un interviu
pe scena, in fata o grămadă

517
00:23:48,410 --> 00:23:53,710
de oameni, vorbind în cele din urmă despre
un subiect, care e destul de acum familiar.

518
00:23:53,710 --> 00:23:54,575
Hai să aruncăm o privire.

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

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt,: Acum Senator,
esti aici, la Google,

521
00:24:03,890 --> 00:24:09,490
și îmi place să cred că a
președinție ca un interviu de angajare.

522
00:24:09,490 --> 00:24:11,712
Acum e greu pentru a obține un loc de muncă în calitate de președinte.

523
00:24:11,712 --> 00:24:12,670
Președintele Obama: dreapta.

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt, Și tu ești
de gând să faci [neauzit] acum.

525
00:24:13,940 --> 00:24:15,523
Este, de asemenea, greu pentru a obține un loc de muncă la Google.

526
00:24:15,523 --> 00:24:17,700
Președintele Obama: dreapta.

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt,: Avem întrebări,
si cerem candidaților întrebările noastre,

528
00:24:21,330 --> 00:24:24,310
iar acesta este de la Larry Schwimmer.

529
00:24:24,310 --> 00:24:25,890
>> Președintele Obama: OK.

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

531
00:24:27,005 --> 00:24:28,130
Credeți că glumesc?

532
00:24:28,130 --> 00:24:30,590
E chiar aici.

533
00:24:30,590 --> 00:24:33,490
Care este cel mai eficient mod de a
sorta un milion de 32 de biți numere întregi?

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

535
00:24:37,560 --> 00:24:38,979
>> Președintele Obama: Well--

536
00:24:38,979 --> 00:24:41,020
Eric Schmidt,: Uneori,
Poate Îmi pare rău, maybe--

537
00:24:41,020 --> 00:24:42,750
Președintele Obama: Nu, nu,
Nu, nu, nu, eu think--

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt,: Asta nu e it--

539
00:24:43,240 --> 00:24:45,430
Președintele Obama: I
cred, cred că bula

540
00:24:45,430 --> 00:24:46,875
fel ar fi calea greșită de a merge.

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

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

543
00:24:50,535 --> 00:24:52,200
Cine-i asta a spus?

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

545
00:24:54,020 --> 00:24:55,590
Nu am stiinta de calculator on--

546
00:24:55,590 --> 00:24:58,986
>> Președintele Obama: Avem
Trebuie spioni noastre acolo.

547
00:24:58,986 --> 00:24:59,860
PROFESORUL: Bine.

548
00:24:59,860 --> 00:25:03,370
Să lăsăm în urma noastră acum din
lume teoretică a algoritmilor

549
00:25:03,370 --> 00:25:06,520
în analiza asimptotică
acestora, și să se întoarcă la unele subiecte

550
00:25:06,520 --> 00:25:09,940
de la zero și săptămână, și start
pentru a elimina niște roți de formare,

551
00:25:09,940 --> 00:25:10,450
dacă vrei.

552
00:25:10,450 --> 00:25:13,241
Astfel încât să înțeleg cu adevărat
în cele din urmă de la sol în sus, ceea ce este

553
00:25:13,241 --> 00:25:16,805
întâmplă sub capotă, atunci când
scrie, compila, și să execute programe.

554
00:25:16,805 --> 00:25:19,680
Reamintim, în special, că aceasta a fost
primul program C ne-am uitat la,

555
00:25:19,680 --> 00:25:22,840
un program de canonic, simplu
de soiuri, relativ vorbind,

556
00:25:22,840 --> 00:25:24,620
care, se imprimă, Hello World.

557
00:25:24,620 --> 00:25:27,610
Și reamintească faptul că i-am spus, procesul de
codul sursă trece prin

558
00:25:27,610 --> 00:25:28,430
este exact acest lucru.

559
00:25:28,430 --> 00:25:31,180
Iei codul sursă, trece
printr-un compilator, cum ar fi zăngănit,

560
00:25:31,180 --> 00:25:34,650
și în afara vine cod obiect, care
s-ar putea arata ca acest lucru, zerouri și cele

561
00:25:34,650 --> 00:25:37,880
că CPU computerului, Central
unitate de procesare sau a creierului,

562
00:25:37,880 --> 00:25:39,760
în cele din urmă înțelege.

563
00:25:39,760 --> 00:25:42,460
>> Se pare că asta-i o
bit de o simplificare,

564
00:25:42,460 --> 00:25:44,480
că suntem acum într-o
Poziția sa tachineze in afara

565
00:25:44,480 --> 00:25:46,720
pentru a intelege ce a fost foarte
întâmplă sub capota

566
00:25:46,720 --> 00:25:48,600
de fiecare dată când a alerga
Zăngăni, sau mai general,

567
00:25:48,600 --> 00:25:53,040
de fiecare dată când face un program,
folosind Marca și CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
În special, chestii de genul
acest lucru este primul generat,

569
00:25:56,760 --> 00:25:58,684
atunci când compilați programul prima.

570
00:25:58,684 --> 00:26:00,600
Cu alte cuvinte, atunci când
ia codul sursă

571
00:26:00,600 --> 00:26:04,390
și compila, ceea ce este în primul rând
fiind scoase de zăngănit

572
00:26:04,390 --> 00:26:06,370
este ceva cunoscut sub numele de cod de asamblare.

573
00:26:06,370 --> 00:26:08,990
Și, de fapt, se pare ca acest lucru exact.

574
00:26:08,990 --> 00:26:11,170
>> Am fugit o comandă la
linie de comandă mai devreme.

575
00:26:11,170 --> 00:26:16,260
Hello.c capitalul bord zăngănit s,
și acest lucru a creat un fișier

576
00:26:16,260 --> 00:26:19,490
pentru ma sunat hello.s,
interiorul din care au fost exact

577
00:26:19,490 --> 00:26:22,290
aceste conținuturi, și un pic mai mult
deasupra și un pic mai jos,

578
00:26:22,290 --> 00:26:25,080
dar am pus juiciest
informații aici pe ecran.

579
00:26:25,080 --> 00:26:29,190
Și dacă te uiți atent, veți vedea
cel puțin câteva cuvinte cheie familiar.

580
00:26:29,190 --> 00:26:31,330
Avem principal în partea de sus.

581
00:26:31,330 --> 00:26:35,140
Am printf în mijloc.

582
00:26:35,140 --> 00:26:38,670
Si ne-am, de asemenea, salut lume
backslash n ghilimele jos.

583
00:26:38,670 --> 00:26:42,450
>> Și orice altceva aici
este instrucțiuni foarte slabe

584
00:26:42,450 --> 00:26:45,500
că CPU computerului intelege.

585
00:26:45,500 --> 00:26:50,090
Instrucțiuni CPU care se mișcă de memorie
în jurul valorii de, că siruri de caractere de încărcare din memorie,

586
00:26:50,090 --> 00:26:52,750
și în cele din urmă, de imprimare
lucruri pe ecran.

587
00:26:52,750 --> 00:26:56,780
Acum, ce se întâmplă, deși după
este generat acest cod de asamblare?

588
00:26:56,780 --> 00:26:59,964
În cele din urmă, ai face, într-adevăr,
încă genera cod obiect.

589
00:26:59,964 --> 00:27:02,630
Dar pașii care au într-adevăr
fost întâmplă sub capota

590
00:27:02,630 --> 00:27:04,180
uite un pic mai mult ca aceasta.

591
00:27:04,180 --> 00:27:08,390
Codul sursă devine codul de asamblare,
care apoi devine cod obiect,

592
00:27:08,390 --> 00:27:11,930
iar cuvintele operative aici sunt ca,
atunci când compilați codul sursă,

593
00:27:11,930 --> 00:27:16,300
out vine codul de asamblare, și apoi
atunci când asambla codul de asamblare,

594
00:27:16,300 --> 00:27:17,800
out vine cod obiect.

595
00:27:17,800 --> 00:27:20,360
>> Acum zăngănit este super sofisticat,
ca o mulțime de compilatoare,

596
00:27:20,360 --> 00:27:23,151
și-l face toate aceste etape
împreună, și aceasta nu neapărat

597
00:27:23,151 --> 00:27:25,360
ieșire orice intermediar
Fișierele pe care le puteți vedea chiar.

598
00:27:25,360 --> 00:27:28,400
Doar compilează lucruri,
care este termenul general care

599
00:27:28,400 --> 00:27:30,000
descrie acest proces.

600
00:27:30,000 --> 00:27:32,000
Dar daca vrei cu adevarat
pentru a fi special, nu e

601
00:27:32,000 --> 00:27:34,330
mult mai mult întâmplă acolo, de asemenea.

602
00:27:34,330 --> 00:27:38,860
>> Dar să considerăm, de asemenea, că, chiar acum
acest program super-simplu, hello.c,

603
00:27:38,860 --> 00:27:40,540
numit o funcție.

604
00:27:40,540 --> 00:27:41,870
Acesta a invitat printf.

605
00:27:41,870 --> 00:27:46,900
Dar nu am scrie printf, într-adevăr,
care vine cu C, ca să spunem așa.

606
00:27:46,900 --> 00:27:51,139
Este o rechemare funcție care este
a declarat în io.h standard care

607
00:27:51,139 --> 00:27:53,180
este un fișier antet, care
este un subiect vom fapt

608
00:27:53,180 --> 00:27:55,780
se arunca cu capul în mai multă profunzime, înainte de mult timp.

609
00:27:55,780 --> 00:27:58,000
Dar un fișier header este
de obicei însoțite

610
00:27:58,000 --> 00:28:02,920
printr-un fișier de cod, sursă fișier de cod, astfel încât
la fel ca exista io.h. standard de

611
00:28:02,920 --> 00:28:05,930
>> Candva acum, cineva,
sau cuiva, de asemenea, a scris

612
00:28:05,930 --> 00:28:11,040
un fișier numit io.c standard în
care definițiile reale,

613
00:28:11,040 --> 00:28:15,220
sau implementari de printf,
și ciorchini de alte funcții,

614
00:28:15,220 --> 00:28:16,870
sunt de fapt scrise.

615
00:28:16,870 --> 00:28:22,140
Deci având în vedere că, dacă luăm în considerare având
aici, pe stânga, hello.c, că, atunci când

616
00:28:22,140 --> 00:28:26,250
compilat, ne dă hello.s, chiar dacă
Zăngăni nu deranjează economisire într-un loc

617
00:28:26,250 --> 00:28:31,360
putem vedea, și că codul de asamblare
devine asamblate în hello.o, care

618
00:28:31,360 --> 00:28:34,630
este, într-adevăr, numele implicit
având în vedere ori de câte ori compila sursa

619
00:28:34,630 --> 00:28:39,350
cod în cod obiect, dar nu sunt
destul de gata să-l execute încă,

620
00:28:39,350 --> 00:28:41,460
deoarece un alt pas
trebuie să se întâmple, și are

621
00:28:41,460 --> 00:28:44,440
se întâmplă pentru ultimele
săptămâni, probabil fără știrea pentru tine.

622
00:28:44,440 --> 00:28:47,290
>> Mai exact undeva
în CS50 IDE, și acest lucru,

623
00:28:47,290 --> 00:28:49,870
de asemenea, va fi un pic de o
simplificare pentru un moment,

624
00:28:49,870 --> 00:28:54,670
există, sau a fost la un moment dat,
un fișier numit io.c standard

625
00:28:54,670 --> 00:28:58,440
că cineva compilat în
io.s standard sau echivalentul,

626
00:28:58,440 --> 00:29:02,010
că cineva apoi asamblate
în io.o standard

627
00:29:02,010 --> 00:29:04,600
sau se dovedește într-un
ușor diferite fișier

628
00:29:04,600 --> 00:29:07,220
format care poate avea un alt
fișier prelungire cu totul,

629
00:29:07,220 --> 00:29:11,720
dar în teorie și conceptual, exact
aceste măsuri trebuia să se întâmple într-o formă.

630
00:29:11,720 --> 00:29:14,060
Care este de a spune, că acum
când am scris un program,

631
00:29:14,060 --> 00:29:17,870
hello.c, ca doar spune, Hello lume,
și eu sunt, folosind codul de altcuiva

632
00:29:17,870 --> 00:29:22,480
ca printf, care a fost o dată la un
timp, într-un fișier numit io.c standard

633
00:29:22,480 --> 00:29:26,390
apoi într-un fel am să-mi iau
cod obiect, zerouri și cele mei,

634
00:29:26,390 --> 00:29:29,260
și obiect care persoane
cod, sau zerouri și cele,

635
00:29:29,260 --> 00:29:34,970
și într-un fel le lega împreună într-
un fișier final numit salut, că

636
00:29:34,970 --> 00:29:38,070
are toate zerourile și
cei de la funcția mea principală,

637
00:29:38,070 --> 00:29:40,830
și toate zerourile
iar cele pentru printf.

638
00:29:40,830 --> 00:29:44,900
>> Și într-adevăr, că ultimul proces este
numit, care leagă codul obiect.

639
00:29:44,900 --> 00:29:47,490
Din care producția
este un fișier executabil.

640
00:29:47,490 --> 00:29:49,780
Deci, în echitate, la
sfârșitul zilei, nimic

641
00:29:49,780 --> 00:29:52,660
sa schimbat din saptamana, cand am
Primul a început compilarea programelor.

642
00:29:52,660 --> 00:29:55,200
Într-adevăr, toate acestea au fost
întâmplă sub capota,

643
00:29:55,200 --> 00:29:57,241
dar acum suntem într-o poziție
în cazul în care putem de fapt

644
00:29:57,241 --> 00:29:58,794
tachineze pe langa aceste diferite etape.

645
00:29:58,794 --> 00:30:00,710
Și într-adevăr, la sfârșitul
a zilei, suntem încă

646
00:30:00,710 --> 00:30:04,480
a plecat cu zero și cele care,
este de fapt o mare Segue acum

647
00:30:04,480 --> 00:30:08,620
într-un alt capacitatea de C, care
noi nu am avut să impulsioneze, cel mai probabil

648
00:30:08,620 --> 00:30:11,250
până în prezent, cunoscut sub numele de operatori la nivel de bit.

649
00:30:11,250 --> 00:30:15,220
Cu alte cuvinte, până acum, oricând ne-am
tratate cu date în C sau variabile în C,

650
00:30:15,220 --> 00:30:17,660
am avut lucruri de genul
caractere, pluteste si ins

651
00:30:17,660 --> 00:30:21,990
și tânjește și duble și altele asemenea, dar
toate acelea sunt cel puțin opt biți.

652
00:30:21,990 --> 00:30:25,550
Noi nu am fost încă în măsură să
manipula biți individuale,

653
00:30:25,550 --> 00:30:28,970
chiar dacă un pic individ, am
știu, poate reprezenta un 0 și 1.

654
00:30:28,970 --> 00:30:32,640
Acum se pare că, în C, vă
pot avea acces la biți individuali,

655
00:30:32,640 --> 00:30:35,530
daca stii sintaxa,
cu care pentru a ajunge la ei.

656
00:30:35,530 --> 00:30:38,010
>> Deci, haideți să aruncăm o privire
operatorilor la nivel de bit.

657
00:30:38,010 --> 00:30:41,700
Deci, imagine aici sunt câteva simboluri care
am, un fel de, un fel de, văzut înainte.

658
00:30:41,700 --> 00:30:45,580
Văd un ampersand, un vertical
bar, și altele, precum și,

659
00:30:45,580 --> 00:30:49,430
și reamintească faptul că ampersand ampersand
este ceva ce am văzut până acum.

660
00:30:49,430 --> 00:30:54,060
Operatorul logic, în cazul în care aveți
doi dintre ei împreună, sau logică sau

661
00:30:54,060 --> 00:30:56,300
Operatorul, în cazul în care
au două bare verticale.

662
00:30:56,300 --> 00:31:00,550
Operatorii la nivel de bit, pe care le vom
vezi operează pe biți individual,

663
00:31:00,550 --> 00:31:03,810
folosi doar un singur ampersand, un
bar vertical unic, simbolul caret

664
00:31:03,810 --> 00:31:06,620
urmeaza, puținul
tilda, și apoi a plecat

665
00:31:06,620 --> 00:31:08,990
suport stânga suport, sau
Suport drept suport dreapta.

666
00:31:08,990 --> 00:31:10,770
Fiecare dintre acestea au sensuri diferite.

667
00:31:10,770 --> 00:31:11,950
>> De fapt, hai să aruncăm o privire.

668
00:31:11,950 --> 00:31:16,560
Să mergem vechea școală astăzi, și utilizarea
un ecran tactil de odinioară,

669
00:31:16,560 --> 00:31:18,002
cunoscut ca o tablă albă.

670
00:31:18,002 --> 00:31:19,710
Și această tablă
este de gând să ne permită

671
00:31:19,710 --> 00:31:27,360
să-și exprime unele simboluri destul de simplu,
sau mai degrabă niște formule destul de simpli,

672
00:31:27,360 --> 00:31:29,560
că putem, atunci în cele din urmă
efectul de levier, în scopul de

673
00:31:29,560 --> 00:31:33,230
pentru a accesa individuale
biți în cadrul unui program C.

674
00:31:33,230 --> 00:31:34,480
Cu alte cuvinte, să facem acest lucru.

675
00:31:34,480 --> 00:31:37,080
Să vorbim mai întâi pentru o
clipă despre ampersand,

676
00:31:37,080 --> 00:31:39,560
care este la nivel de bit operatorul AND.

677
00:31:39,560 --> 00:31:42,130
Cu alte cuvinte, aceasta este
un operator care permite

678
00:31:42,130 --> 00:31:45,930
să am o variabilă stânga
de obicei, și o variabilă dreapta,

679
00:31:45,930 --> 00:31:50,640
sau o valoare individuală, că, dacă noi și
le împreună, îmi dă un rezultat final.

680
00:31:50,640 --> 00:31:51,560
Deci, ce vreau sa spun?

681
00:31:51,560 --> 00:31:54,840
Dacă într-un program, aveți o variabilă
care stochează unul dintre aceste valori,

682
00:31:54,840 --> 00:31:58,000
sau să-l păstrați simplu, și doar
scrie zerouri și cele individuale,

683
00:31:58,000 --> 00:32:00,940
Iată cum funcționează operatorul ampersand.

684
00:32:00,940 --> 00:32:06,400
0 0 ampersand va egala cu 0.

685
00:32:06,400 --> 00:32:07,210
Acum, de ce este asta?

686
00:32:07,210 --> 00:32:09,291
>> Este foarte asemănător cu
Expresii booleene,

687
00:32:09,291 --> 00:32:10,540
pe care le-am discutat până acum.

688
00:32:10,540 --> 00:32:15,800
Dacă credeți că la urma urmei, este de 0
false, 0 este falsă, fals și fals

689
00:32:15,800 --> 00:32:18,720
este, așa cum am discutat
în mod logic, de asemenea fals.

690
00:32:18,720 --> 00:32:20,270
Deci, vom ajunge la 0 aici, de asemenea.

691
00:32:20,270 --> 00:32:24,390
Dacă luați 0 ampersand
1, bine că, de asemenea,

692
00:32:24,390 --> 00:32:29,890
va fi 0, pentru că în acest
expresie stanga, pentru a fi adevărat sau 1,

693
00:32:29,890 --> 00:32:32,360
acesta ar trebui să fie adevărat și adevărat.

694
00:32:32,360 --> 00:32:36,320
Dar aici avem false
și adevărat, sau 0 și 1.

695
00:32:36,320 --> 00:32:42,000
Acum, din nou, în cazul în care avem un ampersand
0, care, de asemenea, va fi 0,

696
00:32:42,000 --> 00:32:47,240
iar dacă avem un ampersand 1,
În cele din urmă avem un pic de 1.

697
00:32:47,240 --> 00:32:50,340
Deci, cu alte cuvinte, nu facem
ceva interesant cu acest operator

698
00:32:50,340 --> 00:32:51,850
încă, acest operator ampersand.

699
00:32:51,850 --> 00:32:53,780
Este la nivel de bit AND operatorul.

700
00:32:53,780 --> 00:32:57,290
Dar acestea sunt ingredientele
prin care putem face

701
00:32:57,290 --> 00:32:59,240
lucruri interesante, cum vom vedea în curând.

702
00:32:59,240 --> 00:33:02,790
>> Acum să ne uităm la doar single-
bară verticală pe aici, pe dreapta.

703
00:33:02,790 --> 00:33:06,710
Dacă am un pic si am 0
Sau cu, la nivel de bit

704
00:33:06,710 --> 00:33:11,030
Sau a operatorului, un alt 0 pic,
care va să-mi dea 0.

705
00:33:11,030 --> 00:33:17,540
Dacă am lua un pic 0 și sau cu
un pic 1, apoi am de gând pentru a obține 1.

706
00:33:17,540 --> 00:33:19,830
Și, de fapt, doar pentru
claritate, lasă-mă să mă întorc,

707
00:33:19,830 --> 00:33:23,380
astfel încât barele verticale mele
nu sunt confundat cu un lui.

708
00:33:23,380 --> 00:33:26,560
Permiteți-mi să rescrie toate
mea 1 este un pic mai mult

709
00:33:26,560 --> 00:33:32,700
în mod clar, astfel încât să putem vedea în continuare, dacă am
au un 1 sau 0, care va fi un 1,

710
00:33:32,700 --> 00:33:39,060
și dacă am un 1 sau 1, care,
de asemenea, va fi un 1.

711
00:33:39,060 --> 00:33:42,900
Deci, puteți vedea în mod logic că RUP
Operatorul se comporta foarte diferit.

712
00:33:42,900 --> 00:33:48,070
Acest lucru îmi dă 0 sau 0 îmi dă 0, dar
orice altă combinație dă-mi o.

713
00:33:48,070 --> 00:33:52,480
Atâta timp cât am o 1 în
formula, rezultatul va fi o.

714
00:33:52,480 --> 00:33:55,580
>> Prin contrast cu AND
Operatorul, ampersand,

715
00:33:55,580 --> 00:34:00,940
numai dacă am două 1 în
ecuație, primesc de fapt, un 1.

716
00:34:00,940 --> 00:34:02,850
Acum există o altă câteva
operatorii de asemenea.

717
00:34:02,850 --> 00:34:04,810
Una dintre ele este un pic mai implicat.

718
00:34:04,810 --> 00:34:07,980
Așa că lasă-mă să merg mai departe și șterge
acest lucru pentru a elibera spațiu.

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

720
00:34:13,020 --> 00:34:16,460
Și haideți să aruncăm o privire la
simbol caret, pentru o clipă.

721
00:34:16,460 --> 00:34:18,210
Aceasta este de obicei o
Caracterul aveți posibilitatea să tastați

722
00:34:18,210 --> 00:34:21,420
pe dumneavoastră exploatație tastatură Shift și
atunci unul dintre numerele de varful US ta

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

724
00:34:22,250 --> 00:34:26,190
>> Deci, acesta este exclusiv
Sau a operatorului, SAU exclusiv.

725
00:34:26,190 --> 00:34:27,790
Deci, am văzut doar operator sau.

726
00:34:27,790 --> 00:34:29,348
Aceasta este exclusiv sau operatorul.

727
00:34:29,348 --> 00:34:30,639
Care este de fapt diferența?

728
00:34:30,639 --> 00:34:34,570
Ei bine, hai să uităm la formula,
și de a folosi acest lucru ca ingrediente în cele din urmă.

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

730
00:34:37,690 --> 00:34:39,650
Am de gând să spun este întotdeauna 0.

731
00:34:39,650 --> 00:34:41,400
Asta e definiția XOR.

732
00:34:41,400 --> 00:34:47,104
0 XOR 1 va fi de 1.

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 va fi 1,
și 1 XOR 1 va fi?

734
00:34:58,810 --> 00:34:59,890
Greșit?

735
00:34:59,890 --> 00:35:00,520
Sau nu?

736
00:35:00,520 --> 00:35:01,860
Eu nu stiu.

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

738
00:35:02,810 --> 00:35:04,700
Acum, ce se întâmplă aici?

739
00:35:04,700 --> 00:35:06,630
Ei bine, Gândiți-vă la
Numele acestui operator.

740
00:35:06,630 --> 00:35:09,980
SAU exclusiv, în așa fel încât
numele, un fel de, sugerează,

741
00:35:09,980 --> 00:35:13,940
raspunsul este doar de gând să fie
1 în cazul în care intrările sunt exclusive,

742
00:35:13,940 --> 00:35:15,560
exclusiv diferit.

743
00:35:15,560 --> 00:35:18,170
Deci, aici intrările sunt
același, astfel încât rezultatul este 0.

744
00:35:18,170 --> 00:35:20,700
Aici intrările sunt
același, astfel încât rezultatul este 0.

745
00:35:20,700 --> 00:35:25,640
Aici sunt rezultatele sunt diferite, ele
sunt exclusive, și astfel ieșirea este 1.

746
00:35:25,640 --> 00:35:28,190
Deci, este foarte similar cu
Și, este foarte asemănătoare,

747
00:35:28,190 --> 00:35:32,760
sau mai degrabă este foarte similar cu
SAU, dar numai într-un mod exclusiv.

748
00:35:32,760 --> 00:35:36,210
Acesta nu mai este un 1,
pentru că avem două 1 lui,

749
00:35:36,210 --> 00:35:38,621
și nu exclusiv, doar una dintre ele.

750
00:35:38,621 --> 00:35:39,120
In regula.

751
00:35:39,120 --> 00:35:40,080
Ce zici de ceilalți?

752
00:35:40,080 --> 00:35:44,220
Ei bine tilda, între timp, este
de fapt, frumos și simplu, din fericire.

753
00:35:44,220 --> 00:35:46,410
Și aceasta este o unar
Operatorul, ceea ce înseamnă

754
00:35:46,410 --> 00:35:50,400
este aplicat la o singură intrare,
un operand, ca să spunem așa.

755
00:35:50,400 --> 00:35:51,800
Nu la un stânga și un drept.

756
00:35:51,800 --> 00:35:56,050
Cu alte cuvinte, dacă luați tilda de
0, răspunsul va fi opusul.

757
00:35:56,050 --> 00:35:59,710
Și dacă luați tilda de 1, The
răspuns nu va fi opusul.

758
00:35:59,710 --> 00:36:02,570
Deci operatorul tilda este
un mod de negarea un pic,

759
00:36:02,570 --> 00:36:06,000
sau flipping un pic de
0 la 1, sau 1 până la 0 ° C.

760
00:36:06,000 --> 00:36:09,820
>> Și asta ne lasă în cele din urmă
cu doar doi operatori finale,

761
00:36:09,820 --> 00:36:13,840
așa-numita schimbare stânga, și
așa-numita operator de schimbare dreapta.

762
00:36:13,840 --> 00:36:16,620
Să aruncăm o privire la modul în care aceste locul de muncă.

763
00:36:16,620 --> 00:36:20,780
Operatorul de schimbare stânga, scris
cu două paranteze unghiulare, cum ar fi faptul că,

764
00:36:20,780 --> 00:36:22,110
funcționează după cum urmează.

765
00:36:22,110 --> 00:36:27,390
Daca intrarea mea, sau operand mea, la stânga
Operatorul schimbare este pur și simplu un 1.

766
00:36:27,390 --> 00:36:33,750
Și am apoi spune computerul pentru a
schimbare lăsat 1, spun șapte locuri,

767
00:36:33,750 --> 00:36:37,150
rezultatul este ca și cum am
iei 1, și mutați-l

768
00:36:37,150 --> 00:36:40,160
șapte locuri pe la
stânga, și în mod implicit,

769
00:36:40,160 --> 00:36:42,270
vom presupune că
spațiul din dreapta

770
00:36:42,270 --> 00:36:44,080
va fi căptușit cu zerouri.

771
00:36:44,080 --> 00:36:50,316
Cu alte cuvinte, o schimbare a plecat 7 se va
să-mi dea că 1, urmat de 1, 2, 3,

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

773
00:36:54,060 --> 00:36:57,380
Deci, într-un fel, aceasta vă permite să
ia un număr mic ca 1,

774
00:36:57,380 --> 00:37:00,740
și în mod clar face mult
mult, mult mai mare în acest fel,

775
00:37:00,740 --> 00:37:06,460
dar ne vom vedea de fapt
abordări mai inteligent pentru el

776
00:37:06,460 --> 00:37:08,080
în schimb, precum și,

777
00:37:08,080 --> 00:37:08,720
>> In regula.

778
00:37:08,720 --> 00:37:10,060
Asta e săptămâna trei.

779
00:37:10,060 --> 00:37:11,400
Vă vom vedea data viitoare.

780
00:37:11,400 --> 00:37:12,770
Acest lucru a fost CS50.

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

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

783
00:37:22,243 --> 00:37:25,766
>> SPEAKER 1: A fost la snack-
bar manca o inghetata Fudge fierbinte.

784
00:37:25,766 --> 00:37:28,090
El a avut toate peste față.

785
00:37:28,090 --> 00:37:30,506
Poartă că ciocolata ca o barbă

786
00:37:30,506 --> 00:37:31,756
SPEAKER 2: Ce faci?

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

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

789
00:37:33,500 --> 00:37:36,800
>> SPEAKER 2: Ai doar dublu baie?

790
00:37:36,800 --> 00:37:38,585
Tu de întâlnire dublă chip.

791
00:37:38,585 --> 00:37:39,460
SPEAKER 3: Scuzați-mă.

792
00:37:39,460 --> 00:37:44,440
SPEAKER 2: Ai întâlnire cip, aveți
a luat o muscatura, si te întâlnire din nou.

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

794
00:37:44,940 --> 00:37:48,440
SPEAKER 2: Deci asta e ca punerea
întreaga dreptul de gura in dip.

795
00:37:48,440 --> 00:37:52,400
Data viitoare să luați un cip,
doar o dată dip, și se încheie o.

796
00:37:52,400 --> 00:37:53,890
>> SPEAKER 3: Știi ce, Dan?

797
00:37:53,890 --> 00:37:58,006
Tu dip modul în care doriți să se scufunde.

798
00:37:58,006 --> 00:38:01,900
Voi dip modul în care vreau să se scufunde.

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