1
00:00:00,000 --> 00:00:11,904
>> [Zenelejátszási]

2
00:00:11,904 --> 00:00:12,910
>> Tanár: Rendben.

3
00:00:12,910 --> 00:00:16,730
Ez CS50 és ez
hét végéig három.

4
00:00:16,730 --> 00:00:20,230
Tehát itt vagyunk ma, és nem a Sanders
Színház, hanem a Weidner Könyvtár.

5
00:00:20,230 --> 00:00:23,170
Amelynek belsejében egy stúdió
néven Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
vagy mondjuk Studio H, vagy meg kell
mi say-- ha tetszett, hogy vicc,

7
00:00:28,310 --> 00:00:30,540
ez valójában a
osztálytársa, Mark, az interneten,

8
00:00:30,540 --> 00:00:32,420
aki azt javasolta, amennyire a Twitteren keresztül.

9
00:00:32,420 --> 00:00:34,270
Most mi erről hűvös
hogy itt egy stúdióban

10
00:00:34,270 --> 00:00:38,410
hogy én vagyok körülvéve E zöld
falak, egy zöld képernyő vagy chromakey,

11
00:00:38,410 --> 00:00:43,290
hogy úgy mondjam, ami azt jelenti, hogy a CS50
produkciós csapat, ismeretlenül nekem

12
00:00:43,290 --> 00:00:47,380
Most, lehet üzembe
engem leginkább a világ bármely pontján,

13
00:00:47,380 --> 00:00:48,660
jobb vagy rosszabb.

14
00:00:48,660 --> 00:00:51,800
>> Most mi vár ránk, a probléma beállítva
Két az ön kezében van erre a hétre,

15
00:00:51,800 --> 00:00:53,830
de a probléma beállítva
Három a jövő héten,

16
00:00:53,830 --> 00:00:56,600
akkor lehet megtámadni a
az úgynevezett játék 15,

17
00:00:56,600 --> 00:00:58,960
Egy régi fél javára, hogy
talán felidézni részesülő

18
00:00:58,960 --> 00:01:02,030
mint a gyermek, hogy van egy csomó
A számok, hogy lehet csúszni lefelé, felfelé,

19
00:01:02,030 --> 00:01:05,790
balra és jobbra, és van egy rés
a puzzle, amelybe

20
00:01:05,790 --> 00:01:07,840
valóban csúszik ezeket puzzle-darabokat.

21
00:01:07,840 --> 00:01:11,150
Végül is megkapja ezt
puzzle néhány félig véletlenszerű sorrendben,

22
00:01:11,150 --> 00:01:12,940
és a cél az, hogy
szortírozni, fentről lefelé,

23
00:01:12,940 --> 00:01:16,310
balról jobbra, egyik
egészen a 15.

24
00:01:16,310 --> 00:01:19,360
>> Sajnos, a végrehajtás
akkor kéznél

25
00:01:19,360 --> 00:01:21,590
lesz szoftverek
alapuló, nem fizikailag.

26
00:01:21,590 --> 00:01:25,280
Te tényleg kell majd írni
kódot, amellyel a tanuló vagy felhasználó

27
00:01:25,280 --> 00:01:26,760
A játék 15.

28
00:01:26,760 --> 00:01:29,030
És valóban, a hekker
kiadás játék 15,

29
00:01:29,030 --> 00:01:32,155
akkor lesz egy kihívás, hogy hajtsák végre,
Nem csak a játék ennek a régi iskola

30
00:01:32,155 --> 00:01:35,010
játék, hanem a megoldási
belőle, végrehajtási isten mód,

31
00:01:35,010 --> 00:01:38,280
hogy úgy mondjam, hogy ténylegesen
megoldja a puzzle az emberi,

32
00:01:38,280 --> 00:01:41,080
biztosítva számukra a célzást,
után hint után hint.

33
00:01:41,080 --> 00:01:42,280
Így még az, hogy a jövő héten.

34
00:01:42,280 --> 00:01:43,720
De ez mi vár ránk.

35
00:01:43,720 --> 00:01:47,610
>> Most emlékeztetnek arra, hogy a hét elején
mi volt ez a filmsorozat, ha úgy tetszik,

36
00:01:47,610 --> 00:01:52,560
ahol a legjobb csinálunk válogatás
bölcs volt, egy felső korlát a nagy o n

37
00:01:52,560 --> 00:01:53,210
négyzeten.

38
00:01:53,210 --> 00:01:56,520
Más szóval, a buborék rendezés,
kiválasztási sorrend, beillesztés sort,

39
00:01:56,520 --> 00:01:59,120
mindegyiket, míg a különböző
a végrehajtásban,

40
00:01:59,120 --> 00:02:03,480
decentralizált egy n futó faragva
ideje a legrosszabb esetben.

41
00:02:03,480 --> 00:02:06,010
És általában azt feltételezik, hogy
A legrosszabb esetben a válogató

42
00:02:06,010 --> 00:02:08,814
az egyik, hogy a bemenetek
teljesen hátra.

43
00:02:08,814 --> 00:02:11,980
És valóban, ez volt jó néhány lépést
hogy végre minden egyes ilyen algoritmusok.

44
00:02:11,980 --> 00:02:15,110
>> Most a legvégén osztály
Emlékezzünk, összehasonlítottuk buborékos rendezést

45
00:02:15,110 --> 00:02:19,390
elleni szelekció egyfajta ellen egy másik
hogy hívják merge sort abban az időben,

46
00:02:19,390 --> 00:02:22,120
és azt javaslom, hogy túl sok időt vesz
Használja ki a leckét a héten

47
00:02:22,120 --> 00:02:24,060
nulla, Oszd meg és uralkodj.

48
00:02:24,060 --> 00:02:28,810
És valahogy eléréséhez valamiféle
logaritmikus futási idő végső soron,

49
00:02:28,810 --> 00:02:31,024
valami helyett
ez tisztán másodfokú.

50
00:02:31,024 --> 00:02:33,440
És ez nem elég logaritmikus,
ez egy kicsit több annál.

51
00:02:33,440 --> 00:02:36,520
De ha visszahívja osztály,
ez sokkal, sokkal gyorsabb.

52
00:02:36,520 --> 00:02:38,210
Vessünk egy pillantást, ahol abbahagytuk.

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

54
00:02:41,880 --> 00:02:45,370
>> Bubble sort versus kiválasztása
Rendezés versus merge sort.

55
00:02:45,370 --> 00:02:47,700
Most meg az összes futó, a
elmélet, ugyanabban az időben.

56
00:02:47,700 --> 00:02:50,510
A CPU fut azonos sebességgel.

57
00:02:50,510 --> 00:02:54,990
De akkor érezni, milyen unalmas ez a
nagyon gyorsan fog válni,

58
00:02:54,990 --> 00:02:58,790
és milyen gyorsan, amikor injekciót
egy kicsit a heti nulla algoritmusok,

59
00:02:58,790 --> 00:03:00,080
lehet felpörgetni a dolgokat.

60
00:03:00,080 --> 00:03:01,630
>> Tehát védjegy a fajta néz ki, csodálatos.

61
00:03:01,630 --> 00:03:05,220
Hogyan tudjuk kiterjesszük, annak érdekében,
a számok sorrendje gyorsabban.

62
00:03:05,220 --> 00:03:07,140
Hát lássuk csak vissza
hogy egy összetevő, hogy mi

63
00:03:07,140 --> 00:03:10,380
volt vissza héten nulla, hogy a
keres valaki egy telefonkönyv,

64
00:03:10,380 --> 00:03:12,380
és emlékszem, hogy a
pszeudokódja hogy mi javasolt,

65
00:03:12,380 --> 00:03:14,560
amelyen keresztül találunk
valaki, mint Mike Smith,

66
00:03:14,560 --> 00:03:16,310
nézett egy kicsit valami ilyesmi.

67
00:03:16,310 --> 00:03:20,820
>> Most vessünk egy pillantást különösen
sorban a 7. és a 8., és a 10. és 11.,

68
00:03:20,820 --> 00:03:25,240
indukáló, hogy hurok, amely által tartott
megy vissza a 3. sorban újra, és újra,

69
00:03:25,240 --> 00:03:26,520
és megint.

70
00:03:26,520 --> 00:03:31,790
De kiderül, hogy mi lehet megtekinteni
Az algoritmus, itt pszeudokódja,

71
00:03:31,790 --> 00:03:33,620
egy kicsit több holisztikusan.

72
00:03:33,620 --> 00:03:35,960
Tény, hogy mit keresek
meg itt a képernyőn,

73
00:03:35,960 --> 00:03:41,180
egy algoritmus keresésére
Mike Smith között néhány sor oldalakon.

74
00:03:41,180 --> 00:03:45,520
És valóban, mi is leegyszerűsítik ezt
algoritmus ezeket a sorokat a 7. és 8.,

75
00:03:45,520 --> 00:03:49,860
10 és 11, hogy csak ezt mondom,
amit már itt bemutatott sárga.

76
00:03:49,860 --> 00:03:52,210
Más szavakkal, ha Mike
Smith korábban a könyvet,

77
00:03:52,210 --> 00:03:55,004
nem kell megadni lépésben
lépésre most hogyan megy találni.

78
00:03:55,004 --> 00:03:56,920
Nem kell megadni
hogy menjen vissza a 3. sorban,

79
00:03:56,920 --> 00:03:58,960
Miért nem csak ahelyett,
mondjuk, általánosabban,

80
00:03:58,960 --> 00:04:01,500
keresni Mike a
bal fele a könyv.

81
00:04:01,500 --> 00:04:03,960
>> Ezzel szemben, ha Mike
igazából később a könyvben,

82
00:04:03,960 --> 00:04:07,540
miért nem csak idézni idézet vége keresés
Mike a jobb fele a könyv.

83
00:04:07,540 --> 00:04:11,030
Más szóval, miért nem megyünk
fajta punt magunkat, mondván,

84
00:04:11,030 --> 00:04:13,130
keresni Mike ezen
részhalmaza a könyv,

85
00:04:13,130 --> 00:04:16,279
és hagyja, hogy a már meglévő
algoritmust, hogy elmondja nekünk

86
00:04:16,279 --> 00:04:18,750
hogyan kell keresni Mike
hogy bal fele a könyv.

87
00:04:18,750 --> 00:04:20,750
Más szavakkal, a mi
algoritmus dolgozik, hogy ez

88
00:04:20,750 --> 00:04:24,670
telefonkönyv ennek vastagsága, ennek
vastagsága, vagy bármilyen vastagságú nélkül.

89
00:04:24,670 --> 00:04:27,826
Így tudjuk rekurzív
határozzák meg ezt az algoritmust.

90
00:04:27,826 --> 00:04:29,950
Más szavakkal, a
képernyőn van, egy algoritmus

91
00:04:29,950 --> 00:04:33,130
keresésére Mike Smith
között az oldalak egy telefonkönyv.

92
00:04:33,130 --> 00:04:37,410
Tehát a sorban a 7 és 10, nézzük
csak annyit, hogy pontosan.

93
00:04:37,410 --> 00:04:40,250
És én ezt a kifejezést egy pillanatra
ezelőtt, és valóban, rekurzió

94
00:04:40,250 --> 00:04:42,450
a szlogen most,
és ez ebben a folyamatban

95
00:04:42,450 --> 00:04:47,210
csinál valamit ciklikus által valahogy
kóddal, hogy már van,

96
00:04:47,210 --> 00:04:49,722
és hív meg újra,
és újra, és újra.

97
00:04:49,722 --> 00:04:51,930
Most lesz fontos
hogy valahogy alján

98
00:04:51,930 --> 00:04:53,821
ki, és nem csinál ilyet végtelenül hosszú.

99
00:04:53,821 --> 00:04:56,070
Ellenkező megyünk
valóban van egy végtelen ciklus.

100
00:04:56,070 --> 00:04:59,810
De lássuk, mi lehet kölcsönözni ezt az elképzelést
A rekurzív, hogy valami újra

101
00:04:59,810 --> 00:05:03,600
és újra és újra, hogy megoldja
A válogatás probléma keresztül merge

102
00:05:03,600 --> 00:05:05,900
rendezés, mind a hatékonyabb.

103
00:05:05,900 --> 00:05:06,970
>> Szóval adok neked merge sort.

104
00:05:06,970 --> 00:05:07,920
Vessünk egy pillantást.

105
00:05:07,920 --> 00:05:10,850
Tehát itt van pszeudokódja, a
amely tudtuk megvalósítani rendezési,

106
00:05:10,850 --> 00:05:12,640
ezt az algoritmust nevű egyesítési sort.

107
00:05:12,640 --> 00:05:13,880
És ez egészen egyszerűen ez.

108
00:05:13,880 --> 00:05:15,940
Input n elem,
más szóval, ha

109
00:05:15,940 --> 00:05:18,830
Adott n elem és számok
levelek, vagy bármi a bemenet,

110
00:05:18,830 --> 00:05:22,430
ha adott n elem, ha
n értéke kisebb, mint 2, csak vissza.

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

112
00:05:22,930 --> 00:05:26,430
Mert ha n értéke kisebb, mint 2, hogy
azt jelenti, hogy én elemek listája

113
00:05:26,430 --> 00:05:30,446
jelentése vagy a mérete 0 vagy 1, és
mindkét ilyen triviális esetekben

114
00:05:30,446 --> 00:05:31,570
A lista már válogatni.

115
00:05:31,570 --> 00:05:32,810
Ha nincs lista, ez válogatni.

116
00:05:32,810 --> 00:05:35,185
És ha van egy lista hosszát
1, ez nyilván válogatni.

117
00:05:35,185 --> 00:05:38,280
Tehát az algoritmus csak arra, hogy
tényleg valami érdekeset,

118
00:05:38,280 --> 00:05:40,870
ha van két vagy több,
elemek adott nekünk.

119
00:05:40,870 --> 00:05:42,440
Szóval nézzük meg a mágikus majd.

120
00:05:42,440 --> 00:05:47,500
Else rendezni a bal fele az elemek,
majd rendezni a jobb fele elemek,

121
00:05:47,500 --> 00:05:49,640
majd egyesíti a rendezve félidőt.

122
00:05:49,640 --> 00:05:52,440
És mi van egyfajta elme hajlító
Itt, az, hogy én nem igazán

123
00:05:52,440 --> 00:05:56,190
Úgy tűnik, hogy megmondtam
semmit csak még, ugye?

124
00:05:56,190 --> 00:05:59,560
Minden, amit mondtam az, kap egy listát
n elem, rendezheti a bal fele,

125
00:05:59,560 --> 00:06:01,800
majd a jobb oldalát, majd
egyesíti a rendezve félidőt,

126
00:06:01,800 --> 00:06:03,840
de hol van a tényleges titkos szósz?

127
00:06:03,840 --> 00:06:05,260
Hol van az algoritmus?

128
00:06:05,260 --> 00:06:09,150
Kiderült, hogy a két vonal
első, egyfajta bal fele elemek,

129
00:06:09,150 --> 00:06:13,970
és egyfajta jobb fele elemek,
rekurzívak hívások, hogy úgy mondjam.

130
00:06:13,970 --> 00:06:16,120
>> Végtére is, ebben a
időpontban, tudom már,

131
00:06:16,120 --> 00:06:18,950
egy algoritmust, amellyel
rendezni egy csomó elemek?

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

133
00:06:19,450 --> 00:06:20,620
Itt van.

134
00:06:20,620 --> 00:06:25,180
Itt van a képernyőn, és
így tudom használni, hogy ugyanazokat a lépéseket

135
00:06:25,180 --> 00:06:28,500
rendezni a bal fele,
amennyit csak tudok jobb felét.

136
00:06:28,500 --> 00:06:30,420
És valóban, újra, és újra.

137
00:06:30,420 --> 00:06:34,210
Szóval valahogy, és ha hamarosan
látni ezt a varázslatos merge sort

138
00:06:34,210 --> 00:06:37,967
van ágyazva, hogy nagyon végső
vonal, összevonása a rendezett félidőt.

139
00:06:37,967 --> 00:06:39,300
És úgy tűnik, meglehetősen intuitív.

140
00:06:39,300 --> 00:06:41,050
Veszel két felét, és akkor,
valahogy egyesíteni őket együtt,

141
00:06:41,050 --> 00:06:43,260
és majd meglátjuk, ez
konkrétan egy pillanat.

142
00:06:43,260 --> 00:06:45,080
>> De ez egy teljes algoritmus.

143
00:06:45,080 --> 00:06:46,640
És lássuk, pontosan miért.

144
00:06:46,640 --> 00:06:50,912
Hát tegyük fel, hogy mi mivel ugyanezek
nyolc elem van a képernyőn, az egyik

145
00:06:50,912 --> 00:06:53,120
a nyolc, de ők
A látszólag véletlenszerű sorrendben.

146
00:06:53,120 --> 00:06:55,320
És a cél kéznél van
rendezni ezeket az elemeket.

147
00:06:55,320 --> 00:06:58,280
Hát hogy is megy a
csinálja segítségével ismét

148
00:06:58,280 --> 00:07:00,407
merge sort, mint egy ennek pszeudokódja?

149
00:07:00,407 --> 00:07:02,740
És ismét, ingrain ezt
fejedben, csak egy pillanatra.

150
00:07:02,740 --> 00:07:05,270
Az első esetben elég
triviális, ha ez kevesebb, mint 2,

151
00:07:05,270 --> 00:07:07,060
csak vissza, nincs tennivaló.

152
00:07:07,060 --> 00:07:09,290
Szóval tényleg ott van csak három
lépéseket, hogy valóban szem előtt tartani.

153
00:07:09,290 --> 00:07:11,081
Újra, és újra, én vagyok
szeretne majd meg

154
00:07:11,081 --> 00:07:13,980
rendezni a bal fele,
rendezni a jobb fele,

155
00:07:13,980 --> 00:07:15,890
majd miután azok
két félből vannak sorolva,

156
00:07:15,890 --> 00:07:18,710
Azt szeretné egyesíteni őket együtt
egyetlen rendezett listát.

157
00:07:18,710 --> 00:07:19,940
Tehát hogy tartsa szem előtt.

158
00:07:19,940 --> 00:07:21,310
>> Tehát itt az eredeti listán.

159
00:07:21,310 --> 00:07:23,510
Nézzük kezelni ezt, mint egy
tömb, ahogy kezdett

160
00:07:23,510 --> 00:07:25,800
héten két, ami egy
összefüggő blokk memória.

161
00:07:25,800 --> 00:07:28,480
Ebben az esetben, amely nyolc
szám, vissza háttal.

162
00:07:28,480 --> 00:07:30,700
És nézzük most alkalmazni merge sort.

163
00:07:30,700 --> 00:07:33,300
Tehát először szeretnék rendezni
A bal fele ezt a listát,

164
00:07:33,300 --> 00:07:37,370
és nézzük tehát,
összpontosítani 4, 8, 6 és 2.

165
00:07:37,370 --> 00:07:41,000
>> Most hogyan megy körülbelül
válogató listáját 4-es méretű?

166
00:07:41,000 --> 00:07:45,990
Hát azt kell most úgy
válogatás a bal oldalon a bal fele.

167
00:07:45,990 --> 00:07:47,720
Ismét nézzük a visszatekerés csak egy pillanatra.

168
00:07:47,720 --> 00:07:51,010
Ha a pszeudokódja ez,
és én adott nyolc elem,

169
00:07:51,010 --> 00:07:53,230
8 nyilvánvalóan nagyobb
mint vagy egyenlő 2.

170
00:07:53,230 --> 00:07:54,980
Tehát az első esetben nem alkalmazható.

171
00:07:54,980 --> 00:07:58,120
Tehát rendezni nyolc elem, először
rendezni a bal fele elemek,

172
00:07:58,120 --> 00:08:01,930
aztán rendezni a jobb oldalát, majd Egyesíthetem
A két sorba rendezett felét, mindegyik 4-es méretű.

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

174
00:08:02,470 --> 00:08:07,480
>> De ha már csak azt mondta nekem, rendezni a
bal fele, amely most a 4-es méretű,

175
00:08:07,480 --> 00:08:09,350
hogyan tudom oldani a bal fele?

176
00:08:09,350 --> 00:08:11,430
Nos, ha van egy
bemeneti négy elem,

177
00:08:11,430 --> 00:08:14,590
Én először rendezni a bal
két, majd a jobb oldali két,

178
00:08:14,590 --> 00:08:16,210
és aztán egyesíteni őket együtt.

179
00:08:16,210 --> 00:08:18,700
Tehát újra, ez lesz egy kicsit
Egy elme hajlító játék itt,

180
00:08:18,700 --> 00:08:21,450
mert, fajta, meg kell
emlékszem, hogy hol van a történet,

181
00:08:21,450 --> 00:08:23,620
de a végén a nap,
adott semmilyen elemek száma,

182
00:08:23,620 --> 00:08:25,620
először szeretné rendezni a
bal felét, majd a jobb oldalát,

183
00:08:25,620 --> 00:08:26,661
majd egyesíti őket.

184
00:08:26,661 --> 00:08:28,630
Kezdjük pontosan erre.

185
00:08:28,630 --> 00:08:30,170
Itt a bemeneti nyolc elem.

186
00:08:30,170 --> 00:08:31,910
Most éppen a bal fele itt.

187
00:08:31,910 --> 00:08:33,720
Hogyan rendezni a négy elem?

188
00:08:33,720 --> 00:08:35,610
Hát először rendezni a bal fele.

189
00:08:35,610 --> 00:08:37,720
Most hogyan tudom oldani a bal fele?

190
00:08:37,720 --> 00:08:39,419
Nos Kaptam két elem.

191
00:08:39,419 --> 00:08:41,240
Úgyhogy rendezni ezt a két elemet.

192
00:08:41,240 --> 00:08:44,540
2-nél nagyobb vagy
egyenlő 2, természetesen.

193
00:08:44,540 --> 00:08:46,170
Úgy, hogy az első esetben nem alkalmazható.

194
00:08:46,170 --> 00:08:49,010
>> Szóval most már rendezni a bal
a fele a két elemet.

195
00:08:49,010 --> 00:08:50,870
A bal fele, persze, csak 4.

196
00:08:50,870 --> 00:08:54,020
Szóval hogyan tudom rendezni a lista egy elemét?

197
00:08:54,020 --> 00:08:57,960
Nos, hogy a különleges alapeset
fel tetején, hogy úgy mondjam, vonatkozik.

198
00:08:57,960 --> 00:09:01,470
1 kevesebb, mint 2, és az én
lista valóban az 1-es méret.

199
00:09:01,470 --> 00:09:02,747
Szóval csak vissza.

200
00:09:02,747 --> 00:09:03,580
Én nem csináltam semmit.

201
00:09:03,580 --> 00:09:06,770
És valóban, nézd meg amit én
kész, 4 már válogatni.

202
00:09:06,770 --> 00:09:09,220
Mint én már
részben sikeres itt.

203
00:09:09,220 --> 00:09:11,750
>> Most, hogy úgy tűnik, elég hülyén
igényelni, de igaz.

204
00:09:11,750 --> 00:09:13,700
4 van egy lista a 1-es méretű.

205
00:09:13,700 --> 00:09:15,090
Ez már válogatni.

206
00:09:15,090 --> 00:09:16,270
Ez a bal felét.

207
00:09:16,270 --> 00:09:18,010
Most rendezni a jobb fele.

208
00:09:18,010 --> 00:09:22,310
Én bemenet egyik eleme, 8
Hasonlóképpen, már válogatni.

209
00:09:22,310 --> 00:09:25,170
Hülye is, de a lényeg,
Ezen alapelv

210
00:09:25,170 --> 00:09:28,310
fog engedje meg, hogy most építenek
Ezen felül sikerrel.

211
00:09:28,310 --> 00:09:32,260
4 válogatni, 8 rendezve, most
Mi volt az utolsó lépés?

212
00:09:32,260 --> 00:09:35,330
Tehát a harmadik és utolsó lépés, bármilyen
alkalommal, amikor válogatás egy listát, visszahívás

213
00:09:35,330 --> 00:09:38,310
volt, hogy összevonja a két felét,
a bal és a jobb oldalon.

214
00:09:38,310 --> 00:09:39,900
Tehát lássuk, hogy pontosan.

215
00:09:39,900 --> 00:09:41,940
A bal fele, természetesen, 4.

216
00:09:41,940 --> 00:09:43,310
A jobb fele 8.

217
00:09:43,310 --> 00:09:44,100
>> Tehát lássuk ezt.

218
00:09:44,100 --> 00:09:46,410
Először fogok kiosztani
Néhány további memória,

219
00:09:46,410 --> 00:09:48,680
hogy én képviselek,
mint csak egy másodlagos tömb,

220
00:09:48,680 --> 00:09:49,660
de nagy ahhoz, hogy elférjen ebben.

221
00:09:49,660 --> 00:09:52,243
De el lehet képzelni meghosszabbításáról
E négyszögben a teljes hosszában,

222
00:09:52,243 --> 00:09:53,290
ha több kell majd.

223
00:09:53,290 --> 00:09:58,440
Hogyan szedjem 4 és 8, és egyesíti
E listáknak a mérete 1 együtt?

224
00:09:58,440 --> 00:10:00,270
Itt is elég egyszerű.

225
00:10:00,270 --> 00:10:03,300
4. előbb, aztán jön 8.

226
00:10:03,300 --> 00:10:07,130
Mert ha azt akarom, hogy rendezze a
bal felét, majd a jobb oldalát,

227
00:10:07,130 --> 00:10:09,900
majd egyesíteni a két félből
együtt, rendezett sorrendben,

228
00:10:09,900 --> 00:10:11,940
4. előbb, aztán jön 8.

229
00:10:11,940 --> 00:10:15,810
>> Tehát úgy tűnik, hogy előrelépéseket tett, sőt
bár én még nem történt semmilyen tényleges munkát.

230
00:10:15,810 --> 00:10:17,800
De ne felejtsd el, hogy hol vagyunk a történetben.

231
00:10:17,800 --> 00:10:19,360
Eredetileg vett nyolc elem.

232
00:10:19,360 --> 00:10:21,480
Mi válogatni a bal fele, amely 4.

233
00:10:21,480 --> 00:10:24,450
Aztán válogatni a bal fele
A bal fele, amely 2.

234
00:10:24,450 --> 00:10:25,270
És itt vagyunk.

235
00:10:25,270 --> 00:10:26,920
Végeztünk ezt a lépést.

236
00:10:26,920 --> 00:10:29,930
>> Tehát, ha egy rendezést a
bal fele 2, most

237
00:10:29,930 --> 00:10:32,130
kell rendezni a jobb fele 2.

238
00:10:32,130 --> 00:10:35,710
Így a jobb fele 2
E két érték itt, a 6. és a 2.

239
00:10:35,710 --> 00:10:40,620
Úgyhogy most felvesznek egy bemeneti méret
2, és a sort a bal fele, majd

240
00:10:40,620 --> 00:10:42,610
a jobb oldalán, majd
egyesíti őket.

241
00:10:42,610 --> 00:10:45,722
Hát hogyan tudom rendezni egy listát a méretet
1, amely csak a 6-os szám?

242
00:10:45,722 --> 00:10:46,430
Én már megtette.

243
00:10:46,430 --> 00:10:48,680
Ezt a listát az 1-es méret van rendezve.

244
00:10:48,680 --> 00:10:52,140
>> Hogyan rendezni egy másik listát
1-es méret, az úgynevezett jobb felét.

245
00:10:52,140 --> 00:10:54,690
Hát ez is, már válogatni.

246
00:10:54,690 --> 00:10:56,190
A 2-es szám van egyedül.

247
00:10:56,190 --> 00:11:00,160
Így most már két fele, a bal és
Rendben, azt kell egyesíteni őket együtt.

248
00:11:00,160 --> 00:11:01,800
Hadd hozzak magamnak egy kis szabad hely.

249
00:11:01,800 --> 00:11:05,580
És tedd 2 oda,
majd 6 odabent, ezáltal

250
00:11:05,580 --> 00:11:10,740
válogatás a listán, jobbra és balra,
és összefonódó össze, végső soron.

251
00:11:10,740 --> 00:11:12,160
Szóval én valamivel jobb állapotban van.

252
00:11:12,160 --> 00:11:16,250
Még nem végeztem, mert egyértelműen 4, 8, 2,
6 nem a végleges rendezés, amit akar.

253
00:11:16,250 --> 00:11:20,640
De most már két lista 2. méretű, hogy
egyaránt, illetve rendezve.

254
00:11:20,640 --> 00:11:24,580
Tehát most, ha visszalép az agyad
szem, hol, hogy el minket?

255
00:11:24,580 --> 00:11:28,520
Elkezdtem a nyolc elem, akkor én
szűkítették le, hogy a bal fele 4,

256
00:11:28,520 --> 00:11:31,386
majd a bal fele a 2, és
majd a jobb fele a 2,

257
00:11:31,386 --> 00:11:34,510
Befejeztem, ezért a válogatás a bal
fele 2, és a jobb fele a 2,

258
00:11:34,510 --> 00:11:37,800
akkor mi a harmadik és egyben utolsó lépés itt?

259
00:11:37,800 --> 00:11:41,290
Meg kell egybeolvadnak
két lista 2. méretű.

260
00:11:41,290 --> 00:11:42,040
Szóval menjünk előre.

261
00:11:42,040 --> 00:11:43,940
És a képernyőn van, így
nekem néhány további memória,

262
00:11:43,940 --> 00:11:47,170
bár alakilag észre, hogy én már
Van egy csomó üres hely akár felső

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

264
00:11:47,670 --> 00:11:50,044
Ha azt akarom, hogy különösen
hatékony tér bölcs,

265
00:11:50,044 --> 00:11:52,960
Tudtam csak elindulni az elemek
oda-vissza, alul és felül.

266
00:11:52,960 --> 00:11:55,460
De csak a vizuális tisztaságért,
Megyek, hogy tegye le az alábbiakban,

267
00:11:55,460 --> 00:11:56,800
hogy a dolgok szép és tiszta.

268
00:11:56,800 --> 00:11:58,150
>> Így kaptam két lista 2. méretű.

269
00:11:58,150 --> 00:11:59,770
Az első lista a 4 és 8.

270
00:11:59,770 --> 00:12:01,500
A második lista 2 és 6.

271
00:12:01,500 --> 00:12:03,950
Nézzük összevonjátok
együtt rendezett sorrendben.

272
00:12:03,950 --> 00:12:09,910
2, természetesen, az első,
majd 4, majd 6, majd 8.

273
00:12:09,910 --> 00:12:12,560
És most úgy tűnik, hogy egyre
egy érdekes helyen.

274
00:12:12,560 --> 00:12:15,720
Most már válogatni fele
listára, és véletlenül, ez

275
00:12:15,720 --> 00:12:18,650
az összes páros számot, de hogy
Valóban, csak véletlen egybeesés.

276
00:12:18,650 --> 00:12:22,220
És most már rendezni a bal
fele, úgy, hogy ez a 2., 4., 6., és 8..

277
00:12:22,220 --> 00:12:23,430
Semmi sem elromlott.

278
00:12:23,430 --> 00:12:24,620
Hogy érzi magát, mint haladást.

279
00:12:24,620 --> 00:12:26,650
>> Most úgy érzem, mintha volna
Beszéltem örökre most,

280
00:12:26,650 --> 00:12:29,850
akkor mi még a jövő zenéje, ha ezt
algoritmus, sőt, hatékonyabb.

281
00:12:29,850 --> 00:12:31,766
De megyünk keresztül
szuper módszeresen.

282
00:12:31,766 --> 00:12:34,060
Egy számítógép, természetesen,
megtenném, mint ezt.

283
00:12:34,060 --> 00:12:34,840
Szóval hol vagyunk?

284
00:12:34,840 --> 00:12:36,180
Azzal kezdtük, hogy nyolc elem.

285
00:12:36,180 --> 00:12:37,840
Én válogatni a bal fele 4.

286
00:12:37,840 --> 00:12:39,290
Úgy látszik, hogy készen van.

287
00:12:39,290 --> 00:12:42,535
Tehát most a következő lépés az, hogy
rendezni a jobb fele a 4.

288
00:12:42,535 --> 00:12:44,410
És ez a rész mehetünk
keresztül egy kicsit több,

289
00:12:44,410 --> 00:12:47,140
Gyorsan, bár te
Üdvözöljük vissza- vagy szüneteltetheti, csak

290
00:12:47,140 --> 00:12:49,910
végiggondolni azt
a saját tempójában, de mi

291
00:12:49,910 --> 00:12:53,290
mi most egy lehetőség, hogy
nem pontosan ugyanazt az algoritmust négy

292
00:12:53,290 --> 00:12:54,380
különböző számokat.

293
00:12:54,380 --> 00:12:57,740
>> Szóval menjünk előre, és figyelembe véve a
a jobb oldalát, ami itt vagyunk.

294
00:12:57,740 --> 00:13:01,260
A bal felét
jobb fele, és most a

295
00:13:01,260 --> 00:13:04,560
bal fele a bal oldali
fele a jobb felét,

296
00:13:04,560 --> 00:13:08,030
és hogyan rendezheti a listát mérete
1, amely csak az 1. számú?

297
00:13:08,030 --> 00:13:09,030
Ez már megtörtént.

298
00:13:09,030 --> 00:13:11,830
Hogyan csináljam ugyanezt a listát
Az 1-es méret, amely mindössze 7?

299
00:13:11,830 --> 00:13:12,840
Ez már megtörtént.

300
00:13:12,840 --> 00:13:16,790
Harmadik lépés erre a felét, majd
van, hogy egyesítsék e két elem

301
00:13:16,790 --> 00:13:20,889
egy új listát a mérete 2, 1 és 7.

302
00:13:20,889 --> 00:13:23,180
Nem úgy tűnik, hogy mindent megtettünk
hogy sok érdekes munka.

303
00:13:23,180 --> 00:13:24,346
Lássuk, mi történik ezután.

304
00:13:24,346 --> 00:13:29,210
Én csak válogatni a bal fele
jobb fele az eredeti input.

305
00:13:29,210 --> 00:13:32,360
Most rendezni a jobb
fele, amely 5 és 3.

306
00:13:32,360 --> 00:13:35,740
Nézzük újra nézd meg a bal
fele, válogatni, jobb fele, válogatni,

307
00:13:35,740 --> 00:13:39,120
és egyesíti a két együttes,
a néhány további hely,

308
00:13:39,120 --> 00:13:41,670
3 jön először, aztán jön 5.

309
00:13:41,670 --> 00:13:46,190
És így most, már válogatni a
bal fele a jobb fele

310
00:13:46,190 --> 00:13:49,420
az eredeti probléma, és
A jobb felét a jobb fél

311
00:13:49,420 --> 00:13:50,800
Az eredeti probléma.

312
00:13:50,800 --> 00:13:52,480
Mi a harmadik és egyben utolsó lépés?

313
00:13:52,480 --> 00:13:54,854
Nos, hogy összevonja a két fél együtt.

314
00:13:54,854 --> 00:13:57,020
Szóval hadd tegyem magam néhány
extra helyet foglalnak el, de én

315
00:13:57,020 --> 00:13:58,699
Lehet használni, hogy tartalék helyre fel tetején.

316
00:13:58,699 --> 00:14:00,490
De mi akarsz tartani
egyszerű szemrevételezéssel.

317
00:14:00,490 --> 00:14:07,070
Hadd úsznak most 1, és
majd 3, majd az 5, majd 7.

318
00:14:07,070 --> 00:14:10,740
Hagyva nekem most a
jobb fele az eredeti probléma

319
00:14:10,740 --> 00:14:12,840
Ez tökéletesen rendezett.

320
00:14:12,840 --> 00:14:13,662
>> Tehát mi marad?

321
00:14:13,662 --> 00:14:16,120
Úgy érzem, mondogatom a
Ugyanazokat a dolgokat újra, és újra,

322
00:14:16,120 --> 00:14:18,700
de ez tükrözi a
Tény, hogy mi használ rekurzió.

323
00:14:18,700 --> 00:14:21,050
A folyamat, amelynek során egy
algoritmus újra, és újra,

324
00:14:21,050 --> 00:14:23,940
A kisebb részhalmaza
Az eredeti probléma.

325
00:14:23,940 --> 00:14:27,580
Szóval most már egy bal rendezve
a fele az eredeti probléma.

326
00:14:27,580 --> 00:14:30,847
Jogom van a rendezett fele
Az eredeti probléma.

327
00:14:30,847 --> 00:14:32,180
Mi a harmadik és egyben utolsó lépés?

328
00:14:32,180 --> 00:14:33,590
Ó, ez összevonása.

329
00:14:33,590 --> 00:14:34,480
Tehát lássuk, hogy.

330
00:14:34,480 --> 00:14:36,420
Nézzük kiosztani néhány további
memória, de istenem, mi

331
00:14:36,420 --> 00:14:37,503
sodorhatják bárhol őt.

332
00:14:37,503 --> 00:14:40,356
Van annyi hely áll rendelkezésre
nekünk, de mi legyen egyszerű.

333
00:14:40,356 --> 00:14:42,730
Ahelyett, hogy oda-vissza
oda a mi eredeti memória,

334
00:14:42,730 --> 00:14:44,480
nézzük csak csináld
Akadálymentes ide alább,

335
00:14:44,480 --> 00:14:47,240
befejezni összevonásával
bal fele és a jobb fele.

336
00:14:47,240 --> 00:14:49,279
>> Szóval összevonásával, mit kell tennem?

337
00:14:49,279 --> 00:14:50,820
Azt akarom, hogy az elemek érdekében.

338
00:14:50,820 --> 00:14:53,230
Így nézett a bal fele,
Látom az első szám a 2.

339
00:14:53,230 --> 00:14:55,230
Nézem a jobb fele,
Látom az első szám

340
00:14:55,230 --> 00:14:58,290
1, így nyilván, amelyek
számú akarom tépni ki,

341
00:14:58,290 --> 00:15:00,430
és tedd az első az én végleges listát?

342
00:15:00,430 --> 00:15:01,449
Természetesen, 1.

343
00:15:01,449 --> 00:15:02,990
Most azt szeretném megkérdezni, hogy ugyanezt a kérdést.

344
00:15:02,990 --> 00:15:05,040
A bal fele, már
Még mindig megvan a 2-es szám.

345
00:15:05,040 --> 00:15:07,490
A jobb felét,
Megvan a 3-as szám.

346
00:15:07,490 --> 00:15:08,930
Melyiket szeretné választani?

347
00:15:08,930 --> 00:15:11,760
Természetesen, a 2 és
Most észre a jelöltek

348
00:15:11,760 --> 00:15:13,620
4 a bal oldalon, a 3. a jobb oldalon.

349
00:15:13,620 --> 00:15:15,020
Nézzük, persze, válassza ki a 3.

350
00:15:15,020 --> 00:15:18,020
Most a jelöltek 4.
a bal, 5 a jobb oldalon.

351
00:15:18,020 --> 00:15:19,460
Mi, persze, válassza a 4.

352
00:15:19,460 --> 00:15:21,240
6 bal, 5 a jobb oldalon.

353
00:15:21,240 --> 00:15:22,730
Mi, persze, válassza 5.

354
00:15:22,730 --> 00:15:25,020
6 a bal oldalon, a 7. a jobb oldalon.

355
00:15:25,020 --> 00:15:29,320
Úgy döntünk, 6, és aztán
válassza a 7, majd úgy döntünk, 8.

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

357
00:15:30,100 --> 00:15:34,370
>> Szóval rengeteg szó később,
csoportosítottad ezt a listát a nyolc elem

358
00:15:34,370 --> 00:15:38,450
egy listát egytől nyolc,
ami növeli minden egyes lépésnél,

359
00:15:38,450 --> 00:15:40,850
De vajon mennyi idő volt
ez visz minket erre.

360
00:15:40,850 --> 00:15:43,190
Hát én már szándékosan
eljárással készült dolgokat képileg

361
00:15:43,190 --> 00:15:46,330
Itt, hogy mi lehet a fajta
látja, vagy értékelik a divízió

362
00:15:46,330 --> 00:15:49,060
A hódító, ami történt.

363
00:15:49,060 --> 00:15:52,830
>> Sőt, ha visszatekintünk a nyomában,
Hagytam az összes ilyen szaggatott vonalak

364
00:15:52,830 --> 00:15:55,660
A távtartók, akkor,
fajta, lásd, fordított sorrendben,

365
00:15:55,660 --> 00:15:58,800
ha a fajta néz vissza
történelem most, az eredeti lista

366
00:15:58,800 --> 00:16:00,250
Természetesen, a 8-as méret.

367
00:16:00,250 --> 00:16:03,480
És akkor a korábban voltam,
foglalkozó két listáját 4-es méretű,

368
00:16:03,480 --> 00:16:08,400
majd négy lista 2-es méret,
majd nyolc listák 1-es méret.

369
00:16:08,400 --> 00:16:10,151
>> Mit is jelent ez,
fajta, emlékeztessem önöket?

370
00:16:10,151 --> 00:16:11,858
Nos, valóban, bármely
Az algoritmusok voltunk

371
00:16:11,858 --> 00:16:14,430
nézett eddig, ahol
szakadék, és oszd meg, és oszd meg,

372
00:16:14,430 --> 00:16:19,500
tartani, amelynek a dolgokat újra, és
ismét eredményezi ezt a közvélekedést.

373
00:16:19,500 --> 00:16:23,100
És így van valami
logaritmikus folyik itt.

374
00:16:23,100 --> 00:16:26,790
És ez nem elég log n, de
van egy logaritmikus alkatrész

375
00:16:26,790 --> 00:16:28,280
hogy amit az imént történt.

376
00:16:28,280 --> 00:16:31,570
>> Most nézzük meg, hogyan, hogy valójában.

377
00:16:31,570 --> 00:16:34,481
Szóval jelentkezzen n, ismét volt
nagy működési idő,

378
00:16:34,481 --> 00:16:36,980
amikor nem valami ilyesmi
bináris keresés, ahogy manapság nevezik,

379
00:16:36,980 --> 00:16:40,090
Az oszd meg és uralkodj stratégia
amelyen keresztül megtaláltuk Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Most technikailag.

381
00:16:41,020 --> 00:16:43,640
Ez log alap 2 n, akkor is,
Bár a legtöbb matematikai osztályok,

382
00:16:43,640 --> 00:16:45,770
10 Általában a bázis, amit vállal.

383
00:16:45,770 --> 00:16:48,940
De számítógépes szakemberek szinte mindig
gondolkodni és beszélni szempontjából alap 2,

384
00:16:48,940 --> 00:16:52,569
tehát általában csak annyit naplót
N, ahelyett, log bázis 2 N,

385
00:16:52,569 --> 00:16:55,110
de ők pontosan egy és
ugyanazt a világon a számítógépes

386
00:16:55,110 --> 00:16:57,234
a tudomány, és mint félre,
Van egy állandó tényező

387
00:16:57,234 --> 00:17:01,070
különbség a kettő között, így ez
vitathatónak egyébként, több formai okok miatt.

388
00:17:01,070 --> 00:17:04,520
>> De most, mi érdekel
körülbelül ez a példa.

389
00:17:04,520 --> 00:17:08,520
Szóval nem tudja bizonyítani a példa, de a
legalább használja egy példa a számok

390
00:17:08,520 --> 00:17:10,730
kéznél van, hiszen a józan csekket, ha úgy tetszik.

391
00:17:10,730 --> 00:17:14,510
Így a korábban a képlet volt, napló adatbázis
2 n, de mi n ebben az esetben.

392
00:17:14,510 --> 00:17:18,526
Volt n eredeti számokat, illetve 8
Az eredeti szám konkrétan.

393
00:17:18,526 --> 00:17:20,359
Most már egy kicsit
míg, de nem vagyok elég

394
00:17:20,359 --> 00:17:25,300
arról, hogy log 2 alap
Az érték 8 jelentése 3,

395
00:17:25,300 --> 00:17:29,630
sőt, mi szép erről van
hogy a 3 pontosan az a szám, ahányszor

396
00:17:29,630 --> 00:17:33,320
hogy lehet osztani egy listát
A hossza 8 újra, és újra,

397
00:17:33,320 --> 00:17:36,160
és újra, amíg te maradt
A listák csak 1-es méret.

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

399
00:17:36,660 --> 00:17:40,790
8 megy 4, megy a 2,
megy 1, és ez

400
00:17:40,790 --> 00:17:43,470
tükrözi pontosan, hogy
kép volt, csak egy pillanattal ezelőtt.

401
00:17:43,470 --> 00:17:47,160
Szóval egy kis józanság ellenőrizze, hogy hol
A logaritmus valójában szó.

402
00:17:47,160 --> 00:17:50,180
>> Tehát most, mi más van itt szó? n.

403
00:17:50,180 --> 00:17:53,440
Tehát észre, hogy minden
Mire szét a listán,

404
00:17:53,440 --> 00:17:58,260
bár fordított sorrendben a történelemben
Itt voltam, mindig csinál n dolgokat.

405
00:17:58,260 --> 00:18:02,320
Beolvadása a lépés szükséges, hogy
Én miden egyik szám,

406
00:18:02,320 --> 00:18:05,060
annak érdekében, hogy tolja azt a
a megfelelő helyre.

407
00:18:05,060 --> 00:18:10,760
Így bár a magassága ezen
rajz mérete log n n vagy 3,

408
00:18:10,760 --> 00:18:13,860
Konkrétabban, más szóval,
Én három hadosztály itt.

409
00:18:13,860 --> 00:18:18,800
Mennyi munkát csináltam vízszintesen
végig ezt a táblázatot minden egyes alkalommal?

410
00:18:18,800 --> 00:18:21,110
>> Nos, én n lépései
dolgozni, mert ha én már

411
00:18:21,110 --> 00:18:24,080
Van négy elem és a négy elemet,
és azt kell egyesíteni őket együtt.

412
00:18:24,080 --> 00:18:26,040
Azt kell átmenni
E négy és ez a négy,

413
00:18:26,040 --> 00:18:28,123
végül egyesíteni őket
vissza nyolc elem.

414
00:18:28,123 --> 00:18:32,182
Ha fordítva Megvan a nyolc ujját
mint itt, amit nem, és nyolc

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry--, ha már
Van négy ujj ide,

416
00:18:34,390 --> 00:18:37,380
amit teszek, négy ujj
mint itt, amit csinál,

417
00:18:37,380 --> 00:18:40,590
akkor ez ugyanaz
Például, mint korábban, ha megteszem

418
00:18:40,590 --> 00:18:44,010
nyolc ujját bár
teljes, amit tud, egyfajta tegye.

419
00:18:44,010 --> 00:18:47,950
Én is pontosan itt,
akkor én is biztosan

420
00:18:47,950 --> 00:18:50,370
egyesíti az összes ilyen listák
Az 1-es méretű össze.

421
00:18:50,370 --> 00:18:54,050
De természetesen meg kell nézni
minden eleme pontosan egyszer.

422
00:18:54,050 --> 00:18:59,640
Tehát a magassága ez a folyamat log n,
a szélessége e folyamat, hogy úgy mondjuk,

423
00:18:59,640 --> 00:19:02,490
n, akkor mi úgy tűnik,
hogy végső soron az,

424
00:19:02,490 --> 00:19:06,470
futásidejű méretű n-szer log n.

425
00:19:06,470 --> 00:19:08,977
>> Más szavakkal, mi osztva
A lista log n-szer,

426
00:19:08,977 --> 00:19:11,810
de minden egyes alkalommal tettük, hogy mi volt
hogy miden egyik eleme

427
00:19:11,810 --> 00:19:13,560
annak érdekében, hogy egyesíti őket
minden együtt, ami

428
00:19:13,560 --> 00:19:18,120
az n lépés, így már n-szer log n,
vagy mint egy számítógép tudós azt mondaná,

429
00:19:18,120 --> 00:19:20,380
aszimptotikusan, amely
lenne a nagy szó

430
00:19:20,380 --> 00:19:22,810
leírni a felső
köti a működési idő,

431
00:19:22,810 --> 00:19:28,010
mi fut egy nagy o
log n idő, hogy úgy mondjam.

432
00:19:28,010 --> 00:19:31,510
>> Most ez jelentős, mert
felidézni, amit a futási idők voltak

433
00:19:31,510 --> 00:19:34,120
buborék rendezés, és a kiválasztás
rendezése és beillesztés sort,

434
00:19:34,120 --> 00:19:38,200
és még néhány más, hogy létezik,
n faragva volt, ahol voltunk.

435
00:19:38,200 --> 00:19:39,990
És tudod, milyen, nézd meg ezt itt.

436
00:19:39,990 --> 00:19:45,720
Ha n faragva nyilvánvalóan n-szer
n, de itt van n-szer log n,

437
00:19:45,720 --> 00:19:48,770
és már tudjuk hétről
zero, log n, a logaritmikus,

438
00:19:48,770 --> 00:19:50,550
jobb, mint valami lineáris.

439
00:19:50,550 --> 00:19:52,930
Végtére is, emlékszem a kép
A piros és a sárga

440
00:19:52,930 --> 00:19:56,500
és a zöld vonalak felhívtuk a
zöld logaritmikus vonal sokkal alacsonyabb volt.

441
00:19:56,500 --> 00:20:00,920
És ezért sokkal jobban és gyorsabban
mint az egyenes sárga és piros vonalak,

442
00:20:00,920 --> 00:20:05,900
n-szer log n is, sőt, jobb,
mint n-szer n vagy N négyzeten.

443
00:20:05,900 --> 00:20:09,110
>> Tehát úgy tűnik, hogy
azonosított egy algoritmus merge

444
00:20:09,110 --> 00:20:11,870
Rendezés futó sokat
gyorsabb, és valóban,

445
00:20:11,870 --> 00:20:16,560
ezért, a hét elején, amikor
láttuk, hogy verseny között buborék

446
00:20:16,560 --> 00:20:20,750
rendezés, kiválasztás sort, és egyesíti
rendezés, merge sort nagyon, nagyon megnyerte.

447
00:20:20,750 --> 00:20:23,660
És valóban, mi sem várta
A buborékos rendezést és kiválasztási sorrend

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

449
00:20:24,790 --> 00:20:27,410
>> Most vessünk egy másik menetben
ezen, egy valamivel több

450
00:20:27,410 --> 00:20:31,030
Formális szempontból, csak a
esetben ez rezonál jobban

451
00:20:31,030 --> 00:20:33,380
mint hogy a magasabb szintű vitát.

452
00:20:33,380 --> 00:20:34,880
Tehát itt az algoritmus újra.

453
00:20:34,880 --> 00:20:36,770
Kérdezzük magunkat,
amit a futási idő

454
00:20:36,770 --> 00:20:39,287
az ezen algoritmusok különböző lépések?

455
00:20:39,287 --> 00:20:41,620
Nézzük osszuk az első
ügy és a második esetben.

456
00:20:41,620 --> 00:20:46,280
A BA és a máshol a HA esetben,
Ha n kevesebb, mint 2, csak vissza.

457
00:20:46,280 --> 00:20:47,580
Olyan, mint a folyamatos időt.

458
00:20:47,580 --> 00:20:50,970
Ez, a fajta, mint a két lépést,
Ha n kevesebb, mint 2, majd vissza.

459
00:20:50,970 --> 00:20:54,580
De ahogy mondta hétfőn,
konstans időben, vagy nagy o 1,

460
00:20:54,580 --> 00:20:57,130
lehet két lépésben, három
lépéseket, még 1000 lépéseket.

461
00:20:57,130 --> 00:20:59,870
A fontos az, hogy ez az
konstans számú lépést.

462
00:20:59,870 --> 00:21:03,240
Tehát a sárga kiemelt pszeudokódja
Itt fut, hívjuk meg,

463
00:21:03,240 --> 00:21:04,490
konstans időt.

464
00:21:04,490 --> 00:21:06,780
Tehát formálisan, és
megyünk az alábbiakra: ezt

465
00:21:06,780 --> 00:21:09,910
lesz, hogy milyen mértékben mi
hivatalossá ezt a jogot now-- T n,

466
00:21:09,910 --> 00:21:15,030
A működési idő a probléma
vevő n asok a bemenet,

467
00:21:15,030 --> 00:21:19,150
egyenlő nagy o egy,
Ha n kevesebb, mint 2.

468
00:21:19,150 --> 00:21:20,640
Szóval ez feltétele, hogy.

469
00:21:20,640 --> 00:21:24,150
Tehát, hogy világos legyen, ha n kisebb, mint
2, van egy nagyon rövid lista, akkor

470
00:21:24,150 --> 00:21:29,151
a futási idő, T n, ahol n értéke
1 vagy 0, ebben a nagyon különleges esetben,

471
00:21:29,151 --> 00:21:30,650
ez csak lesz állandó időt.

472
00:21:30,650 --> 00:21:32,691
Ez lesz, hogy az egyik
lépésre, két lépésben, mindegy.

473
00:21:32,691 --> 00:21:33,950
Ez egy fix számú lépést.

474
00:21:33,950 --> 00:21:38,840
>> Tehát a szaftos része bizonyosan a
A másik esetben a pszeudokódja.

475
00:21:38,840 --> 00:21:40,220
Az else ügyben.

476
00:21:40,220 --> 00:21:44,870
Rendezés bal fele elemek, egyfajta jobb
fele elemek, összeolvad a rendezett félidőt.

477
00:21:44,870 --> 00:21:46,800
Mennyi ideig tart minden ilyen lépést tartani?

478
00:21:46,800 --> 00:21:49,780
Nos, ha a futó
a rendezés n elemek

479
00:21:49,780 --> 00:21:53,010
van, nevezzük nagyon
generikusan, T n,

480
00:21:53,010 --> 00:21:55,500
majd válogatás a bal
fele az elemek

481
00:21:55,500 --> 00:21:59,720
van, olyan, mintha azt mondanánk,
T n osztva 2,

482
00:21:59,720 --> 00:22:03,000
és hasonlóan válogatás a jobb fele
Az elemek, a fajta, mintha azt mondanánk,

483
00:22:03,000 --> 00:22:06,974
T n osztva a 2, majd
összevonásával rendezve félidőt.

484
00:22:06,974 --> 00:22:08,890
Nos, ha van pár
elemek száma itt,

485
00:22:08,890 --> 00:22:11,230
mint a négy, és néhány szám
Az elemek itt, mint négy,

486
00:22:11,230 --> 00:22:14,650
és azt kell egyesíteni mind a négy
-ban, és minden egyes ilyen négy, az egyik

487
00:22:14,650 --> 00:22:17,160
a másik után, úgy, hogy
végső soron azt kell nyolc elem.

488
00:22:17,160 --> 00:22:20,230
Olyan, mintha ez nagy o n lépéseket?

489
00:22:20,230 --> 00:22:23,500
Ha megvan n ujjait és az egyes
nekik kell egyesíteni a helyére,

490
00:22:23,500 --> 00:22:25,270
ez olyan, mint egy másik n lépéseket.

491
00:22:25,270 --> 00:22:27,360
>> Tehát valóban formulaically,
tudjuk fejezni ezt,

492
00:22:27,360 --> 00:22:29,960
ámbátor kissé ijesztően első
pillantásra, de ez valami

493
00:22:29,960 --> 00:22:31,600
amely rávilágít, hogy pontosan logika.

494
00:22:31,600 --> 00:22:35,710
A működési idő, T n, ha n
nagyobb mint vagy egyenlő 2.

495
00:22:35,710 --> 00:22:42,500
Ebben az esetben, az ELSE esetben T n
osztva 2, plusz a T N osztva 2,

496
00:22:42,500 --> 00:22:45,320
plusz nagy o n, néhány
lineáris lépések számát,

497
00:22:45,320 --> 00:22:51,630
Talán pontosan n, talán 2-szer
n, de ez durván, sorrendben n.

498
00:22:51,630 --> 00:22:54,060
Szóval, hogy is, hogy miként lehet
kifejezni ezt formulaically.

499
00:22:54,060 --> 00:22:56,809
Most azt nem tudom, ezt, hacsak
amit felvett a fejedben,

500
00:22:56,809 --> 00:22:58,710
vagy keresse fel a
vissza a tankönyv, hogy

501
00:22:58,710 --> 00:23:00,501
Lehet, hogy egy kicsit
csalni lap végén,

502
00:23:00,501 --> 00:23:03,940
de ez valóban megy
ad nekünk egy nagy o n log n,

503
00:23:03,940 --> 00:23:06,620
mert a kiújulás
látsz itt a képernyőn,

504
00:23:06,620 --> 00:23:09,550
ha ténylegesen ki, a
végtelen számú példák,

505
00:23:09,550 --> 00:23:13,000
vagy megcsináltad formulaically, akkor
látni, hogy ezt, mert ez a képlet

506
00:23:13,000 --> 00:23:17,100
Maga rekurzív, a t
n át valami jobb,

507
00:23:17,100 --> 00:23:21,680
és t n át a bal oldalon, ez lehet
ténylegesen kifejezhető, végső soron,

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

509
00:23:24,339 --> 00:23:26,130
Ha nem győzte, ez
finom most, csak

510
00:23:26,130 --> 00:23:28,960
hogy a hit, hogy ez valóban,
hogy ez mit megismétlődését vezet,

511
00:23:28,960 --> 00:23:31,780
de ez csak egy kicsit nagyobb
matematikai megközelítése keres

512
00:23:31,780 --> 00:23:36,520
a menetideje merge sort
alapuló pszeudokód egyedül.

513
00:23:36,520 --> 00:23:39,030
>> Most vessünk egy kicsit
visszavezető minden adott,

514
00:23:39,030 --> 00:23:41,710
és vessen egy pillantást a
bizonyos korábbi szenátor, aki

515
00:23:41,710 --> 00:23:44,260
Lehet nézni egy kicsit ismerős,
aki leült a Google Eric

516
00:23:44,260 --> 00:23:48,410
Schmidt, néhány évvel ezelőtt, egy interjú
a színpadon, előtte egy csomó

517
00:23:48,410 --> 00:23:53,710
emberek, beszél végső soron
egy témát, hogy elég már jól ismert.

518
00:23:53,710 --> 00:23:54,575
Vessünk egy pillantást.

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

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt: Most szenátor,
vagy itt a Google-nál,

521
00:24:03,890 --> 00:24:09,490
és szeretem azt hinni, a
elnökség, mint egy állásinterjú.

522
00:24:09,490 --> 00:24:11,712
Most nehéz munkát találni, mint elnök.

523
00:24:11,712 --> 00:24:12,670
Obama elnök: Így van.

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt: És te
fog tenni [hallhatatlan] most.

525
00:24:13,940 --> 00:24:15,523
Ez is nehéz munkát találni a Google-nál.

526
00:24:15,523 --> 00:24:17,700
Obama elnök: Így van.

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt: Van kérdésekre,
és kéri, hogy a jelöltek kérdéseket,

528
00:24:21,330 --> 00:24:24,310
és ez az egyik a Larry Schwimmer.

529
00:24:24,310 --> 00:24:25,890
>> Obama elnök: OK.

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

531
00:24:27,005 --> 00:24:28,130
Azt hiszitek, viccelek?

532
00:24:28,130 --> 00:24:30,590
Itt van.

533
00:24:30,590 --> 00:24:33,490
Mi a leghatékonyabb módja annak, hogy
rendezni egy millió 32 bites egész?

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

535
00:24:37,560 --> 00:24:38,979
>> Obama elnök: Well--

536
00:24:38,979 --> 00:24:41,020
Eric Schmidt: Néha,
Talán Sajnálom, maybe--

537
00:24:41,020 --> 00:24:42,750
Obama elnök: Nem, nem,
nem, nem, nem, én think--

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt: Ez nem it--

539
00:24:43,240 --> 00:24:45,430
Obama elnök: Én
gondolom, azt hiszem, a buborék

540
00:24:45,430 --> 00:24:46,875
Rendezés lenne rossz irányba menni.

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

542
00:24:49,619 --> 00:24:50,535
Eric Schmidt: Gyerünk.

543
00:24:50,535 --> 00:24:52,200
Ki mondta ezt neki?

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

545
00:24:54,020 --> 00:24:55,590
Én nem a számítógép-tudomány on--

546
00:24:55,590 --> 00:24:58,986
>> Obama elnök: kaptunk
Megvan a kémek vannak.

547
00:24:58,986 --> 00:24:59,860
Tanár: Rendben.

548
00:24:59,860 --> 00:25:03,370
Hagyjuk magunk mögött most a
elméleti világa algoritmusok

549
00:25:03,370 --> 00:25:06,520
A aszimptotikus elemzés
pontjára, és térjen vissza néhány téma

550
00:25:06,520 --> 00:25:09,940
hétről nulla és egy, a start
hogy távolítsa el néhány képzés kerekek,

551
00:25:09,940 --> 00:25:10,450
ha úgy tetszik.

552
00:25:10,450 --> 00:25:13,241
Úgy, hogy valóban megértsék
végső soron az alapoktól kezdve, mi

553
00:25:13,241 --> 00:25:16,805
folyik a motorháztető alatt, ha
levelet, összeállítják, és végre programokat.

554
00:25:16,805 --> 00:25:19,680
Emlékezzünk különösen, hogy ez volt
Az első C program néztük,

555
00:25:19,680 --> 00:25:22,840
kanonikus, egyszerű program
a fajta, viszonylag szerény,

556
00:25:22,840 --> 00:25:24,620
ahol, kinyomtatja, Hello World.

557
00:25:24,620 --> 00:25:27,610
És emlékszem, hogy azt mondtam, a folyamat
hogy a forráskód megy keresztül

558
00:25:27,610 --> 00:25:28,430
Pontosan ez az.

559
00:25:28,430 --> 00:25:31,180
Veszel a forráskódot, át
ez egy fordító, mint csenget,

560
00:25:31,180 --> 00:25:34,650
és ki jön tárgykód, hogy
így nézhet ki, nullák

561
00:25:34,650 --> 00:25:37,880
hogy a számítógép CPU, központi
feldolgozó egység vagy agy,

562
00:25:37,880 --> 00:25:39,760
végül megérti.

563
00:25:39,760 --> 00:25:42,460
>> Kiderül, hogy ez egy
kicsit túlzott leegyszerűsítés,

564
00:25:42,460 --> 00:25:44,480
hogy mi most egy
helyzetben, hogy ugratni egymástól

565
00:25:44,480 --> 00:25:46,720
megérteni, hogy mi volt igazán
folyik a motorháztető alatt

566
00:25:46,720 --> 00:25:48,600
minden indítás
Csengés, vagy általánosabban,

567
00:25:48,600 --> 00:25:53,040
Minden alkalommal, amikor egy programot,
felhasználásával készítsünk és CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
Különösen, ilyesmi
ez az első generált,

569
00:25:56,760 --> 00:25:58,684
amikor először fordítsa le a programot.

570
00:25:58,684 --> 00:26:00,600
Más szavakkal, ha
hogy a forráskód

571
00:26:00,600 --> 00:26:04,390
és lefordítani, akkor mi az első
hogy outputted által csenget

572
00:26:04,390 --> 00:26:06,370
valami ismert assembly kódot.

573
00:26:06,370 --> 00:26:08,990
És valóban, úgy néz ki, mint ez.

574
00:26:08,990 --> 00:26:11,170
>> Futottam egy parancsot a
parancssori korábban.

575
00:26:11,170 --> 00:26:16,260
Clang kötőjel tőke s hello.c,
és ez teremtett egy fájlt

576
00:26:16,260 --> 00:26:19,490
Nekem nevű hello.s,
belsejében amelyek pontosan

577
00:26:19,490 --> 00:26:22,290
ezek a tartalmak, és egy kicsit több
felett, és egy kicsit több, az alábbiakban,

578
00:26:22,290 --> 00:26:25,080
de tettem a juiciest
információk itt a képernyőn.

579
00:26:25,080 --> 00:26:29,190
És ha jobban megnézed, látni fogod
legalább néhány ismerős kulcsszavakat.

580
00:26:29,190 --> 00:26:31,330
Van fő tetején.

581
00:26:31,330 --> 00:26:35,140
Mi már printf le a közepén.

582
00:26:35,140 --> 00:26:38,670
És mi is hello world
backslash n idézőjelbe lent.

583
00:26:38,670 --> 00:26:42,450
>> És itt minden
nagyon alacsony szintű utasítások

584
00:26:42,450 --> 00:26:45,500
hogy a számítógép CPU megérti.

585
00:26:45,500 --> 00:26:50,090
CPU utasításokat, hogy mozog a memória
körül, hogy terhelés húrok a memóriából,

586
00:26:50,090 --> 00:26:52,750
és végül, a nyomtatási
dolgokat a képernyőn.

587
00:26:52,750 --> 00:26:56,780
Most mi történik, bár után
ez a szerelvény kódot generál?

588
00:26:56,780 --> 00:26:59,964
Végső soron, akkor nem, sőt,
továbbra is generálnak tárgykód.

589
00:26:59,964 --> 00:27:02,630
De a lépéseket, amelyek valóban
óta folyik a motorháztető alatt

590
00:27:02,630 --> 00:27:04,180
nézni egy kicsit, mint ez.

591
00:27:04,180 --> 00:27:08,390
Forráskód válik assembly kódot,
ami aztán lesz tárgyi kód

592
00:27:08,390 --> 00:27:11,930
és az operatív szó itt, hogy
amikor fordítod a forráskódot,

593
00:27:11,930 --> 00:27:16,300
ki jön assembly kód, majd
ha össze a gyülekezési kódot,

594
00:27:16,300 --> 00:27:17,800
ki jön tárgykód.

595
00:27:17,800 --> 00:27:20,360
>> Most Clang szuper kifinomult,
mint a sok fordítóprogramok,

596
00:27:20,360 --> 00:27:23,151
és ez nem az összes ezeket a lépéseket
együtt, és ez nem feltétlenül

597
00:27:23,151 --> 00:27:25,360
kimeneti valamennyi közbenső
fájlokat lehet még látni.

598
00:27:25,360 --> 00:27:28,400
Csak lefordul a dolgokat,
amely olyan általános kifejezés, amely

599
00:27:28,400 --> 00:27:30,000
leírja a teljes folyamatot.

600
00:27:30,000 --> 00:27:32,000
De ha igazán akar
hogy különösen ott

601
00:27:32,000 --> 00:27:34,330
sokkal több folyik ott is.

602
00:27:34,330 --> 00:27:38,860
>> De nézzük is úgy most, hogy még
hogy szuper egyszerű program, hello.c,

603
00:27:38,860 --> 00:27:40,540
nevű függvény.

604
00:27:40,540 --> 00:27:41,870
Felszólította printf.

605
00:27:41,870 --> 00:27:46,900
De nem én írtam printf, sőt,
hogy jön c, hogy úgy mondjam.

606
00:27:46,900 --> 00:27:51,139
Ez egy funkciót emlékeztetnek arra, hogy az
bejelentett szabvány io.h, amely

607
00:27:51,139 --> 00:27:53,180
egy header fájl, ami
egy olyan téma, akkor tulajdonképpen

608
00:27:53,180 --> 00:27:55,780
belevetik magukat mélyebben nemsokára.

609
00:27:55,780 --> 00:27:58,000
De a fejléc fájl
jellemzően együtt

610
00:27:58,000 --> 00:28:02,920
egy kód fájlt, forráskód fájlt, így
hasonlóan létezik szabvány io.h.

611
00:28:02,920 --> 00:28:05,930
>> Valamikor ezelőtt valaki,
vagy valakiknek is írt

612
00:28:05,930 --> 00:28:11,040
nevű fájl szabvány io.c, a
amely a tényleges definíciók,

613
00:28:11,040 --> 00:28:15,220
vagy megvalósítások printf,
és csokor egyéb funkciók,

614
00:28:15,220 --> 00:28:16,870
ténylegesen leírt.

615
00:28:16,870 --> 00:28:22,140
Tehát mivel, ha arra gondolunk, amelynek
Itt a bal oldalon, hello.c, hogy amikor

616
00:28:22,140 --> 00:28:26,250
összeállított, ad nekünk hello.s, akkor is, ha
Csengés nem zavar megtakarítás egy helyen

617
00:28:26,250 --> 00:28:31,360
látjuk azt, és assembly kód
lesz összeállítva hello.o, amely

618
00:28:31,360 --> 00:28:34,630
Valóban, az alapértelmezett név
nyújtására, amikor fordítod forrás

619
00:28:34,630 --> 00:28:39,350
kódot tárgykód, de nem
teljesen kész végrehajtani még,

620
00:28:39,350 --> 00:28:41,460
mert újabb lépés
meg kell történnie, és

621
00:28:41,460 --> 00:28:44,440
történt az elmúlt pár
hétig, esetleg tudtán kívül van.

622
00:28:44,440 --> 00:28:47,290
>> Különösen valahol
A CS50 IDE, és ez,

623
00:28:47,290 --> 00:28:49,870
is lesz egy kicsit egy
leegyszerűsítés egy pillanatra,

624
00:28:49,870 --> 00:28:54,670
van, vagy volt, hol nem volt,
nevű fájl szabvány io.c,

625
00:28:54,670 --> 00:28:58,440
hogy valaki fordítva
szabvány io.s vagy az azzal egyenértékű,

626
00:28:58,440 --> 00:29:02,010
hogy valaki majd össze
szabványos io.o,

627
00:29:02,010 --> 00:29:04,600
vagy kiderül, egy
kicsit más fájl

628
00:29:04,600 --> 00:29:07,220
formában, hogy lehet más
fájl kiterjesztését összesen,

629
00:29:07,220 --> 00:29:11,720
de elméletileg és fogalmilag pontosan
ezeket a lépéseket meg kellett történnie valamilyen formában.

630
00:29:11,720 --> 00:29:14,060
Ami azt jelenti, hogy most
ha írok egy programot,

631
00:29:14,060 --> 00:29:17,870
hello.c, hogy csak azt mondja, hello world,
és én vagyok a valaki másnak a kódját

632
00:29:17,870 --> 00:29:22,480
mint a printf, ami egyszer volt, hol
ideje, nevű fájlt szabványos io.c,

633
00:29:22,480 --> 00:29:26,390
aztán valahogy el kell vennem az én
tárgykód, én nullák,

634
00:29:26,390 --> 00:29:29,260
és annak a személynek a tárgy
kódot, vagy nullák,

635
00:29:29,260 --> 00:29:34,970
és valahogy össze őket össze
Egy utolsó file, hello, hogy

636
00:29:34,970 --> 00:29:38,070
az összes nullák és
azok az én fő funkciója,

637
00:29:38,070 --> 00:29:40,830
és az összes nullák
és azok a printf.

638
00:29:40,830 --> 00:29:44,900
>> És valóban, az utolsó folyamat
nevű, összekapcsolja a tárgykód.

639
00:29:44,900 --> 00:29:47,490
Amelynek kimenete
egy futtatható fájl.

640
00:29:47,490 --> 00:29:49,780
Tehát a méltányosság, a
A nap végén, semmi

641
00:29:49,780 --> 00:29:52,660
óta változott a héten az egyik, amikor
először kezdett összeállítása programok.

642
00:29:52,660 --> 00:29:55,200
Valóban, az összes ez volt
történik a motorháztető alatt,

643
00:29:55,200 --> 00:29:57,241
de most mi vagyunk abban a helyzetben,
ahol tudunk valójában

644
00:29:57,241 --> 00:29:58,794
ugratni egymástól a különböző lépéseket.

645
00:29:58,794 --> 00:30:00,710
És valóban, a végén
A nap, még mindig

646
00:30:00,710 --> 00:30:04,480
maradt nullák, amelyek
valójában egy nagy Segue most

647
00:30:04,480 --> 00:30:08,620
egy másik képessége C, hogy
mi már nem volt képes mozgósítani a legvalószínűbb

648
00:30:08,620 --> 00:30:11,250
a mai napig, az úgynevezett bitműveletek.

649
00:30:11,250 --> 00:30:15,220
Más szóval, eddig, bármikor mi ve
foglalkozott az adatokat a C vagy C változók,

650
00:30:15,220 --> 00:30:17,660
mi már voltak dolgok, mint
karakter és úszók és modulok

651
00:30:17,660 --> 00:30:21,990
és vágyik és páros és a hasonló, de
az összes ilyen legalább nyolc bit.

652
00:30:21,990 --> 00:30:25,550
Mi soha nem sikerült még
manipulálni egyes biteket,

653
00:30:25,550 --> 00:30:28,970
annak ellenére, hogy az egyén kicsit, mi
tudható, hogy képviselje a 0 és 1.

654
00:30:28,970 --> 00:30:32,640
Most kiderül, hogy a C, akkor
kaphat hozzáférést az egyes biteket,

655
00:30:32,640 --> 00:30:35,530
Ha tudod, hogy a szintaxis,
amellyel kap rájuk.

656
00:30:35,530 --> 00:30:38,010
>> Szóval vessünk egy pillantást
A bitműveletek.

657
00:30:38,010 --> 00:30:41,700
Tehát képen itt van néhány szimbólum, amely
mi már, milyen, fajta, látott.

658
00:30:41,700 --> 00:30:45,580
Látok egy jelet, egy függőleges
bár, és mások is,

659
00:30:45,580 --> 00:30:49,430
és emlékszem, hogy jelet jelet
van valami, amit eddig láttunk.

660
00:30:49,430 --> 00:30:54,060
A logikai ÉS operátor, ahol van,
ketten együtt, vagy a logikai VAGY

661
00:30:54,060 --> 00:30:56,300
üzemben, ahol
két függőleges rúd.

662
00:30:56,300 --> 00:31:00,550
Bitműveletek, amit majd
lásd működnek bit egyénileg,

663
00:31:00,550 --> 00:31:03,810
csak használ egy jelet, egy
Egyetlen függőleges vonal, a kalap szimbólum

664
00:31:03,810 --> 00:31:06,620
következik, a kis
tilde, majd balra

665
00:31:06,620 --> 00:31:08,990
konzol bal oldali konzol, vagy
szögletes zárójel szögletes zárójel.

666
00:31:08,990 --> 00:31:10,770
Mindegyik más-más jelentése van.

667
00:31:10,770 --> 00:31:11,950
>> Tény, hogy vessünk egy pillantást.

668
00:31:11,950 --> 00:31:16,560
Menjünk régi iskola ma, és felhasználása
érintőképernyős származó múlt,

669
00:31:16,560 --> 00:31:18,002
néven ismert fehér tábla.

670
00:31:18,002 --> 00:31:19,710
És ez a fehér tábla
fog lehetővé teszi számunkra,

671
00:31:19,710 --> 00:31:27,360
kifejezni néhány meglehetősen egyszerű szimbólumok,
vagy inkább néhány meglehetősen egyszerű képletek,

672
00:31:27,360 --> 00:31:29,560
hogy mi lehet majd a végső
tőkeáttétel, annak érdekében,

673
00:31:29,560 --> 00:31:33,230
eléréséhez az egyéni
bitek egy C program.

674
00:31:33,230 --> 00:31:34,480
Más szóval, csináljuk ezt.

675
00:31:34,480 --> 00:31:37,080
Először essék egy
pillanatra jelet,

676
00:31:37,080 --> 00:31:39,560
amely a bitenkénti ÉS operátor.

677
00:31:39,560 --> 00:31:42,130
Más szavakkal, ez az
az üzemben, amely lehetővé teszi

678
00:31:42,130 --> 00:31:45,930
nekem van egy bal oldali változó
jellemzően, és a jobb oldali változó,

679
00:31:45,930 --> 00:31:50,640
vagy egy egyedi értéket, hogy ha mi és
őket, ad nekem egy végeredményt.

680
00:31:50,640 --> 00:31:51,560
Szóval mit gondolok?

681
00:31:51,560 --> 00:31:54,840
Ha egy program, van egy változó
amely tárolja a következő értékek egyikét,

682
00:31:54,840 --> 00:31:58,000
vagy nézzük, hogy ez egyszerű, és csak
kiírja nullák egyénileg,

683
00:31:58,000 --> 00:32:00,940
Íme a jelet üzemeltető működik.

684
00:32:00,940 --> 00:32:06,400
0-jel 0 lesz egyenlő 0.

685
00:32:06,400 --> 00:32:07,210
Most miért van ez?

686
00:32:07,210 --> 00:32:09,291
>> Ez nagyon hasonlít a
Logikai kifejezések,

687
00:32:09,291 --> 00:32:10,540
hogy már tárgyalt eddig.

688
00:32:10,540 --> 00:32:15,800
Ha úgy gondolja, elvégre a 0
hamis, 0 hamis, hamis és téves

689
00:32:15,800 --> 00:32:18,720
van, ahogy már tárgyalt
logikailag is hamis.

690
00:32:18,720 --> 00:32:20,270
Így kapunk 0 itt is.

691
00:32:20,270 --> 00:32:24,390
Ha az előírtnál 0-jel
1, nos ez is

692
00:32:24,390 --> 00:32:29,890
lesz 0, mert erre
bal oldali kifejezés, hogy igaz legyen, vagy 1,

693
00:32:29,890 --> 00:32:32,360
lenne szükség ahhoz, hogy igaz és valódi.

694
00:32:32,360 --> 00:32:36,320
De itt van a hamis
és igaz, vagy 0 és 1.

695
00:32:36,320 --> 00:32:42,000
Most újra, ha van 1-jel
0, ez is lesz 0,

696
00:32:42,000 --> 00:32:47,240
és ha van 1-jel 1,
Végül van még egy 1 bites.

697
00:32:47,240 --> 00:32:50,340
Más szóval, mi nem csinál
valami érdekes, hogy ennek az üzemeltető

698
00:32:50,340 --> 00:32:51,850
csak még, ez az & karakter üzemeltető.

699
00:32:51,850 --> 00:32:53,780
Ez a bitenkénti ÉS operátor.

700
00:32:53,780 --> 00:32:57,290
De ezek az összetevők
amelyen keresztül meg tudjuk csinálni

701
00:32:57,290 --> 00:32:59,240
Érdekes dolog, ahogy hamarosan látni.

702
00:32:59,240 --> 00:33:02,790
>> Most nézzük meg, csak az egységes
függőleges sáv felett van a jobb oldalon.

703
00:33:02,790 --> 00:33:06,710
Ha van egy 0 és én kicsit
VAGY azt, bitenkénti

704
00:33:06,710 --> 00:33:11,030
VAGY operátor, a másik 0 bit,
hogy fog adni nekem 0.

705
00:33:11,030 --> 00:33:17,540
Ha én 0 darab és OR azt
1 kicsit, aztán megyek kap 1.

706
00:33:17,540 --> 00:33:19,830
És valóban, csak
egyértelműség, hadd menjen vissza,

707
00:33:19,830 --> 00:33:23,380
hogy az én függőleges vonalak
nem tévednek az 1-es.

708
00:33:23,380 --> 00:33:26,560
Hadd írjam át az összes
én 1 egy kicsit

709
00:33:26,560 --> 00:33:32,700
egyértelműen, hogy mi lesz ezután, ha én
van egy 1 vagy 0, hogy lesz egy 1,

710
00:33:32,700 --> 00:33:39,060
és ha van egy 1 vagy 1, hogy
is lesz egy 1.

711
00:33:39,060 --> 00:33:42,900
Tehát látható, logikusan, hogy az OR
üzemeltető viselkedik nagyon eltérő.

712
00:33:42,900 --> 00:33:48,070
Ez ad nekem 0 vagy 0 ad nekem 0, de
Minden más kombináció ad nekem 1.

713
00:33:48,070 --> 00:33:52,480
Mindaddig, amíg van egy 1 a
általános képletű, az eredmény lesz 1.

714
00:33:52,480 --> 00:33:55,580
>> Ezzel szemben az ÉS
üzemeltető, a jelet,

715
00:33:55,580 --> 00:34:00,940
csak akkor, ha van két 1-esek
egyenletet, tudom tényleg kap egy 1 out.

716
00:34:00,940 --> 00:34:02,850
Most van néhány más
üzemeltetők is.

717
00:34:02,850 --> 00:34:04,810
Ezek közül az egyik egy kicsit nagyobb szerepet.

718
00:34:04,810 --> 00:34:07,980
Szóval hadd menjen előre, és törli
ezt, hogy szabadítson fel helyet.

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

720
00:34:13,020 --> 00:34:16,460
És vessünk egy pillantást a
kalap szimbólum, csak egy pillanatra.

721
00:34:16,460 --> 00:34:18,210
Ez tipikusan egy
karaktert beírhatja

722
00:34:18,210 --> 00:34:21,420
a billentyűzeten Shift és
Ezután az egyik szám tetején, a US

723
00:34:21,420 --> 00:34:22,250
billentyűzet.

724
00:34:22,250 --> 00:34:26,190
>> Tehát ez az exkluzív
VAGY operátor, exkluzív VAGY.

725
00:34:26,190 --> 00:34:27,790
Tehát most láttam a VAGY operátor.

726
00:34:27,790 --> 00:34:29,348
Ez a ERCW.

727
00:34:29,348 --> 00:34:30,639
Mi valójában a különbség?

728
00:34:30,639 --> 00:34:34,570
Nos nézzük csak nézd meg a képletet,
és ezt összetevőként végül.

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

730
00:34:37,690 --> 00:34:39,650
Azt fogom mondani mindig 0.

731
00:34:39,650 --> 00:34:41,400
Ez a meghatározás a XOR.

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

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 lesz 1,
és 1 XOR 1 lesz?

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

735
00:34:59,890 --> 00:35:00,520
Vagy nem?

736
00:35:00,520 --> 00:35:01,860
Nem tudom.

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

738
00:35:02,810 --> 00:35:04,700
Most mi folyik itt?

739
00:35:04,700 --> 00:35:06,630
Nos gondoljon a
neve ennek üzemeltető.

740
00:35:06,630 --> 00:35:09,980
Kizáró vagy, így például a
név, fajta, azt sugallja,

741
00:35:09,980 --> 00:35:13,940
A válasz csak lesz
1, ha a bemenetek exkluzív,

742
00:35:13,940 --> 00:35:15,560
kizárólag különböző.

743
00:35:15,560 --> 00:35:18,170
Tehát itt a bemenetek a
azonos, így a kimenet 0.

744
00:35:18,170 --> 00:35:20,700
Itt a bemenetek a
azonos, így a kimenet 0.

745
00:35:20,700 --> 00:35:25,640
Itt vannak a kimenetek különböznek egymástól,
kizárólagosak, és így a kimenet 1.

746
00:35:25,640 --> 00:35:28,190
Tehát ez nagyon hasonlít a
És ez nagyon hasonló,

747
00:35:28,190 --> 00:35:32,760
vagy inkább ez nagyon hasonlít a
VAGY, de csak egy exkluzív módon.

748
00:35:32,760 --> 00:35:36,210
Ez az egy már nem egy 1,
mert van két 1-es,

749
00:35:36,210 --> 00:35:38,621
és nem kizárólag, csak az egyiket.

750
00:35:38,621 --> 00:35:39,120
Minden rendben.

751
00:35:39,120 --> 00:35:40,080
Mi van a többiekkel?

752
00:35:40,080 --> 00:35:44,220
Nos, a hullámvonal, eközben
valóban szép és egyszerű, szerencsére.

753
00:35:44,220 --> 00:35:46,410
És ez egy egyváltozós
üzemben, ami azt jelenti,

754
00:35:46,410 --> 00:35:50,400
ez kizárólag egy input,
Egy operandus, hogy úgy mondjam.

755
00:35:50,400 --> 00:35:51,800
Nem egy jobb és bal.

756
00:35:51,800 --> 00:35:56,050
Más szóval, ha Ön hullámvonal a
0, a válasz az ellenkezője.

757
00:35:56,050 --> 00:35:59,710
És ha veszel tilde 1, a
válasz lesz az ellenkezője.

758
00:35:59,710 --> 00:36:02,570
Tehát a hullámvonal üzemeltető
egy módja a tagadásának egy kicsit,

759
00:36:02,570 --> 00:36:06,000
vagy essek egy kicsit a
0-1, vagy 1-0.

760
00:36:06,000 --> 00:36:09,820
>> És, hogy hagy bennünket végre
mindössze két záró szereplők,

761
00:36:09,820 --> 00:36:13,840
Az úgynevezett baloldali váltás, és a
az úgynevezett jobb shift üzemeltető.

762
00:36:13,840 --> 00:36:16,620
Vessünk egy pillantást, hogyan ezek a munkák.

763
00:36:16,620 --> 00:36:20,780
A balra tolt üzemben, írásos
két csúcsos zárójel ilyesmi,

764
00:36:20,780 --> 00:36:22,110
a következőképpen működik.

765
00:36:22,110 --> 00:36:27,390
Ha a bemenet, vagy én operandus, hogy a bal oldali
eltolás operátora egész egyszerűen egy 1.

766
00:36:27,390 --> 00:36:33,750
És én majd mondd el a számítógépet
balratolást, hogy 1, mondjuk hét helyen,

767
00:36:33,750 --> 00:36:37,150
Az eredmény az, hogy én
venni, hogy 1, és mozgassa

768
00:36:37,150 --> 00:36:40,160
hét helyen át a
bal, és alapértelmezés szerint

769
00:36:40,160 --> 00:36:42,270
fogjuk feltételezni, hogy
A hellyel jobbra

770
00:36:42,270 --> 00:36:44,080
lesz nullákkal töltődik.

771
00:36:44,080 --> 00:36:50,316
Más szavakkal, 1 fűzött műszak 7 megy
adj, hogy az 1, majd 1, 2, 3,

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

773
00:36:54,060 --> 00:36:57,380
Tehát úgy, hogy lehetővé teszi, hogy
hogy egy kis szám, mint 1,

774
00:36:57,380 --> 00:37:00,740
és világosan, hogy sokkal
sokkal, sokkal nagyobb ezen a módon,

775
00:37:00,740 --> 00:37:06,460
de mi történt valójában látni
okosabb megközelítés érte

776
00:37:06,460 --> 00:37:08,080
helyett, valamint,

777
00:37:08,080 --> 00:37:08,720
>> Minden rendben.

778
00:37:08,720 --> 00:37:10,060
Ennyi héten három.

779
00:37:10,060 --> 00:37:11,400
Látni fogjuk legközelebb.

780
00:37:11,400 --> 00:37:12,770
Ez volt CS50.

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

782
00:37:17,270 --> 00:37:22,243
>> [Zenelejátszási]

783
00:37:22,243 --> 00:37:25,766
>> 1. Előadó: Ő volt a snack
bár eszik egy fagylaltkehely forró csokoládéöntettel.

784
00:37:25,766 --> 00:37:28,090
Ő volt az egész arcát.

785
00:37:28,090 --> 00:37:30,506
Ő visel, hogy a csokoládé, mint egy szakáll

786
00:37:30,506 --> 00:37:31,756
Hangszóró 2: Mit csinálsz?

787
00:37:31,756 --> 00:37:32,422
Hangszóró 3: Hmmm?

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

789
00:37:33,500 --> 00:37:36,800
>> Hangszóró 2: Csak nem kettős dip?

790
00:37:36,800 --> 00:37:38,585
Ha kétszer mártott a chip.

791
00:37:38,585 --> 00:37:39,460
Hangszóró 3: Elnézést.

792
00:37:39,460 --> 00:37:44,440
Hangszóró 2: Ön mártott a chip, akkor
beleharapott, és akkor mártott újra.

793
00:37:44,440 --> 00:37:44,940
Hangszóró 3:

794
00:37:44,940 --> 00:37:48,440
Hangszóró 2: Szóval ez olyan, mintha
az egész szája közvetlenül a dip.

795
00:37:48,440 --> 00:37:52,400
Legközelebb veszel egy chip,
Csak mártsuk meg egyszer, és vége.

796
00:37:52,400 --> 00:37:53,890
>> Hangszóró 3: Tudod mit, Dan?

797
00:37:53,890 --> 00:37:58,006
Ön mártsuk a kívánt módon dip.

798
00:37:58,006 --> 00:38:01,900
Majd mártsuk az is, hogy szeretnék dip.

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