1
00:00:00,000 --> 00:00:11,904
>> [Přehrávání hudby]

2
00:00:11,904 --> 00:00:12,910
>> Profesor: Dobře.

3
00:00:12,910 --> 00:00:16,730
To je CS50, a to je
koncem třetího týdne.

4
00:00:16,730 --> 00:00:20,230
Tak jsme tady dnes, ne v Sanders
Divadlo, místo toho v Weidner knihovně.

5
00:00:20,230 --> 00:00:23,170
Uvnitř což je studio
známý jako Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
nebo řekněme Studio H, nebo musí
my say-- pokud se vám to líbilo ten vtip,

7
00:00:28,310 --> 00:00:30,540
je to vlastně z
spolužák, Mark, online,

8
00:00:30,540 --> 00:00:32,420
který navrhl tolik přes Twitter.

9
00:00:32,420 --> 00:00:34,270
Teď, co je v pohodě
tady ve studiu

10
00:00:34,270 --> 00:00:38,410
je, že jsem obklopen těchto zelených
zdi, zelené obrazovky nebo chromakey,

11
00:00:38,410 --> 00:00:43,290
tak říkajíc, což znamená, že je CS50
Inscenační tým unbeknownst mně

12
00:00:43,290 --> 00:00:47,380
právě teď, může být uvedení
Nejvíc mě kdekoli na světě,

13
00:00:47,380 --> 00:00:48,660
k lepšímu nebo k horšímu.

14
00:00:48,660 --> 00:00:51,800
>> Teď, co je před námi, nastavte problém
dva je ve vašich rukou pro tento týden,

15
00:00:51,800 --> 00:00:53,830
ale s problémem set
Tři tento nadcházející týden,

16
00:00:53,830 --> 00:00:56,600
budete mít za úkol s
tzv hra 15,

17
00:00:56,600 --> 00:00:58,960
starý strana laskavost, že
můžete připomenout příjem

18
00:00:58,960 --> 00:01:02,030
jako dítě, který má spoustu
čísel, která může klouzat nahoru, dolů,

19
00:01:02,030 --> 00:01:05,790
vlevo a vpravo, a je tu ještě jedna mezera
v rámci skládačky, do kterého jste

20
00:01:05,790 --> 00:01:07,840
může skutečně posunout ty dílků.

21
00:01:07,840 --> 00:01:11,150
Nakonec obdržíte tento
puzzle v nějakém semifinále náhodném pořadí,

22
00:01:11,150 --> 00:01:12,940
a cílem je, aby
třídit to, shora dolů,

23
00:01:12,940 --> 00:01:16,310
zleva doprava, z jedné
celou cestu nahoru přes 15.

24
00:01:16,310 --> 00:01:19,360
>> Bohužel, implementace
budete mít po ruce

25
00:01:19,360 --> 00:01:21,590
bude software
na bázi, není fyzicky.

26
00:01:21,590 --> 00:01:25,280
Ty vlastně bude muset psát
kód, pomocí kterého student nebo Uživatel může

27
00:01:25,280 --> 00:01:26,760
hrát hru 15.

28
00:01:26,760 --> 00:01:29,030
A ve skutečnosti, v hacker
vydání hry 15,

29
00:01:29,030 --> 00:01:32,155
budete výzvou realizovat,
ne jen hraní této staré školy

30
00:01:32,155 --> 00:01:35,010
hra, ale spíše řešení
o tom, kterou se provádí nesmrtelnost,

31
00:01:35,010 --> 00:01:38,280
abych tak řekl, že ve skutečnosti
řeší puzzle pro člověka,

32
00:01:38,280 --> 00:01:41,080
tím, že jim s nádechem,
po náznaku, po náznakem.

33
00:01:41,080 --> 00:01:42,280
Takže o tom až příští týden.

34
00:01:42,280 --> 00:01:43,720
Ale to je to, co nás čeká.

35
00:01:43,720 --> 00:01:47,610
>> Pro tuto chvíli připomenout, že začátkem tohoto týdne
jsme měli tento cliffhanger, chcete-li,

36
00:01:47,610 --> 00:01:52,560
přičemž nejlepší, co jsme dělali třídění
moudrý byla horní hranice velkého o n

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

38
00:01:53,210 --> 00:01:56,520
Jinými slovy, bublinkové řazení,
výběr třídění, insertion sort,

39
00:01:56,520 --> 00:01:59,120
všechny z nich, zatímco jiná
při jejich provádění,

40
00:01:59,120 --> 00:02:03,480
přešel do n druhou spuštění
Čas ve velmi nejhorším případě.

41
00:02:03,480 --> 00:02:06,010
A my obecně předpokládají, že
úplně nejhorším případě pro třídění

42
00:02:06,010 --> 00:02:08,814
je ten, který vaše vstupy
jsou zcela dozadu.

43
00:02:08,814 --> 00:02:11,980
A skutečně, to trvalo poměrně málo kroků
k provádění každé z těchto algoritmů.

44
00:02:11,980 --> 00:02:15,110
>> Nyní na samém konci třídy
Připomeňme, porovnali jsme bublinkové řazení

45
00:02:15,110 --> 00:02:19,390
proti výběru druhu proti jednomu jiný
že jsme nazvali merge sort v té době,

46
00:02:19,390 --> 00:02:22,120
a navrhuji, aby to trvá
Výhodou lekci od týdne

47
00:02:22,120 --> 00:02:24,060
nula, rozděl a panuj.

48
00:02:24,060 --> 00:02:28,810
A nějak dosáhnout nějaký druh
logaritmická doba chodu nakonec,

49
00:02:28,810 --> 00:02:31,024
místo něčeho
to je čistě kvadratická.

50
00:02:31,024 --> 00:02:33,440
A není to úplně logaritmické,
je to trochu víc než to.

51
00:02:33,440 --> 00:02:36,520
Ale pokud si vzpomínáte ze třídy,
to bylo mnohem, mnohem rychlejší.

52
00:02:36,520 --> 00:02:38,210
Pojďme se podívat, kde jsme přestali.

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

54
00:02:41,880 --> 00:02:45,370
>> Bubble sort proti výběru
třídit proti sloučení druhu.

55
00:02:45,370 --> 00:02:47,700
Teď jsou všichni běží, v
teorie, ve stejnou dobu.

56
00:02:47,700 --> 00:02:50,510
CPU běží stejnou rychlostí.

57
00:02:50,510 --> 00:02:54,990
Ale můžete cítit, jak to nuda
se velmi rychle stane,

58
00:02:54,990 --> 00:02:58,790
a jen jak rychle, když jsme injekci
trochu týdnu nula je algoritmů,

59
00:02:58,790 --> 00:03:00,080
můžeme věci urychlit.

60
00:03:00,080 --> 00:03:01,630
>> Takže značka nějak vypadá úžasně.

61
00:03:01,630 --> 00:03:05,220
Jak můžeme využít ji, aby
rychleji seřadit čísel.

62
00:03:05,220 --> 00:03:07,140
Tak pojďme vzpomenu
na složky, které jsme

63
00:03:07,140 --> 00:03:10,380
měla již v týdnu nula, to
hledat někoho, kdo se v telefonním seznamu,

64
00:03:10,380 --> 00:03:12,380
a připomněl, že
pseudokód, že jsme navrhli,

65
00:03:12,380 --> 00:03:14,560
přes který můžeme najít
někdo jako Mike Smith,

66
00:03:14,560 --> 00:03:16,310
vypadal trochu něco takového.

67
00:03:16,310 --> 00:03:20,820
>> Nyní se podívejte především
na řádku 7 a 8, a 10 a 11,

68
00:03:20,820 --> 00:03:25,240
který přimět jej smyčky, čímž jsme ponechali
jít zpátky do řádku 3 znovu a znovu,

69
00:03:25,240 --> 00:03:26,520
a znovu.

70
00:03:26,520 --> 00:03:31,790
Ale ukazuje se, že můžeme zobrazit
Tento algoritmus, tady v pseudokódu,

71
00:03:31,790 --> 00:03:33,620
trochu více holisticky.

72
00:03:33,620 --> 00:03:35,960
Ve skutečnosti to, co jsem hledal
v tady na obrazovce,

73
00:03:35,960 --> 00:03:41,180
je algoritmus pro vyhledávání
Mike Smith mezi některými sady stránek.

74
00:03:41,180 --> 00:03:45,520
A skutečně, můžeme zjednodušit tento
algoritmus v těchto bodů 7 a 8,

75
00:03:45,520 --> 00:03:49,860
a 10 a 11 jen říct to,
který jsem zde uvedena v žluté.

76
00:03:49,860 --> 00:03:52,210
Jinými slovy, v případě, Mike
Smith je dříve v knize,

77
00:03:52,210 --> 00:03:55,004
nepotřebujeme specifikovat krok
za krokem, teď, jak ho najít.

78
00:03:55,004 --> 00:03:56,920
Nemáme specifikovat
se vrátit do řádku 3,

79
00:03:56,920 --> 00:03:58,960
proč ne my jen místo,
řekněme, obecněji,

80
00:03:58,960 --> 00:04:01,500
hledat Mike v
Levá polovina knihy.

81
00:04:01,500 --> 00:04:03,960
>> Naopak, pokud je Mike
ve skutečnosti později v knize,

82
00:04:03,960 --> 00:04:07,540
proč ne my jen citovat konec citátu hledání
Mike v pravé polovině knihy.

83
00:04:07,540 --> 00:04:11,030
Jinými slovy, proč ne my jen
druh pramici na sebe říká,

84
00:04:11,030 --> 00:04:13,130
hledat Mike v této
podmnožina knihy,

85
00:04:13,130 --> 00:04:16,279
a nechte to na naše stávající
algoritmus, aby nám řekli

86
00:04:16,279 --> 00:04:18,750
jak hledat Mike v
že levá polovina knihy.

87
00:04:18,750 --> 00:04:20,750
Jinými slovy, naše
algoritmus pracuje ať už je to

88
00:04:20,750 --> 00:04:24,670
telefonní seznam této síly, z toho
Tloušťka, nebo jakékoliv tloušťce vůbec.

89
00:04:24,670 --> 00:04:27,826
Takže můžeme rekurzivně
definovat tento algoritmus.

90
00:04:27,826 --> 00:04:29,950
Jinými slovy, na
Obrazovka tady, je algoritmus

91
00:04:29,950 --> 00:04:33,130
pro vyhledávání Mike Smith
Mezi stránkami telefonního seznamu.

92
00:04:33,130 --> 00:04:37,410
Takže v řádku 7 a 10, pojďme
jen říct, že přesně.

93
00:04:37,410 --> 00:04:40,250
A já používat tento termín na chvíli
Před, a opravdu, rekurze

94
00:04:40,250 --> 00:04:42,450
je módní slovo pro tuto chvíli,
a to je tento proces

95
00:04:42,450 --> 00:04:47,210
dělat něco, co by nějak cyklické
pomocí kódu, který již máte,

96
00:04:47,210 --> 00:04:49,722
a znovu volá,
a znovu a znovu.

97
00:04:49,722 --> 00:04:51,930
Teď to bude důležité,
že jsme se nějak dno

98
00:04:51,930 --> 00:04:53,821
out, a nedělejte to nekonečně dlouho.

99
00:04:53,821 --> 00:04:56,070
V opačném případě budeme
mají opravdu nekonečné smyčce.

100
00:04:56,070 --> 00:04:59,810
Ale pojďme se podívat, jestli můžeme půjčit tuto myšlenku
z rekurze, zase něco

101
00:04:59,810 --> 00:05:03,600
a znovu a znovu, řešit
třídění problém přes sloučení

102
00:05:03,600 --> 00:05:05,900
třídit, tím efektivněji.

103
00:05:05,900 --> 00:05:06,970
>> Takže dávám sloučení třídit.

104
00:05:06,970 --> 00:05:07,920
Pojďme se podívat.

105
00:05:07,920 --> 00:05:10,850
Takže tady je pseudokód, s
které jsme mohli provádět třídění,

106
00:05:10,850 --> 00:05:12,640
Pomocí tohoto algoritmu s názvem merge sort.

107
00:05:12,640 --> 00:05:13,880
A je to docela jednoduše to.

108
00:05:13,880 --> 00:05:15,940
Na vstupu n elementy,
Jinými slovy, pokud jste

109
00:05:15,940 --> 00:05:18,830
vzhledem k tomu, n prvky a čísla a
dopisy nebo co je vstup,

110
00:05:18,830 --> 00:05:22,430
pokud jste dal n elementy, pokud
n je menší než 2, jen se vrátit.

111
00:05:22,430 --> 00:05:22,930
Je to tak?

112
00:05:22,930 --> 00:05:26,430
Vzhledem k tomu, pokud n je menší než 2, které
Znamená to, že můj seznam prvků

113
00:05:26,430 --> 00:05:30,446
je buď o velikosti 0 nebo 1, a
V obou těchto případech triviální,

114
00:05:30,446 --> 00:05:31,570
seznam je již řazeno.

115
00:05:31,570 --> 00:05:32,810
Pokud není k dispozici seznam, je to třídit.

116
00:05:32,810 --> 00:05:35,185
A pokud tam je seznam délky
1, je to samozřejmě třídit.

117
00:05:35,185 --> 00:05:38,280
Takže algoritmus pouze potřebuje
opravdu něco zajímavého,

118
00:05:38,280 --> 00:05:40,870
pokud budeme mít dva nebo více
prvky nám dána.

119
00:05:40,870 --> 00:05:42,440
Takže pojďme se podívat na magii poté.

120
00:05:42,440 --> 00:05:47,500
Else seřadit levé poloviny prvků,
pak třídit pravou polovinu prvků,

121
00:05:47,500 --> 00:05:49,640
pak sloučit setříděné poloviny.

122
00:05:49,640 --> 00:05:52,440
A co je druh mysli ohýbání
tady je, že opravdu nemám

123
00:05:52,440 --> 00:05:56,190
Zdá se, že vám řekl,
něco ještě ne, že jo?

124
00:05:56,190 --> 00:05:59,560
Všechno, co jsem řekl, je, dostane seznam
n prvků, třídit levou polovinu,

125
00:05:59,560 --> 00:06:01,800
poté pravé poloviny, poté
sloučit seřazené poloviny,

126
00:06:01,800 --> 00:06:03,840
ale tam, kde je skutečný tajný recept?

127
00:06:03,840 --> 00:06:05,260
Kde je algoritmus?

128
00:06:05,260 --> 00:06:09,150
No, ukázalo se, že těch dvou linek
První, druh levé polovině prvků,

129
00:06:09,150 --> 00:06:13,970
a druh pravá polovina prvků,
jsou rekurzivní volání, abych tak řekl.

130
00:06:13,970 --> 00:06:16,120
>> Koneckonců, na to
bod v čase, musím

131
00:06:16,120 --> 00:06:18,950
algoritmus, se kterým
seřadit spoustu prvků?

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

133
00:06:19,450 --> 00:06:20,620
Je to přímo tady.

134
00:06:20,620 --> 00:06:25,180
Je to přímo tady na obrazovce, a
takže mohu použít ten stejný soubor kroků

135
00:06:25,180 --> 00:06:28,500
třídit levou polovinu,
jak mohu pravá polovina.

136
00:06:28,500 --> 00:06:30,420
A skutečně, znovu a znovu.

137
00:06:30,420 --> 00:06:34,210
Takže tak či onak, a my brzy
vidět, kouzlo sloučení druhu

138
00:06:34,210 --> 00:06:37,967
je zakotven v tom, že velmi konečný
linka, slučování tříděných poloviny.

139
00:06:37,967 --> 00:06:39,300
A to se zdá být poměrně intuitivní.

140
00:06:39,300 --> 00:06:41,050
Budete mít dvě poloviny, a ti,
nějak, spojit je dohromady,

141
00:06:41,050 --> 00:06:43,260
a my budeme vidět
konkrétně za chvíli.

142
00:06:43,260 --> 00:06:45,080
>> Ale to je kompletní algoritmus.

143
00:06:45,080 --> 00:06:46,640
A podívejme se, proč.

144
00:06:46,640 --> 00:06:50,912
Tak předpokládám, že jsme vzhledem k tytéž
Osm prvky tady na obrazovce, jeden

145
00:06:50,912 --> 00:06:53,120
přes osm, ale jsou
ve zdánlivě náhodném pořadí.

146
00:06:53,120 --> 00:06:55,320
A cíl je na dosah ruky
třídit tyto prvky.

147
00:06:55,320 --> 00:06:58,280
Tak jak mohu jít o
dělá použití, znovu,

148
00:06:58,280 --> 00:07:00,407
merge sort, jak na tento pseudokódu?

149
00:07:00,407 --> 00:07:02,740
A opět, barvit to v
vaše mysl, jen na chvíli.

150
00:07:02,740 --> 00:07:05,270
V prvním případě je dost
triviální, pokud je to méně než 2,

151
00:07:05,270 --> 00:07:07,060
jen vrátit, není práce je třeba udělat.

152
00:07:07,060 --> 00:07:09,290
Takže opravdu tam je jen tři
kroky k opravdu mít na paměti.

153
00:07:09,290 --> 00:07:11,081
Znovu a znovu, já jsem
bude chtít mít

154
00:07:11,081 --> 00:07:13,980
třídit levou polovinu,
třídit pravou polovinu,

155
00:07:13,980 --> 00:07:15,890
a pak ještě jednou jejich
dvě poloviny jsou řazeny,

156
00:07:15,890 --> 00:07:18,710
Chci je sloučit dohromady
do jednoho seřazeném seznamu.

157
00:07:18,710 --> 00:07:19,940
Takže mějte na paměti, že.

158
00:07:19,940 --> 00:07:21,310
>> Tak tady je původní seznam.

159
00:07:21,310 --> 00:07:23,510
Pojďme se touto jako
pole, jak jsme začali

160
00:07:23,510 --> 00:07:25,800
ve dvou týdnu, což je
souvislý blok paměti.

161
00:07:25,800 --> 00:07:28,480
V tomto případě, který obsahuje osm
Čísla, zády k sobě k sobě.

162
00:07:28,480 --> 00:07:30,700
A pojďme se nyní vztahují merge sort.

163
00:07:30,700 --> 00:07:33,300
Tak jsem se poprvé chcete seřadit
levá polovina tohoto seznamu,

164
00:07:33,300 --> 00:07:37,370
a pojďme se tedy,
zaměřit se na 4, 8, 6, a 2.

165
00:07:37,370 --> 00:07:41,000
>> Nyní, jak mám jít o
řazení seznamu velikosti 4?

166
00:07:41,000 --> 00:07:45,990
No musím nyní považují
třídění vlevo od levé poloviny.

167
00:07:45,990 --> 00:07:47,720
Opět platí, pojďme vzad jen na chvíli.

168
00:07:47,720 --> 00:07:51,010
V případě, že je to pseudokód,
a já jsem dal osm elementů,

169
00:07:51,010 --> 00:07:53,230
8 je samozřejmě větší,
než nebo roven 2.

170
00:07:53,230 --> 00:07:54,980
A tak se o první případ, nepoužije.

171
00:07:54,980 --> 00:07:58,120
Takže třídit osm elementů, jsem poprvé
řadit levou polovinu prvků,

172
00:07:58,120 --> 00:08:01,930
Pak jsem seřadit pravou polovinu, pak jsem se sloučit
obě seřazená poloviny, každá o velikosti 4.

173
00:08:01,930 --> 00:08:02,470
DOBŘE.

174
00:08:02,470 --> 00:08:07,480
>> Ale pokud jste právě mi řekl, setřiďte
levá polovina, která je nyní o velikosti 4,

175
00:08:07,480 --> 00:08:09,350
jak mám třídit levou polovinu?

176
00:08:09,350 --> 00:08:11,430
No, pokud mám
vstup ze čtyř prvků,

177
00:08:11,430 --> 00:08:14,590
Poprvé jsem řadit levou
dvou a poté pravé dva,

178
00:08:14,590 --> 00:08:16,210
a pak jsem se spojit je dohromady.

179
00:08:16,210 --> 00:08:18,700
Takže znovu, to se stává trochu
na mysli ohýbání hru tady,

180
00:08:18,700 --> 00:08:21,450
Protože ty, druh, musí
vzpomenout, kde jste v příběhu,

181
00:08:21,450 --> 00:08:23,620
ale na konci dne,
vzhledem k tomu, libovolný počet prvků,

182
00:08:23,620 --> 00:08:25,620
nejprve chcete třídit
levá polovina, potom pravá polovina,

183
00:08:25,620 --> 00:08:26,661
pak spojit je dohromady.

184
00:08:26,661 --> 00:08:28,630
Pojďme začít dělat přesně to.

185
00:08:28,630 --> 00:08:30,170
Zde je vstup z osmi prvků.

186
00:08:30,170 --> 00:08:31,910
Nyní se díváme na levé polovině zde.

187
00:08:31,910 --> 00:08:33,720
Jak mám třídit čtyři prvky?

188
00:08:33,720 --> 00:08:35,610
Tak jsem nejprve seřadit levé poloviny.

189
00:08:35,610 --> 00:08:37,720
Nyní, jak se mohu řadit levou polovinu?

190
00:08:37,720 --> 00:08:39,419
No já jsem dostal dva prvky.

191
00:08:39,419 --> 00:08:41,240
Takže pojďme seřadit tyto dva prvky.

192
00:08:41,240 --> 00:08:44,540
2 je větší než nebo
rovné 2, samozřejmě.

193
00:08:44,540 --> 00:08:46,170
Tak, že první případ nevztahuje.

194
00:08:46,170 --> 00:08:49,010
>> Takže jsem teď musí třídit levou
polovina z těchto dvou prvků.

195
00:08:49,010 --> 00:08:50,870
Levá polovina, samozřejmě, je jen 4.

196
00:08:50,870 --> 00:08:54,020
Tak jak mám seřadit seznam z jednoho prvku?

197
00:08:54,020 --> 00:08:57,960
Tak a teď, že zvláštní referenční případ
up vrcholu, abych tak řekl, platí.

198
00:08:57,960 --> 00:09:01,470
1 je menší než 2, a my
Seznam je skutečně o velikosti 1.

199
00:09:01,470 --> 00:09:02,747
Tak jsem se vrátit.

200
00:09:02,747 --> 00:09:03,580
Já nedělám nic.

201
00:09:03,580 --> 00:09:06,770
A skutečně, dívat se na to, co jsem
udělal, 4 je již řazeno.

202
00:09:06,770 --> 00:09:09,220
Jako bych už
částečně úspěšné zde.

203
00:09:09,220 --> 00:09:11,750
>> Nyní se zdá, že trochu hloupý
nároku, ale je to pravda.

204
00:09:11,750 --> 00:09:13,700
4 je uveden seznam velikosti 1.

205
00:09:13,700 --> 00:09:15,090
Je to již řazeno.

206
00:09:15,090 --> 00:09:16,270
To je levá polovina.

207
00:09:16,270 --> 00:09:18,010
Teď jsem řadit pravou polovinu.

208
00:09:18,010 --> 00:09:22,310
Můj vstup je jedním z prvků, 8
podobně, již seřazeny.

209
00:09:22,310 --> 00:09:25,170
Hloupý, taky, ale opět,
Tento základní princip

210
00:09:25,170 --> 00:09:28,310
bude nám umožní si nyní budují
v horní části této úspěšně.

211
00:09:28,310 --> 00:09:32,260
4 řazeny, 8 je tříděn, nyní
co to bylo poslední krok?

212
00:09:32,260 --> 00:09:35,330
Takže třetí a poslední krok, jakýkoliv
Čas, který se třídění seznamu, odvolání,

213
00:09:35,330 --> 00:09:38,310
bylo sloučit dvě poloviny,
levý a pravý.

214
00:09:38,310 --> 00:09:39,900
Takže pojďme udělat přesně to.

215
00:09:39,900 --> 00:09:41,940
Má levá polovina je, samozřejmě, 4.

216
00:09:41,940 --> 00:09:43,310
Moje pravá polovina je 8.

217
00:09:43,310 --> 00:09:44,100
>> Tak jdeme na to.

218
00:09:44,100 --> 00:09:46,410
Nejprve budu přidělit
některé další paměť,

219
00:09:46,410 --> 00:09:48,680
že budu reprezentovat tady,
jen jako sekundární pole,

220
00:09:48,680 --> 00:09:49,660
to je dost velký, aby se vešly to.

221
00:09:49,660 --> 00:09:52,243
Ale můžete si představit rozšíření
že obdélník po celé délce,

222
00:09:52,243 --> 00:09:53,290
pokud budeme potřebovat více později.

223
00:09:53,290 --> 00:09:58,440
Jak mohu pořídit 4 a 8, a sloučit
tyto dva seznamy velikosti 1 spolu?

224
00:09:58,440 --> 00:10:00,270
I zde docela jednoduché.

225
00:10:00,270 --> 00:10:03,300
4 je na prvním místě, pak přijde 8.

226
00:10:03,300 --> 00:10:07,130
Protože pokud chci na třídíte
levá polovina, potom pravá polovina,

227
00:10:07,130 --> 00:10:09,900
a potom sloučit tyto dvě poloviny
společně, v seřazeném pořadí,

228
00:10:09,900 --> 00:10:11,940
4 je na prvním místě, pak přijde 8.

229
00:10:11,940 --> 00:10:15,810
>> Takže se zdá, že bude dělat pokroky, a to i
i když jsem neudělal žádnou skutečnou práci.

230
00:10:15,810 --> 00:10:17,800
Ale pamatujte, kde jsme v příběhu.

231
00:10:17,800 --> 00:10:19,360
Původně jsme vzali osm prvků.

232
00:10:19,360 --> 00:10:21,480
Vyřešili jsme levou polovinu, což je 4.

233
00:10:21,480 --> 00:10:24,450
Pak jsme řazeny levou polovinu
z levé poloviny, který byl 2.

234
00:10:24,450 --> 00:10:25,270
A je to tady.

235
00:10:25,270 --> 00:10:26,920
Jsme skončili s tímto krokem.

236
00:10:26,920 --> 00:10:29,930
>> Takže pokud jsme třídí
levé poloviny 2, teď jsme

237
00:10:29,930 --> 00:10:32,130
mají třídit pravou polovinu 2.

238
00:10:32,130 --> 00:10:35,710
Takže pravá polovina 2 je
Tyto dvě hodnoty zde, 6 a 2.

239
00:10:35,710 --> 00:10:40,620
Takže pojďme se teď vstup velikosti
2, a třídit levou polovinu, a poté

240
00:10:40,620 --> 00:10:42,610
pravou polovinu, a poté
sloučit dohromady.

241
00:10:42,610 --> 00:10:45,722
Tak jak mám seřadit seznam velikosti
1, který obsahuje jen číslo 6?

242
00:10:45,722 --> 00:10:46,430
Já jsem už skončil.

243
00:10:46,430 --> 00:10:48,680
Tento seznam o velikosti 1 je seřazen.

244
00:10:48,680 --> 00:10:52,140
>> Jak mohu vyřešit další seznam
velikost 1, tzv pravá polovina.

245
00:10:52,140 --> 00:10:54,690
No to, také, je již řazeno.

246
00:10:54,690 --> 00:10:56,190
Číslo 2 je sám.

247
00:10:56,190 --> 00:11:00,160
Takže teď mám dvě poloviny, vlevo a
Dobře, je třeba je sloučit dohromady.

248
00:11:00,160 --> 00:11:01,800
Dovolte mi abych si nějaké extra prostor.

249
00:11:01,800 --> 00:11:05,580
A dal 2 tam,
pak 6 tam, čímž

250
00:11:05,580 --> 00:11:10,740
třídění tohoto seznamu, vlevo a vpravo,
a slučování společně, nakonec.

251
00:11:10,740 --> 00:11:12,160
Takže já jsem v trochu lepším stavu.

252
00:11:12,160 --> 00:11:16,250
Já jsem neskončil, protože jasně 4, 8, 2,
6 není konečný, které nařizuje chci.

253
00:11:16,250 --> 00:11:20,640
Ale teď mám dva seznamy velikosti 2, že
mají oba, v daném pořadí, byly seřazeny.

254
00:11:20,640 --> 00:11:24,580
Takže teď, pokud přetočíte ve vaší mysli
oko, kde se to pro nás znamená?

255
00:11:24,580 --> 00:11:28,520
Začal jsem s osmi prvků, pak jsem
ořezaný dolů do levé poloviny 4,

256
00:11:28,520 --> 00:11:31,386
poté levou část 2, a
pak je pravá polovina 2,

257
00:11:31,386 --> 00:11:34,510
Jsem skončil, a proto, třídění levý
poloviny 2, a v pravé polovině 2,

258
00:11:34,510 --> 00:11:37,800
takže to, co je tady třetí a poslední krok?

259
00:11:37,800 --> 00:11:41,290
Musím se spojit dohromady
dva seznamy velikosti 2.

260
00:11:41,290 --> 00:11:42,040
Tak pojďme do toho.

261
00:11:42,040 --> 00:11:43,940
A na obrazovce se tady, dej
mi některé další paměť,

262
00:11:43,940 --> 00:11:47,170
ačkoli technicky, všimněte si, že jsem
dostal spoustu prázdné místo na začátek

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

264
00:11:47,670 --> 00:11:50,044
Pokud chci být obzvláště
efektivní prostor moudrý,

265
00:11:50,044 --> 00:11:52,960
Mohl bych dát do pohybu prvky
tam a zpět, nahoře a dole.

266
00:11:52,960 --> 00:11:55,460
Ale jen pro vizuální jasnost,
Chystám se dát to dole,

267
00:11:55,460 --> 00:11:56,800
udržet věci pěkné a čisté.

268
00:11:56,800 --> 00:11:58,150
>> Tak jsem dostal dva seznamy velikosti 2.

269
00:11:58,150 --> 00:11:59,770
První seznam má 4 a 8.

270
00:11:59,770 --> 00:12:01,500
Druhý seznam obsahuje 2 a 6.

271
00:12:01,500 --> 00:12:03,950
Pojďme sloučit ty
spolu v seřazeném pořadí.

272
00:12:03,950 --> 00:12:09,910
2, samozřejmě, je na prvním místě,
pak 4, pak 6, pak 8.

273
00:12:09,910 --> 00:12:12,560
A teď se zdá, že se dostat
někde zajímavé.

274
00:12:12,560 --> 00:12:15,720
Teď jsem řazeny polovina
vypsat, a shodou okolností je to

275
00:12:15,720 --> 00:12:18,650
všechna sudá čísla, ale že
je opravdu jen náhoda.

276
00:12:18,650 --> 00:12:22,220
A teď si řazeny levý
polovina, tak, že to je 2, 4, 6 a 8.

277
00:12:22,220 --> 00:12:23,430
Nic není mimo provoz.

278
00:12:23,430 --> 00:12:24,620
To se cítí jako pokrok.

279
00:12:24,620 --> 00:12:26,650
>> Teď to vypadá, jsem
byl nyní hovoří navždy,

280
00:12:26,650 --> 00:12:29,850
Takže to, co zbývá být viděn jestliže toto
algoritmus je skutečně efektivnější.

281
00:12:29,850 --> 00:12:31,766
Ale my procházíme
to výborný metodicky.

282
00:12:31,766 --> 00:12:34,060
Počítač, samozřejmě,
bych to takhle.

283
00:12:34,060 --> 00:12:34,840
Tak kde to jsme?

284
00:12:34,840 --> 00:12:36,180
Začali jsme s osmi prvků.

285
00:12:36,180 --> 00:12:37,840
Řazeny jsem levou polovinu 4.

286
00:12:37,840 --> 00:12:39,290
Zdá se mi, je třeba udělat s tím.

287
00:12:39,290 --> 00:12:42,535
Takže teď je dalším krokem k
třídit pravou polovinu 4.

288
00:12:42,535 --> 00:12:44,410
A tato část můžeme jít
přes trochu více

289
00:12:44,410 --> 00:12:47,140
rychle, i když jste
Vítáme Vás na vzad nebo pozastavit, jen

290
00:12:47,140 --> 00:12:49,910
myslíte, že přes to na
svým vlastním tempem, ale to, co

291
00:12:49,910 --> 00:12:53,290
teď máme, je příležitost
dělat přesně stejný algoritmus na čtyřech

292
00:12:53,290 --> 00:12:54,380
různá čísla.

293
00:12:54,380 --> 00:12:57,740
>> Tak pojďme do toho, a zaměřit se na
pravá polovina, který jsme tady.

294
00:12:57,740 --> 00:13:01,260
Levá polovina, která
pravou polovinu, a teď

295
00:13:01,260 --> 00:13:04,560
Levá polovina vlevo
polovina z té pravé poloviny,

296
00:13:04,560 --> 00:13:08,030
a jak seřadit seznam velikosti
1 obsahující pouze číslo 1?

297
00:13:08,030 --> 00:13:09,030
Už se stalo.

298
00:13:09,030 --> 00:13:11,830
Jak to mám udělat totéž pro seznam
o velikosti 1, který obsahuje jen 7?

299
00:13:11,830 --> 00:13:12,840
Už se stalo.

300
00:13:12,840 --> 00:13:16,790
Třetí krok pro toto je polovina
je sloučit tyto dva prvky

301
00:13:16,790 --> 00:13:20,889
do nového seznamu velikosti 2, 1 a 7.

302
00:13:20,889 --> 00:13:23,180
Nezdá se, že udělali vše
že hodně zajímavá práce.

303
00:13:23,180 --> 00:13:24,346
Podívejme se, co se bude dít dál.

304
00:13:24,346 --> 00:13:29,210
Jen jsem řazeny do levé poloviny
pravá polovina mého původního vstupu.

305
00:13:29,210 --> 00:13:32,360
Nyní pojďme seřadit právo
polovina, která obsahuje 5 a 3.

306
00:13:32,360 --> 00:13:35,740
Pojďme se znovu podívat na levé straně
polovina, tříděny, pravá polovina, tříděny,

307
00:13:35,740 --> 00:13:39,120
a spojit ty dva dohromady,
do nějakého dalšího prostoru,

308
00:13:39,120 --> 00:13:41,670
3 je na prvním místě, pak přijde 5.

309
00:13:41,670 --> 00:13:46,190
A tak teď jsme se třídí
Levá polovina pravou polovinu

310
00:13:46,190 --> 00:13:49,420
z původní problém, a
pravá polovina pravou polovinu

311
00:13:49,420 --> 00:13:50,800
z původní problém.

312
00:13:50,800 --> 00:13:52,480
Co je třetí a poslední krok?

313
00:13:52,480 --> 00:13:54,854
No sloučit tyto dvě poloviny dohromady.

314
00:13:54,854 --> 00:13:57,020
Tak ať mi, abych si sám trochu
prostor navíc, ale opět jsem

315
00:13:57,020 --> 00:13:58,699
může být pomocí tohoto extra prostor na vrchol.

316
00:13:58,699 --> 00:14:00,490
Ale budeme držet
to jednoduché vizuálně.

317
00:14:00,490 --> 00:14:07,070
Dovolte mi, abych nyní sloučit v 1, a
pak 3, a poté 5, a pak 7.

318
00:14:07,070 --> 00:14:10,740
Tím mě teď opouští s
Pravá polovina původní problém

319
00:14:10,740 --> 00:14:12,840
to je dokonale seřazeny.

320
00:14:12,840 --> 00:14:13,662
>> Takže to, co zůstane?

321
00:14:13,662 --> 00:14:16,120
Mám pocit, jako bych držet říkat
stejné věci znovu a znovu,

322
00:14:16,120 --> 00:14:18,700
ale to je odrážející
Skutečnost, že jsme pomocí rekurze.

323
00:14:18,700 --> 00:14:21,050
Proces za použití
algoritmus znovu a znovu,

324
00:14:21,050 --> 00:14:23,940
na menší podmnožiny
původní problém.

325
00:14:23,940 --> 00:14:27,580
Takže jsem teď se levý seřazena
polovinu původní problém.

326
00:14:27,580 --> 00:14:30,847
Mám právo seřazené polovinu
z původní problém.

327
00:14:30,847 --> 00:14:32,180
Co je třetí a poslední krok?

328
00:14:32,180 --> 00:14:33,590
Oh, to je sloučení.

329
00:14:33,590 --> 00:14:34,480
Takže pojďme to udělat.

330
00:14:34,480 --> 00:14:36,420
Pojďme přidělit některé další
paměť, ale můj Bože,

331
00:14:36,420 --> 00:14:37,503
ji mohl dát teď kdekoliv.

332
00:14:37,503 --> 00:14:40,356
Máme tolik místa k dispozici
k nám, ale my budeme držet to jednoduché.

333
00:14:40,356 --> 00:14:42,730
Místo toho, aby šel zpět a
dále s naší původní pamětí,

334
00:14:42,730 --> 00:14:44,480
ať to prostě udělat
vizuálně tady dole,

335
00:14:44,480 --> 00:14:47,240
aby dokončit sloučení
levou polovinu a pravá polovina.

336
00:14:47,240 --> 00:14:49,279
>> Takže sloučením, co musím udělat?

337
00:14:49,279 --> 00:14:50,820
Chci, aby se prvky v pořadí.

338
00:14:50,820 --> 00:14:53,230
Takže při pohledu na levé polovině,
Vidím, první číslo je 2.

339
00:14:53,230 --> 00:14:55,230
Dívám se na pravou polovinu,
Vidím první číslo

340
00:14:55,230 --> 00:14:58,290
je 1, tak samozřejmě což
Číslo nechci trhat ven,

341
00:14:58,290 --> 00:15:00,430
a dal první v mém konečném seznamu?

342
00:15:00,430 --> 00:15:01,449
Samozřejmě, 1.

343
00:15:01,449 --> 00:15:02,990
Teď chci položit tuto stejnou otázku.

344
00:15:02,990 --> 00:15:05,040
Na levé polovině, jsem
pořád číslo 2.

345
00:15:05,040 --> 00:15:07,490
Na pravé polovině,
Mám číslo 3.

346
00:15:07,490 --> 00:15:08,930
Který z nich si chci vybrat?

347
00:15:08,930 --> 00:15:11,760
Samozřejmě, že číslo 2 a
Nyní si všimnout kandidátů

348
00:15:11,760 --> 00:15:13,620
jsou 4 vlevo, 3 vpravo.

349
00:15:13,620 --> 00:15:15,020
Pojďme se, samozřejmě, zvolte 3.

350
00:15:15,020 --> 00:15:18,020
Nyní jsou 4 kandidáti na
levá, 5 na pravé straně.

351
00:15:18,020 --> 00:15:19,460
My, samozřejmě, zvolte 4.

352
00:15:19,460 --> 00:15:21,240
6 na levé straně, 5 vpravo.

353
00:15:21,240 --> 00:15:22,730
My, samozřejmě, zvolte 5.

354
00:15:22,730 --> 00:15:25,020
6 na levé straně, 7 na pravé straně.

355
00:15:25,020 --> 00:15:29,320
Vybíráme 6, a pak jsme
vybrat 7, a pak volíme 8.

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

357
00:15:30,100 --> 00:15:34,370
>> Tak obrovské množství slov později jsme
mají řazeny tento seznam osmi prvků

358
00:15:34,370 --> 00:15:38,450
do seznamu jeden přes osm,
který je roste s každým krokem,

359
00:15:38,450 --> 00:15:40,850
ale kolik času udělal
trvat nás to udělat.

360
00:15:40,850 --> 00:15:43,190
No jsem záměrně
položené věci obrazově

361
00:15:43,190 --> 00:15:46,330
tady, takže můžeme druh
vidět nebo ocenit divizi

362
00:15:46,330 --> 00:15:49,060
dobýt, že se děje.

363
00:15:49,060 --> 00:15:52,830
>> Ve skutečnosti, když se podíváte zpátky na brázdě,
Nechala jsem všechny tyto přerušovanou čarou

364
00:15:52,830 --> 00:15:55,660
V držitelů místě, můžete,
druh, vidět, v opačném pořadí,

365
00:15:55,660 --> 00:15:58,800
pokud jste trochu ohlédnout v
Historie teď, můj původní seznam

366
00:15:58,800 --> 00:16:00,250
Je, samozřejmě, velikosti 8.

367
00:16:00,250 --> 00:16:03,480
A pak již dříve, jsem byl
zabývající se dvěma seznamy velikosti 4,

368
00:16:03,480 --> 00:16:08,400
a pak čtyři seznamy velikosti 2,
a pak osm seznamy velikosti 1.

369
00:16:08,400 --> 00:16:10,151
>> Takže to, co dělá to,
druh, vás upozorní na?

370
00:16:10,151 --> 00:16:11,858
No, opravdu, některé z
algoritmy jsme

371
00:16:11,858 --> 00:16:14,430
Podíval se na tak daleko, kde jsme
rozděl a dělit, a rozdělit,

372
00:16:14,430 --> 00:16:19,500
zachovat s věci znovu, a
opět vede v tomto obecném myšlence.

373
00:16:19,500 --> 00:16:23,100
A tak je tu něco
logaritmická tady děje.

374
00:16:23,100 --> 00:16:26,790
A není to úplně log n, ale
tam je logaritmická komponent

375
00:16:26,790 --> 00:16:28,280
k tomu, co jsme právě udělali.

376
00:16:28,280 --> 00:16:31,570
>> Nyní se pojďme zvážit, jak to ve skutečnosti je.

377
00:16:31,570 --> 00:16:34,481
Takže log n, opět byl
skvělý hrací čas,

378
00:16:34,481 --> 00:16:36,980
když jsme udělali něco jako
binární vyhledávání, jak my teď říkáme,

379
00:16:36,980 --> 00:16:40,090
rozděl a panuj strategie
přes který jsme našli Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Teď technicky.

381
00:16:41,020 --> 00:16:43,640
To je základ log 2 n, a to i
i když ve většině matematických tříd,

382
00:16:43,640 --> 00:16:45,770
10 je obvykle báze, která se domníváte.

383
00:16:45,770 --> 00:16:48,940
Ale počítačoví odborníci téměř vždy
myslet a mluvit, pokud jde o základně 2,

384
00:16:48,940 --> 00:16:52,569
takže jsme se obecně stačí říct záznam
n, místo toho, log základny 2 n,

385
00:16:52,569 --> 00:16:55,110
ale jsou to přesně jeden a
Totéž ve světě počítače

386
00:16:55,110 --> 00:16:57,234
vědy, a jak stranou,
tam je konstantní faktor

387
00:16:57,234 --> 00:17:01,070
Rozdíl mezi těmito dvěma, takže je
diskutabilní tak jako tak, pro více formálních důvodů.

388
00:17:01,070 --> 00:17:04,520
>> Ale teď, to, co nás zajímá
o je tento příklad.

389
00:17:04,520 --> 00:17:08,520
Takže pojďme nedokazuje příkladem, ale v
alespoň na jeden příklad z čísel

390
00:17:08,520 --> 00:17:10,730
po ruce jako kontrola sanitačního, chcete-li.

391
00:17:10,730 --> 00:17:14,510
Takže předtím vzorec byl základ log
2 n, ale to, co je v tomto případě n.

392
00:17:14,510 --> 00:17:18,526
Měl jsem n původní čísla, nebo 8
z původního počtu specificky.

393
00:17:18,526 --> 00:17:20,359
Teď už je to trochu
zatímco, ale jsem docela

394
00:17:20,359 --> 00:17:25,300
jisti, že log základ 2
hodnoty 8 je 3,

395
00:17:25,300 --> 00:17:29,630
a opravdu, co je hezké o který je
3, který je přesně počet, kolikrát

396
00:17:29,630 --> 00:17:33,320
že můžete rozdělit seznam
délky 8 znovu a znovu,

397
00:17:33,320 --> 00:17:36,160
a znovu, dokud jste odešel
seznamy pouze velikosti 1.

398
00:17:36,160 --> 00:17:36,660
Je to tak?

399
00:17:36,660 --> 00:17:40,790
8 jde do 4, jde do 2,
jde k 1, a to je

400
00:17:40,790 --> 00:17:43,470
odrazem přesně to
picture měli jsme před chvílí.

401
00:17:43,470 --> 00:17:47,160
Tak trochu zdravý rozum zjistit, kam
logaritmus je vlastně jedná.

402
00:17:47,160 --> 00:17:50,180
>> Takže teď, co ještě se zde jedná? n.

403
00:17:50,180 --> 00:17:53,440
Takže si všimnout, že každý
Když jsem rozdělil seznamu,

404
00:17:53,440 --> 00:17:58,260
i když v opačném pořadí v historii
tady, byl jsem stále dělá n věci.

405
00:17:58,260 --> 00:18:02,320
Že sloučení krok vyžaduje, aby
Dotknu každý jeden z čísel,

406
00:18:02,320 --> 00:18:05,060
aby to sklouznout
svým vhodným umístěním.

407
00:18:05,060 --> 00:18:10,760
Takže i když je výška této
diagram je velikosti log n n nebo 3,

408
00:18:10,760 --> 00:18:13,860
specificky, jinými slovy,
Udělal jsem tři divize sem.

409
00:18:13,860 --> 00:18:18,800
Kolik práce jsem udělal horizontálně
podél této tabulce pokaždé?

410
00:18:18,800 --> 00:18:21,110
>> No, já jsem n kroky
fungovat, protože pokud jsem

411
00:18:21,110 --> 00:18:24,080
dostal čtyři elementy a čtyři elementy,
a musím sloučit dohromady.

412
00:18:24,080 --> 00:18:26,040
Musím projít
tyto čtyři a tyto čtyři,

413
00:18:26,040 --> 00:18:28,123
nakonec sloučit
zpět do osmi prvků.

414
00:18:28,123 --> 00:18:32,182
Pokud naopak mám osm prstů
tady, což nechci, a osmi

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- jestli jsem
dostal čtyři prsty sem,

416
00:18:34,390 --> 00:18:37,380
které dělám, čtyři prsty
tady, což dělám,

417
00:18:37,380 --> 00:18:40,590
pak je to stejné
Příkladem jako předtím, když to udělám

418
00:18:40,590 --> 00:18:44,010
mají osm prstů i když v
celkem, který jsem si, druh, ano.

419
00:18:44,010 --> 00:18:47,950
Můžu přesně se zde,
pak jsem si určitě

420
00:18:47,950 --> 00:18:50,370
sloučit všechny z těchto seznamů
o velikosti 1, společně.

421
00:18:50,370 --> 00:18:54,050
Ale já rozhodně se podívat
u každého prvku právě jednou.

422
00:18:54,050 --> 00:18:59,640
Takže je výška tohoto procesu je log n,
šířka tohoto procesu, abych tak řekl,

423
00:18:59,640 --> 00:19:02,490
je n, takže to, co se nám zdá,
mít, nakonec, je

424
00:19:02,490 --> 00:19:06,470
běžící čas o velikosti n časy log n.

425
00:19:06,470 --> 00:19:08,977
>> Jinými slovy, jsme rozdělili
seznam, log n-krát,

426
00:19:08,977 --> 00:19:11,810
ale pokaždé, když jsme udělali, že jsme měli
dotknout každý jeden z prvků,

427
00:19:11,810 --> 00:19:13,560
za účelem jejich sloučení
dohromady, což

428
00:19:13,560 --> 00:19:18,120
n byl krok, takže máme n-krát log n,
nebo jako počítačový vědec by řekl,

429
00:19:18,120 --> 00:19:20,380
asymptoticky, který
by bylo velké slovo

430
00:19:20,380 --> 00:19:22,810
popsat horní
vázané na jízdní doby,

431
00:19:22,810 --> 00:19:28,010
jsme se běží ve velkém O
log n času, abych tak řekl.

432
00:19:28,010 --> 00:19:31,510
>> Nyní je to významné, protože
vzpomenout, co běží časy byly

433
00:19:31,510 --> 00:19:34,120
bublinkové druhu, a výběr
třídění a vkládání třídění,

434
00:19:34,120 --> 00:19:38,200
a dokonce i několik dalších, které existují,
n čtvercový bylo místo, kde jsme byli na.

435
00:19:38,200 --> 00:19:39,990
A můžete, druh, vidět tady.

436
00:19:39,990 --> 00:19:45,720
Je-li na druhou n je samozřejmě n krát
n, ale tady máme n-krát log n,

437
00:19:45,720 --> 00:19:48,770
a my již známe z týdne
nula, že log n, logaritmické,

438
00:19:48,770 --> 00:19:50,550
je lepší než něco lineární.

439
00:19:50,550 --> 00:19:52,930
Koneckonců, připomínají obraz
s červenou a žlutou

440
00:19:52,930 --> 00:19:56,500
a zelené linky, které jsme vypracovali, tím
green logaritmická linie byla mnohem nižší.

441
00:19:56,500 --> 00:20:00,920
A proto, mnohem lépe a rychleji
než rovných žluté a červené čáry,

442
00:20:00,920 --> 00:20:05,900
n-krát log n je skutečně lepší,
než N-krát n, nebo n na druhou.

443
00:20:05,900 --> 00:20:09,110
>> Takže se zdá, že se
identifikoval algoritmus sloučení

444
00:20:09,110 --> 00:20:11,870
druh, který běží v mnohem
rychlejší, a dokonce,

445
00:20:11,870 --> 00:20:16,560
to je důvod, proč na počátku tohoto týdne, kdy
jsme viděli, že soutěž mezi bubliny

446
00:20:16,560 --> 00:20:20,750
třídění, výběr třídit, a sloučit
třídění, merge sort opravdu, ale opravdu vyhrál.

447
00:20:20,750 --> 00:20:23,660
A skutečně, jsme neměli ani čekat
k Bubble druhu a výběru druhu

448
00:20:23,660 --> 00:20:24,790
dokončit.

449
00:20:24,790 --> 00:20:27,410
>> Nyní se pojďme jeden další průchod
na to, ze o něco více

450
00:20:27,410 --> 00:20:31,030
formální perspektiva, jen v
případ, to rezonuje lépe

451
00:20:31,030 --> 00:20:33,380
než této vyšší úrovni diskuse.

452
00:20:33,380 --> 00:20:34,880
Takže tady je opět algoritmus.

453
00:20:34,880 --> 00:20:36,770
Pojďme se sami sebe zeptat,
co je doba chodu

454
00:20:36,770 --> 00:20:39,287
Je to algoritmy různé kroky?

455
00:20:39,287 --> 00:20:41,620
Pojďme rozdělit jej na první
pouzdro a druhý případ.

456
00:20:41,620 --> 00:20:46,280
IF a jiný v případě, pokud,
IF n je menší než 2, jen se vrátit.

457
00:20:46,280 --> 00:20:47,580
Cítím se jako konstantním čase.

458
00:20:47,580 --> 00:20:50,970
Je to, druh, stejně jako dvou krocích,
IF n je menší než 2, pak se vrátíte.

459
00:20:50,970 --> 00:20:54,580
Ale jak jsme si řekli v pondělí,
konstantní čas, nebo velký O 1,

460
00:20:54,580 --> 00:20:57,130
mohou být dvě, tři kroky
kroky, dokonce i 1000 kroků.

461
00:20:57,130 --> 00:20:59,870
Důležité je, že je to
konstantní počet kroků.

462
00:20:59,870 --> 00:21:03,240
Takže žlutý zvýrazněné pseudocode
tady běží v, budeme říkat,

463
00:21:03,240 --> 00:21:04,490
konstantní čas.

464
00:21:04,490 --> 00:21:06,780
Takže více formálně, a
jdeme to-- to

465
00:21:06,780 --> 00:21:09,910
bude míra, do které
formalizovat toto právo now-- T n,

466
00:21:09,910 --> 00:21:15,030
běžící čas problému
že se n somethings jako vstup,

467
00:21:15,030 --> 00:21:19,150
rovná big o jedné,
IF n je menší než 2.

468
00:21:19,150 --> 00:21:20,640
Takže je to podmíněno to.

469
00:21:20,640 --> 00:21:24,150
Tak aby bylo jasno, když n je menší než
2, máme velmi krátký seznam, poté

470
00:21:24,150 --> 00:21:29,151
Doba chodu, T n, kde n je
1 nebo 0, v tomto velmi specifickém případě,

471
00:21:29,151 --> 00:21:30,650
je to jen bude konstantní čas.

472
00:21:30,650 --> 00:21:32,691
Bude to trvat jeden
krok, dva kroky, cokoliv.

473
00:21:32,691 --> 00:21:33,950
Je to pevně stanovený počet kroků.

474
00:21:33,950 --> 00:21:38,840
>> Takže šťavnaté část musí jistě být v
Druhým případem v pseudokódu.

475
00:21:38,840 --> 00:21:40,220
Případ ELSE.

476
00:21:40,220 --> 00:21:44,870
Třídit levou polovinu prvků, třídit vpravo
polovina z prvků, sloučit tříděných půlky.

477
00:21:44,870 --> 00:21:46,800
Jak dlouho trvá každý z těchto kroků trvat?

478
00:21:46,800 --> 00:21:49,780
No, v případě, že běží
čas, aby třídit n prvků

479
00:21:49,780 --> 00:21:53,010
je, nazvěme to velmi
obecně, T n,

480
00:21:53,010 --> 00:21:55,500
pak třídění levou
polovina elementů

481
00:21:55,500 --> 00:21:59,720
je trochu, jako říkat,
T n děleno 2,

482
00:21:59,720 --> 00:22:03,000
a podobně třídění pravou polovinu
prvků je, druh, jako říkat,

483
00:22:03,000 --> 00:22:06,974
T n rozdělena 2, a poté
slučování seřazené poloviny.

484
00:22:06,974 --> 00:22:08,890
No, pokud mám nějaký
počet prvků zde,

485
00:22:08,890 --> 00:22:11,230
stejně jako čtyři, a nějaké číslo
prvků tady, stejně jako čtyři,

486
00:22:11,230 --> 00:22:14,650
a já musím sloučit každé z těchto čtyř
v, a každé z těchto čtyř v, jeden

487
00:22:14,650 --> 00:22:17,160
po druhém tak, že
nakonec Mám osm prvků.

488
00:22:17,160 --> 00:22:20,230
Vypadá to, že to je velká o n kroků?

489
00:22:20,230 --> 00:22:23,500
Jestliže mám n prstů a každý z
jim musí být sloučeny do místa,

490
00:22:23,500 --> 00:22:25,270
to je jako další n kroků.

491
00:22:25,270 --> 00:22:27,360
>> Takže opravdu formulaically,
můžeme vyjádřit to,

492
00:22:27,360 --> 00:22:29,960
i když trochu děsivě zprvu
pohled, ale je to něco

493
00:22:29,960 --> 00:22:31,600
který zachycuje přesně tuto logiku.

494
00:22:31,600 --> 00:22:35,710
Doba běhu, T n, n IF
je větší než nebo rovno 2.

495
00:22:35,710 --> 00:22:42,500
V tomto případě, ELSE případě je T n
děleno 2 plus T n děleno 2,

496
00:22:42,500 --> 00:22:45,320
a velký o n, některé
lineární počet kroků,

497
00:22:45,320 --> 00:22:51,630
možná přesně n, možná 2 krát
n, ale je to zhruba, pořadí n.

498
00:22:51,630 --> 00:22:54,060
Tak to také, je to, jak můžeme
to vyjádřit formulaically.

499
00:22:54,060 --> 00:22:56,809
Teď už by neznal, pokud to není
které jste nahráli ve své mysli,

500
00:22:56,809 --> 00:22:58,710
nebo hledat to v
zadní učebnice, že

501
00:22:58,710 --> 00:23:00,501
může mít trochu
cheat sheet na konci,

502
00:23:00,501 --> 00:23:03,940
ale to je opravdu jít do
nám velkou o n log n,

503
00:23:03,940 --> 00:23:06,620
protože opakování, že
vidíte tady na obrazovce,

504
00:23:06,620 --> 00:23:09,550
pokud jste vlastně dělal to, s
nekonečný počet příkladů,

505
00:23:09,550 --> 00:23:13,000
nebo jste to udělal formulaically, že ne
vidět, že to, protože tento vzorec

506
00:23:13,000 --> 00:23:17,100
sám o sobě je rekurzivní, s t
n nad něčím na pravé straně,

507
00:23:17,100 --> 00:23:21,680
a t o n přes na levé straně, to může
ve skutečnosti být vyjádřeno, v konečném důsledku,

508
00:23:21,680 --> 00:23:24,339
jak velký go n log n.

509
00:23:24,339 --> 00:23:26,130
Pokud tomu tak není přesvědčen o tom, že je to
pokuta pro tuto chvíli, jen

510
00:23:26,130 --> 00:23:28,960
vzít na víře, že to je, opravdu,
co to vede k opakování,

511
00:23:28,960 --> 00:23:31,780
ale to je jen trochu více
matematický přístup k dívá

512
00:23:31,780 --> 00:23:36,520
v běžící době merge sort
na základě svého pseudokódu sám.

513
00:23:36,520 --> 00:23:39,030
>> Nyní se pojďme trochu
průduch z všechno,

514
00:23:39,030 --> 00:23:41,710
a vzít podívat se na
jistý bývalý senátor, který

515
00:23:41,710 --> 00:23:44,260
může vypadat trochu povědomý,
kdo si sedl s Google Eric

516
00:23:44,260 --> 00:23:48,410
Schmidt, před časem, na pohovor
na pódiu, v přední části celá parta

517
00:23:48,410 --> 00:23:53,710
lidí, mluví nakonec o
téma, to je docela teď povědomý.

518
00:23:53,710 --> 00:23:54,575
Pojďme se podívat.

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

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt: Nyní Senator,
jsi tady na Google,

521
00:24:03,890 --> 00:24:09,490
a já jsem rád myslet na
Předsednictví jako pracovní pohovor.

522
00:24:09,490 --> 00:24:11,712
Teď je těžké sehnat práci jako prezident.

523
00:24:11,712 --> 00:24:12,670
Prezident Obama: Správně.

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt: A ty jsi
dělat [neslyšitelný] teď.

525
00:24:13,940 --> 00:24:15,523
Je také těžké získat práci ve společnosti Google.

526
00:24:15,523 --> 00:24:17,700
Prezident Obama: Správně.

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt: Máme dotazy,
a žádáme naše kandidáty otázky,

528
00:24:21,330 --> 00:24:24,310
a tohle je od Larry Schwimmer.

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

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

531
00:24:27,005 --> 00:24:28,130
Myslíte si dělám legraci?

532
00:24:28,130 --> 00:24:30,590
Je to přímo tady.

533
00:24:30,590 --> 00:24:33,490
Jaký je nejúčinnější způsob, jak
třídit milion 32 bit celé číslo?

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

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

536
00:24:38,979 --> 00:24:41,020
Eric Schmidt: Někdy
Možná mi to líto, maybe--

537
00:24:41,020 --> 00:24:42,750
Prezident Obama: Ne, ne,
Ne, ne, ne, já think--

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt: To není to--

539
00:24:43,240 --> 00:24:45,430
Prezident Obama: Já
myslím, myslím, že bublinu

540
00:24:45,430 --> 00:24:46,875
sort by byl špatný způsob, jak jít.

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

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

543
00:24:50,535 --> 00:24:52,200
Kdo mu to řekl?

544
00:24:52,200 --> 00:24:54,020
DOBŘE.

545
00:24:54,020 --> 00:24:55,590
Nechtěl jsem počítač věda on--

546
00:24:55,590 --> 00:24:58,986
>> Prezident Obama: Máme
dostal své špehy tam.

547
00:24:58,986 --> 00:24:59,860
Profesor: Dobře.

548
00:24:59,860 --> 00:25:03,370
Nechme za námi nyní
teoretický svět algoritmů

549
00:25:03,370 --> 00:25:06,520
v asymptotické analýze
této smlouvy, a vrátit se do některá témata

550
00:25:06,520 --> 00:25:09,940
týden od nuly do jedné, a začátek
odstranit některé kolečka,

551
00:25:09,940 --> 00:25:10,450
chcete-li.

552
00:25:10,450 --> 00:25:13,241
Aby jste opravdu pochopit,
nakonec od základů, co je

553
00:25:13,241 --> 00:25:16,805
děje pod kapotou, když vás
psát, kompilovat a spouštět programy.

554
00:25:16,805 --> 00:25:19,680
Připomeňme, a zejména, že je to
První program v jazyce C jsme se na,

555
00:25:19,680 --> 00:25:22,840
kanonický, jednoduchý program
druhů, relativně vzato,

556
00:25:22,840 --> 00:25:24,620
kde, vytiskne, Hello World.

557
00:25:24,620 --> 00:25:27,610
A Vzpomínám si, že jsem řekl, proces
že zdrojový kód prochází

558
00:25:27,610 --> 00:25:28,430
je přesně to.

559
00:25:28,430 --> 00:25:31,180
Berete zdrojového kódu, projít
to přes kompilátor, jako je Clang,

560
00:25:31,180 --> 00:25:34,650
a ven vychází strojový kód, který
může vypadat takhle, nul a jedniček

561
00:25:34,650 --> 00:25:37,880
že procesor počítače, centrální
procesorová jednotka nebo mozku,

562
00:25:37,880 --> 00:25:39,760
nakonec chápe.

563
00:25:39,760 --> 00:25:42,460
>> Ukázalo se, že je to
bit jako zjednodušující,

564
00:25:42,460 --> 00:25:44,480
že jsme nyní v
Postoj k šprýmaři odděleně

565
00:25:44,480 --> 00:25:46,720
pochopit, co to opravdu bylo
děje pod kapotou

566
00:25:46,720 --> 00:25:48,600
pokaždé, když spustíte
Clang, nebo obecněji,

567
00:25:48,600 --> 00:25:53,040
pokaždé, když program,
pomocí funkce Provést a CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
Zejména, věci jako
to je nejprve generován,

569
00:25:56,760 --> 00:25:58,684
při prvním kompilaci programu.

570
00:25:58,684 --> 00:26:00,600
Jinými slovy, když vás
vezměte si zdrojový kód

571
00:26:00,600 --> 00:26:04,390
a zkompilovat, co je nejprve
bytí výstupu by Clang

572
00:26:04,390 --> 00:26:06,370
je něco, co znám jako assembleru.

573
00:26:06,370 --> 00:26:08,990
A ve skutečnosti, to vypadá přesně jako to.

574
00:26:08,990 --> 00:26:11,170
>> Běžel jsem příkaz u
příkazového řádku dříve.

575
00:26:11,170 --> 00:26:16,260
Řinčet DASH velkým S hello.c,
a to vytvořili soubor

576
00:26:16,260 --> 00:26:19,490
pro mě volal hello.s,
uvnitř které byly přesně

577
00:26:19,490 --> 00:26:22,290
tyto obsahy, a trochu více
výše a trochu níže,

578
00:26:22,290 --> 00:26:25,080
ale já jsem dal nejšťavnatější
Informace zde na obrazovce.

579
00:26:25,080 --> 00:26:29,190
A když se podíváte pozorně, uvidíte,
alespoň několik známých klíčová slova.

580
00:26:29,190 --> 00:26:31,330
Máme hlavní nahoře.

581
00:26:31,330 --> 00:26:35,140
Máme printf dole uprostřed.

582
00:26:35,140 --> 00:26:38,670
A máme také hello world
zpětné lomítko n v uvozovkách dole.

583
00:26:38,670 --> 00:26:42,450
>> A všechno ostatní tady
je návod na velmi nízké úrovni

584
00:26:42,450 --> 00:26:45,500
že procesor počítače rozumí.

585
00:26:45,500 --> 00:26:50,090
Pokyny pro CPU, které se pohybují paměť
kolem, že zatížení struny z paměti,

586
00:26:50,090 --> 00:26:52,750
a nakonec, tisk
věci na obrazovce.

587
00:26:52,750 --> 00:26:56,780
Teď, co se stane, když po
Tato sestava kód je generován?

588
00:26:56,780 --> 00:26:59,964
Nakonec, to uděláte, opravdu,
ještě tvořit objektový kód.

589
00:26:59,964 --> 00:27:02,630
Ale kroky, které mají opravdu
se děje pod kapotou

590
00:27:02,630 --> 00:27:04,180
vypadat trochu víc jako je tento.

591
00:27:04,180 --> 00:27:08,390
Zdrojový kód se stává kód assembleru,
který se pak stává kód objektu,

592
00:27:08,390 --> 00:27:11,930
a operativní pojmy jsou to,
při kompilaci zdrojového kódu,

593
00:27:11,930 --> 00:27:16,300
out přijde kód montáž, a pak
když si sestavit svou assembleru,

594
00:27:16,300 --> 00:27:17,800
out přijde objektový kód.

595
00:27:17,800 --> 00:27:20,360
>> Nyní Clang je super sofistikované,
jako hodně překladačů,

596
00:27:20,360 --> 00:27:23,151
a to dělá všechny tyto kroky
dohromady, a to není nezbytně

597
00:27:23,151 --> 00:27:25,360
Výstup jakýkoli meziprodukt
soubory, které můžete dokonce vidět.

598
00:27:25,360 --> 00:27:28,400
Prostě kompiluje věci,
což je obecný pojem, který

599
00:27:28,400 --> 00:27:30,000
popisuje celý tento proces.

600
00:27:30,000 --> 00:27:32,000
Ale pokud opravdu chcete
být konkrétní, je tu

601
00:27:32,000 --> 00:27:34,330
mnohem více děje i tam.

602
00:27:34,330 --> 00:27:38,860
>> Ale pojďme se také zvážit, že i teď
že mimořádně jednoduchý program, hello.c,

603
00:27:38,860 --> 00:27:40,540
nazývá funkce.

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

605
00:27:41,870 --> 00:27:46,900
Ale já jsem nepsal printf, opravdu,
který je dodáván s c, abych tak řekl.

606
00:27:46,900 --> 00:27:51,139
Je to funkce, připomeňme, že je to
deklarován ve standardním io.h, který

607
00:27:51,139 --> 00:27:53,180
je soubor záhlaví, který
je téma, budeme vlastně

608
00:27:53,180 --> 00:27:55,780
ponořit do větší hloubky, než dlouhý.

609
00:27:55,780 --> 00:27:58,000
Ale hlavičkový soubor je
obvykle doprovázené

610
00:27:58,000 --> 00:28:02,920
souborem kódu, zdrojový kód souboru, takže
stejně jako existuje standardní io.h.

611
00:28:02,920 --> 00:28:05,930
>> Před nějakým časem, někdo,
nebo něčí, také psal

612
00:28:05,930 --> 00:28:11,040
soubor s názvem standardní io.c, v
niž je skutečný definice,

613
00:28:11,040 --> 00:28:15,220
nebo implementace printf,
a trsy dalších funkcí,

614
00:28:15,220 --> 00:28:16,870
jsou ve skutečnosti v písemné formě.

615
00:28:16,870 --> 00:28:22,140
Takže vzhledem k tomu, že, pokud vezmeme v úvahu s
tady na levé straně, hello.c, že ​​když

616
00:28:22,140 --> 00:28:26,250
sestavovány, nám dává hello.s, i když
Clang netrápí úspory v místě

617
00:28:26,250 --> 00:28:31,360
můžeme vidět, a že kód shromáždění
dostane sestaveny do hello.o, který

618
00:28:31,360 --> 00:28:34,630
je, opravdu, výchozí název
vzhledem k tomu, kdykoli budete kompilovat zdroje

619
00:28:34,630 --> 00:28:39,350
kód do objektového kódu, ale nejsou
zcela připraven jej vykonat ještě,

620
00:28:39,350 --> 00:28:41,460
protože další krok
se musí stát, a má

621
00:28:41,460 --> 00:28:44,440
dělo v posledních několika
týdnů, možná bez vašeho vědomí k vám.

622
00:28:44,440 --> 00:28:47,290
>> Konkrétně někde
V CS50 IDE, a to,

623
00:28:47,290 --> 00:28:49,870
Také bude tak trochu
oversimplification na chvíli,

624
00:28:49,870 --> 00:28:54,670
tam je, nebo byl na nějaký čas,
soubor s názvem standardní io.c,

625
00:28:54,670 --> 00:28:58,440
že někdo sestavil do
standardní io.s nebo ekvivalent,

626
00:28:58,440 --> 00:29:02,010
že někdo pak shromáždil
do standardního io.o,

627
00:29:02,010 --> 00:29:04,600
nebo se ukáže na A
mírně odlišný soubor

628
00:29:04,600 --> 00:29:07,220
formát, který může mít jiný
příponu souboru úplně,

629
00:29:07,220 --> 00:29:11,720
ale v teorii a koncepčně, přesně
ty kroky se muselo stát v nějaké formě.

630
00:29:11,720 --> 00:29:14,060
Což znamená, že nyní
když píšu program,

631
00:29:14,060 --> 00:29:17,870
hello.c, že ​​jen říká, hello world,
a já jsem s použitím kódu někoho jiného

632
00:29:17,870 --> 00:29:22,480
jako printf, který byl kdysi
čas, v souboru s názvem standardní io.c,

633
00:29:22,480 --> 00:29:26,390
pak nějak musím Take My
objektový kód, moji nuly a jedničky,

634
00:29:26,390 --> 00:29:29,260
a že osoby objekt
kódu nebo nuly a jedničky,

635
00:29:29,260 --> 00:29:34,970
a nějak spojit je do
jeden poslední soubor, nazvaný ahoj, že

636
00:29:34,970 --> 00:29:38,070
má všechny nul a
ty z mé hlavní funkci,

637
00:29:38,070 --> 00:29:40,830
a všechny nul
a ty pro printf.

638
00:29:40,830 --> 00:29:44,900
>> A opravdu, že poslední proces je
volal, spojující vaše objektový kód.

639
00:29:44,900 --> 00:29:47,490
Jehož výstup
je spustitelný soubor.

640
00:29:47,490 --> 00:29:49,780
Takže ve spravedlnost, u
konec dne, nic

641
00:29:49,780 --> 00:29:52,660
změnilo od týdne jedna, když jsme
První začal sestavování programů.

642
00:29:52,660 --> 00:29:55,200
Ve skutečnosti, je to vše
děje pod kapotou,

643
00:29:55,200 --> 00:29:57,241
ale teď jsme v situaci,
kde můžeme skutečně

644
00:29:57,241 --> 00:29:58,794
šprýmaři odděleně tyto jednotlivé kroky.

645
00:29:58,794 --> 00:30:00,710
A skutečně, na konci
dne, jsme pořád

646
00:30:00,710 --> 00:30:04,480
odešel s nul a jedniček, které
je skutečně skvělý segue nyní

647
00:30:04,480 --> 00:30:08,620
na jiné schopnosti C, která
jsme neměli využívat největší pravděpodobností

648
00:30:08,620 --> 00:30:11,250
k dnešnímu dni, známý jako operátory bitové.

649
00:30:11,250 --> 00:30:15,220
Jinými slovy, tak daleko, kdykoliv máme
zabýval s daty v C nebo proměnných v C,

650
00:30:15,220 --> 00:30:17,660
jsme měli věci, jako
znaky a plováky a ins

651
00:30:17,660 --> 00:30:21,990
a touží a dvoulůžkové a podobně, ale
všechny z nich jsou nejméně osm bitů.

652
00:30:21,990 --> 00:30:25,550
My jsme ještě nikdy nebyl schopen
manipulovat s jednotlivými bity,

653
00:30:25,550 --> 00:30:28,970
i když individuální bitu, jsme
Víte, mohou představovat 0 a 1.

654
00:30:28,970 --> 00:30:32,640
Nyní se ukazuje, že v C, vy
mohou získat přístup k jednotlivých bitů,

655
00:30:32,640 --> 00:30:35,530
pokud víte, syntaxi,
s nimiž se dostat na ně.

656
00:30:35,530 --> 00:30:38,010
>> Takže pojďme se podívat
na operátory bitové.

657
00:30:38,010 --> 00:30:41,700
Tak tady na snímku je několik symboly, které
jsme se, druh, druh, předtím neviděl.

658
00:30:41,700 --> 00:30:45,580
Vidím ampersand, vertikální
bar, a některé další, stejně,

659
00:30:45,580 --> 00:30:49,430
a připomněla, že ampersand ampersand
je něco, co jsme neviděli.

660
00:30:49,430 --> 00:30:54,060
Logická AND operátor, kde musíte
dva z nich společně, nebo logické OR

661
00:30:54,060 --> 00:30:56,300
operátor, kde na vás
mají dva svislé pruhy.

662
00:30:56,300 --> 00:31:00,550
Bitové operátory, které budeme
viz fungují na bity jednotlivě,

663
00:31:00,550 --> 00:31:03,810
stačí použít jeden ampersand, je
single svislá čára, stříška symbol

664
00:31:03,810 --> 00:31:06,620
přijde příště, malý
vlnovky, a pak doleva

665
00:31:06,620 --> 00:31:08,990
držák levý držák, nebo
pravá závorka pravá závorka.

666
00:31:08,990 --> 00:31:10,770
Každý z nich má různé významy.

667
00:31:10,770 --> 00:31:11,950
>> Ve skutečnosti, pojďme se podívat.

668
00:31:11,950 --> 00:31:16,560
Pojďme stará škola dnes, a použití
dotyková obrazovka z dávných dob,

669
00:31:16,560 --> 00:31:18,002
známý jako bílou tabuli.

670
00:31:18,002 --> 00:31:19,710
A to bílé tabule
bude nám neumožňuje,

671
00:31:19,710 --> 00:31:27,360
vyjadřovat některé docela jednoduché symboly,
nebo spíše některé poměrně jednoduché vzorce,

672
00:31:27,360 --> 00:31:29,560
že se pak můžeme nakonec
pákový efekt, za účelem

673
00:31:29,560 --> 00:31:33,230
individuální přístup
bity v rámci programu C.

674
00:31:33,230 --> 00:31:34,480
Jinými slovy, jdeme na to.

675
00:31:34,480 --> 00:31:37,080
Let první mluvit Aby
moment o ampersand,

676
00:31:37,080 --> 00:31:39,560
což je bitové operace AND operátor.

677
00:31:39,560 --> 00:31:42,130
Jinými slovy, je to
operátor, který umožňuje

678
00:31:42,130 --> 00:31:45,930
abych si levostranné proměnné
typicky, a pravá variabilní,

679
00:31:45,930 --> 00:31:50,640
nebo individuální hodnotu, že pokud budeme A
je dohromady, mi dává konečný výsledek.

680
00:31:50,640 --> 00:31:51,560
Tak co mám na mysli?

681
00:31:51,560 --> 00:31:54,840
Je-li v programu, máte proměnnou
, který ukládá jednu z těchto hodnot,

682
00:31:54,840 --> 00:31:58,000
nebo řekněme, aby to jednoduché, a jen
vypsat nulami a jedničkami jednotlivě,

683
00:31:58,000 --> 00:32:00,940
Zde je návod, jak operátor ampersand funguje.

684
00:32:00,940 --> 00:32:06,400
0 ampersand 0 se bude rovnat 0.

685
00:32:06,400 --> 00:32:07,210
Teď proč je tomu tak?

686
00:32:07,210 --> 00:32:09,291
>> Je to velmi podobné
Boolean výrazy,

687
00:32:09,291 --> 00:32:10,540
že jsme diskutovali doposud.

688
00:32:10,540 --> 00:32:15,800
Pokud si myslíte, že po tom všem, 0
false, 0 je false, false false

689
00:32:15,800 --> 00:32:18,720
je, jak jsme diskutovali
logicky, také falešné.

690
00:32:18,720 --> 00:32:20,270
Tak dostaneme 0 i zde.

691
00:32:20,270 --> 00:32:24,390
Pokud budete mít 0 ampersand
1, dobře, že taky,

692
00:32:24,390 --> 00:32:29,890
bude být 0, protože pro tento
levá exprese aby to byla pravda nebo 1,

693
00:32:29,890 --> 00:32:32,360
to by musela být pravdivá a pravdivá.

694
00:32:32,360 --> 00:32:36,320
Ale tady máme false
a pravdivé, nebo 0 a 1.

695
00:32:36,320 --> 00:32:42,000
A teď zase, máme-li 1 ampersand
0, to také bude 0,

696
00:32:42,000 --> 00:32:47,240
a pokud budeme mít 1 ampersand 1,
Nakonec to máme 1 bit.

697
00:32:47,240 --> 00:32:50,340
Takže jinými slovy, my neděláme
něco zajímavého s tímto operátorem

698
00:32:50,340 --> 00:32:51,850
ještě ne, tento operátor ampersand.

699
00:32:51,850 --> 00:32:53,780
Je to bitové operace AND operátor.

700
00:32:53,780 --> 00:32:57,290
Ale to jsou ingredience
přes který můžeme udělat

701
00:32:57,290 --> 00:32:59,240
zajímavých věcí, jak brzy uvidíme.

702
00:32:59,240 --> 00:33:02,790
>> Nyní se pojďme podívat na právě jeden
svislá čára tady na pravé straně.

703
00:33:02,790 --> 00:33:06,710
Pokud mám 0 bit a I
NEBO to s, bitové

704
00:33:06,710 --> 00:33:11,030
OR operátor, další 0 bit,
, co se děje, aby mi 0.

705
00:33:11,030 --> 00:33:17,540
Pokud bych se trochu 0 a nebo to s
1 bit, a pak budu mít 1.

706
00:33:17,540 --> 00:33:19,830
A ve skutečnosti, jen pro
jasnost, nech mě jít zpátky,

707
00:33:19,830 --> 00:33:23,380
takže moje svislé pruhy
nejsou splést 1 je.

708
00:33:23,380 --> 00:33:26,560
Dovolte mi, abych přepsat všechny
můj 1 je trochu více

709
00:33:26,560 --> 00:33:32,700
Je zřejmé, že tak, že vedle vidět, je-li I
mají 1 nebo 0, že to bude 1,

710
00:33:32,700 --> 00:33:39,060
a když mám 1 nebo 1, která,
Také bude 1.

711
00:33:39,060 --> 00:33:42,900
Takže můžete vidět, že logicky OR
operátor se chová velmi odlišně.

712
00:33:42,900 --> 00:33:48,070
To mi dává 0 nebo 0 mi dává 0, ale
každá jiná kombinace mi dává 1.

713
00:33:48,070 --> 00:33:52,480
Tak dlouho, jak budu mít jeden 1 V
vzorec, výsledek bude 1.

714
00:33:52,480 --> 00:33:55,580
>> Na rozdíl od AND
operátor, ampersand,

715
00:33:55,580 --> 00:34:00,940
pouze tehdy, když mám dvě 1 je v
rovnice, mohu skutečně dostat do vedení 1 out.

716
00:34:00,940 --> 00:34:02,850
Teď je tu několik dalších
Provozovatelé stejně.

717
00:34:02,850 --> 00:34:04,810
Jedním z nich je trochu více zapojit.

718
00:34:04,810 --> 00:34:07,980
Tak nech mě jít dopředu a vymazat
to, aby se uvolnily nějaké místo.

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

720
00:34:13,020 --> 00:34:16,460
A pojďme se podívat na
stříška symbol, jen na chvíli.

721
00:34:16,460 --> 00:34:18,210
Toto je typicky
znak můžete zadat

722
00:34:18,210 --> 00:34:21,420
na klávesnici SHIFT a
pak jedno z čísel na vrcholku vaší USA

723
00:34:21,420 --> 00:34:22,250
klávesnice.

724
00:34:22,250 --> 00:34:26,190
>> Tak tohle je exkluzivní
OR operátor, exclusive OR.

725
00:34:26,190 --> 00:34:27,790
Takže jsme právě viděli provozovatelem nebo.

726
00:34:27,790 --> 00:34:29,348
Toto je exkluzivní OR operátor.

727
00:34:29,348 --> 00:34:30,639
Jaký je vlastně rozdíl?

728
00:34:30,639 --> 00:34:34,570
Tak pojďme stačí se podívat na vzorec,
a použít jako přísady v konečném důsledku.

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

730
00:34:37,690 --> 00:34:39,650
Já jsem chtěl říct, je vždy 0.

731
00:34:39,650 --> 00:34:41,400
To je definice XOR.

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

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 bude 1,
a 1 XOR 1 bude?

734
00:34:58,810 --> 00:34:59,890
Špatné?

735
00:34:59,890 --> 00:35:00,520
Nebo ne?

736
00:35:00,520 --> 00:35:01,860
Nevím.

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

738
00:35:02,810 --> 00:35:04,700
A teď, co se tady děje?

739
00:35:04,700 --> 00:35:06,630
No přemýšlet o
název tohoto operátora.

740
00:35:06,630 --> 00:35:09,980
Exkluzivní OR, tak jak
jméno, druh, naznačuje,

741
00:35:09,980 --> 00:35:13,940
odpověď bude pouze
1, pokud vstupy jsou exkluzivní,

742
00:35:13,940 --> 00:35:15,560
výhradně různé.

743
00:35:15,560 --> 00:35:18,170
Tak tady vstupy jsou
stejné, takže na výstupu je 0.

744
00:35:18,170 --> 00:35:20,700
Zde vstupy jsou
stejné, takže na výstupu je 0.

745
00:35:20,700 --> 00:35:25,640
Zde jsou výstupy jsou odlišné,
jsou exkluzivní, a tak výstup je 1.

746
00:35:25,640 --> 00:35:28,190
Takže je to velmi podobné
A je to velmi podobné,

747
00:35:28,190 --> 00:35:32,760
nebo spíše je to velmi podobné
OR, ale pouze v exkluzivním způsobem.

748
00:35:32,760 --> 00:35:36,210
Tato je již není 1,
protože máme dvě 1 je,

749
00:35:36,210 --> 00:35:38,621
a ne výlučně, jen jeden z nich.

750
00:35:38,621 --> 00:35:39,120
Dobře.

751
00:35:39,120 --> 00:35:40,080
A co ostatní?

752
00:35:40,080 --> 00:35:44,220
No tilda, zatím, je
skutečně pěkný a jednoduchý, naštěstí.

753
00:35:44,220 --> 00:35:46,410
A to je unární
operátor, což znamená, že

754
00:35:46,410 --> 00:35:50,400
to je aplikován pouze na jeden vstup,
jedním operand, abych tak řekl.

755
00:35:50,400 --> 00:35:51,800
Není na levé a pravé.

756
00:35:51,800 --> 00:35:56,050
Jinými slovy, pokud budete mít na vlnovku
0, odpověď bude opačný.

757
00:35:56,050 --> 00:35:59,710
A pokud budete mít vlnovky z 1,
odpověď bude naopak.

758
00:35:59,710 --> 00:36:02,570
Takže tilda provozovatel
způsob, jak negování trochu,

759
00:36:02,570 --> 00:36:06,000
nebo obracející kousek od
0-1, nebo od 1 do 0 ° C.

760
00:36:06,000 --> 00:36:09,820
>> A to nás nechává konečně
s pouhými dvěma konečnými operátory,

761
00:36:09,820 --> 00:36:13,840
tzv doleva posun, a
takzvaný doprava operátor posunu.

762
00:36:13,840 --> 00:36:16,620
Pojďme se podívat na to, jak této práci.

763
00:36:16,620 --> 00:36:20,780
Provozovatel vlevo posun, psaný
se dvěma lomených závorkách, jako je to,

764
00:36:20,780 --> 00:36:22,110
pracuje následovně.

765
00:36:22,110 --> 00:36:27,390
Pokud je můj vstup, nebo má operand, vlevo
operátor posun je jednoduše 1.

766
00:36:27,390 --> 00:36:33,750
A já pak říci počítače na
je vlevo posun, že 1, řekněme sedm míst,

767
00:36:33,750 --> 00:36:37,150
Výsledkem je, jako bych
přijmout, že 1, a přesunout ji

768
00:36:37,150 --> 00:36:40,160
sedm míst, více než na
vlevo, a ve výchozím nastavení,

769
00:36:40,160 --> 00:36:42,270
budeme předpokládat, že
prostor na pravé straně

770
00:36:42,270 --> 00:36:44,080
se bude ořezán nulami.

771
00:36:44,080 --> 00:36:50,316
Jinými slovy, 1 učinilo posun 7 se děje
aby mi, že 1, následovaný 1, 2, 3,

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

773
00:36:54,060 --> 00:36:57,380
Takže svým způsobem to vám umožní
trvat malé množství jako 1,

774
00:36:57,380 --> 00:37:00,740
a jasně, aby to hodně
mnohem, mnohem větší, tímto způsobem,

775
00:37:00,740 --> 00:37:06,460
ale my jsme vlastně bude vidět
chytřejší přístupy k ní

776
00:37:06,460 --> 00:37:08,080
místo toho, jakož i,

777
00:37:08,080 --> 00:37:08,720
>> Dobře.

778
00:37:08,720 --> 00:37:10,060
To je pro tři týden.

779
00:37:10,060 --> 00:37:11,400
Uvidíme se příště.

780
00:37:11,400 --> 00:37:12,770
To bylo CS50.

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

782
00:37:17,270 --> 00:37:22,243
>> [Přehrávání hudby]

783
00:37:22,243 --> 00:37:25,766
>> Reproduktor 1: On byl u občerstvení
bar jíst hot fudge pohár.

784
00:37:25,766 --> 00:37:28,090
Měl to všechno přes obličej.

785
00:37:28,090 --> 00:37:30,506
Má na sobě, že čokoláda jako vousy

786
00:37:30,506 --> 00:37:31,756
SPEAKER 2: Co to děláš?

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

788
00:37:32,422 --> 00:37:33,500
Cože?

789
00:37:33,500 --> 00:37:36,800
>> SPEAKER 2: Věděli jste právě double dip?

790
00:37:36,800 --> 00:37:38,585
Ty double ponořil čipu.

791
00:37:38,585 --> 00:37:39,460
SPEAKER 3: Promiňte.

792
00:37:39,460 --> 00:37:44,440
SPEAKER 2: ponořil jste čip, budete
vzal sousto, a znovu ponořil.

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

794
00:37:44,940 --> 00:37:48,440
SPEAKER 2: Takže to je jako dávat
Celá vaše ústa přímo v dip.

795
00:37:48,440 --> 00:37:52,400
Příště budete mít čip,
ponořit jen jednou, a nakonec to.

796
00:37:52,400 --> 00:37:53,890
>> SPEAKER 3: Víš co, Dane?

797
00:37:53,890 --> 00:37:58,006
Můžete ponořit způsob, jakým chcete ponořit.

798
00:37:58,006 --> 00:38:01,900
Budu ponořit způsob, jakým chci ponořit.

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