1
00:00:00,000 --> 00:00:11,904
>> [MUZIKO Ludante]

2
00:00:11,904 --> 00:00:12,910
>> PROFESORO: Bone.

3
00:00:12,910 --> 00:00:16,730
Jen CS50 kaj ĉi tiu estas
la fino de semajno tri.

4
00:00:16,730 --> 00:00:20,230
Do ni estas ĉi tie hodiaŭ, ne en Sanders
Teatro, anstataŭ en Weidner Biblioteko.

5
00:00:20,230 --> 00:00:23,170
Ene de kio estas studo
konata kiel Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
aux ni diru Studio H, aux cxu
ni say-- se vi ĝuis tiun ŝercon,

7
00:00:28,310 --> 00:00:30,540
ĝi estas fakte de
samklasano, Marko, rete,

8
00:00:30,540 --> 00:00:32,420
kiu sugestis tiel tra Twitter.

9
00:00:32,420 --> 00:00:34,270
Nun kio estas malvarmeta pri
esti tie en studio

10
00:00:34,270 --> 00:00:38,410
estas ke mi ĉirkaŭitaj de tiuj verdaj
muroj, verda ekrano aŭ chromakey,

11
00:00:38,410 --> 00:00:43,290
tiel diri, kio signifas ke CS50 la
produktteamo, nekonata al mi

12
00:00:43,290 --> 00:00:47,380
ĝuste nun, povus esti metante
min plej ie ajn en la mondo,

13
00:00:47,380 --> 00:00:48,660
por bone aŭ por malbone.

14
00:00:48,660 --> 00:00:51,800
>> Nun kio estas antauxe, problemo aro
du estas en viaj manoj por tiu semajno,

15
00:00:51,800 --> 00:00:53,830
sed kun problemo aro
tri ĉi venanta semajnon,

16
00:00:53,830 --> 00:00:56,600
Vi estos defiita kun
la tn ludo de 15,

17
00:00:56,600 --> 00:00:58,960
malnova partio favoro ke
vi eble memoras ricevanta

18
00:00:58,960 --> 00:01:02,030
kiel infano kiu havas tutan faskon
de nombroj kiuj povas gliti supren, suben,

19
00:01:02,030 --> 00:01:05,790
maldekstre kaj dekstre, kaj tie estas unu breĉo
ene de la enigmo, en kiun vi

20
00:01:05,790 --> 00:01:07,840
povas fakte gliti tiuj puzlo pecoj.

21
00:01:07,840 --> 00:01:11,150
Finfine vi ricevis ĉi
puzlo en iuj duon hazarda ordo,

22
00:01:11,150 --> 00:01:12,940
kaj la celo estas
ordigi ĝin, supre sube,

23
00:01:12,940 --> 00:01:16,310
maldekstre dekstren, de unu
tutan vojon supren tra 15.

24
00:01:16,310 --> 00:01:19,360
>> Bedaŭrinde, la efektivigo
vi devos mane

25
00:01:19,360 --> 00:01:21,590
tuj esti programaro
bazita, ne fizike.

26
00:01:21,590 --> 00:01:25,280
Vi efektive tuj havos skribi
kodo kun kiu studento aŭ uzanto povas

27
00:01:25,280 --> 00:01:26,760
ludi la ludon de 15.

28
00:01:26,760 --> 00:01:29,030
Kaj fakte, en la hacker
eldono de ludo de 15,

29
00:01:29,030 --> 00:01:32,155
Vi estos defio al implementar,
Ne nur la ludado de tiu malnova lernejo

30
00:01:32,155 --> 00:01:35,010
ludo, sed prefere la solvado
de ĝi, implementando dio moduso,

31
00:01:35,010 --> 00:01:38,280
tiel diri, ke reale
solvas la enigmon por la homaj,

32
00:01:38,280 --> 00:01:41,080
provizante ilin per aludo,
post aludo, post aludo.

33
00:01:41,080 --> 00:01:42,280
Do pli en tiu proksima semajno.

34
00:01:42,280 --> 00:01:43,720
Sed tio kio kuŝas antaŭen.

35
00:01:43,720 --> 00:01:47,610
>> Por nun memoras ke antaŭe ĉi tiu semajno
ni havis ĉi cliffhanger, se vi volas,

36
00:01:47,610 --> 00:01:52,560
per kio la plej bona ni faris ordiga
saĝa estis supera baro de big o de n

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

38
00:01:53,210 --> 00:01:56,520
Alivorte, bobelo varo,
selektado varon, inserción varo,

39
00:01:56,520 --> 00:01:59,120
ĉiuj el ili, dum malsamaj
en ilia efektivigo,

40
00:01:59,120 --> 00:02:03,480
ekhavis en n kvadratoj kurante
tempo en la plej malbona kazo.

41
00:02:03,480 --> 00:02:06,010
Kaj ni ĝenerale supozas ke
la plej malbona kazo por ordigado

42
00:02:06,010 --> 00:02:08,814
Estas kiu via enigoj
estas tute malantaŭen.

43
00:02:08,814 --> 00:02:11,980
Kaj ja, ĝi prenis tre kelkajn paŝojn
implementar ĉiu de tiuj algoritmoj.

44
00:02:11,980 --> 00:02:15,110
>> Nun je la fino de klaso
revokon, ni komparis bobelo varo

45
00:02:15,110 --> 00:02:19,390
kontraŭ selektado speco kontraŭ unu alia
ke ni nomis merge speco tiutempe,

46
00:02:19,390 --> 00:02:22,120
kaj mi proponas ke ĝi estas prenanta
avantaĝon lecionon de semajno

47
00:02:22,120 --> 00:02:24,060
nulo, dividi kaj venki.

48
00:02:24,060 --> 00:02:28,810
Kaj iel atingi ian
logaritma rultempo finfine,

49
00:02:28,810 --> 00:02:31,024
anstataŭ ion
ke estas pure kvadrata.

50
00:02:31,024 --> 00:02:33,440
Kaj ĝi ne estas sufiĉe logaritma,
estas iom pli ol tio.

51
00:02:33,440 --> 00:02:36,520
Sed se vi memoras de klaso,
estis multe, multe pli rapida.

52
00:02:36,520 --> 00:02:38,210
Ni rigardu, kie ni cxesis.

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

54
00:02:41,880 --> 00:02:45,370
>> Bobelo varo kontre selektado
ia kontre merge varon.

55
00:02:45,370 --> 00:02:47,700
Nun ili ĉiuj kuras, en
teorio, samtempe.

56
00:02:47,700 --> 00:02:50,510
La CPU kuras ĉe la sama rapido.

57
00:02:50,510 --> 00:02:54,990
Sed vi povas senti kiel enuiga ĉi
Estas tre rapide tuj fariĝis,

58
00:02:54,990 --> 00:02:58,790
kaj kiom rapida, kiam ni injekti
iom de semajno nulo la algoritmoj,

59
00:02:58,790 --> 00:03:00,080
ni povas akceli aĵojn.

60
00:03:00,080 --> 00:03:01,630
>> Do markon speco aspektas miriga.

61
00:03:01,630 --> 00:03:05,220
Kiel ni povas utiligi ĝin, por
ordigi nombroj pli rapide.

62
00:03:05,220 --> 00:03:07,140
Bone ni pensas reen
al ingredienco kiun ni

63
00:03:07,140 --> 00:03:10,380
havis reen en semajno nulo, tiu de
sercxas iu en telefono libro,

64
00:03:10,380 --> 00:03:12,380
kaj memoras ke la
_pseudocode_ ke ni proponis,

65
00:03:12,380 --> 00:03:14,560
tra kiu ni povas trovi
iu kiel Mike Smith,

66
00:03:14,560 --> 00:03:16,310
aspektis iom io tiamaniere.

67
00:03:16,310 --> 00:03:20,820
>> Nun rigardu en aparta
ĉe la linio 7 kaj 8, kaj 10 kaj 11,

68
00:03:20,820 --> 00:03:25,240
kiu induktas ke buklo, per kiu ni gardis
revenanta al linio 3 denove, kaj denove,

69
00:03:25,240 --> 00:03:26,520
kaj denove.

70
00:03:26,520 --> 00:03:31,790
Sed rezultu ke ni povas vidi
tiu algoritmo, tie en _pseudocode_,

71
00:03:31,790 --> 00:03:33,620
iom pli amplekse.

72
00:03:33,620 --> 00:03:35,960
Fakte, kion mi serĉas
ĉe tie sur la ekrano,

73
00:03:35,960 --> 00:03:41,180
estas algoritmo por serĉanta
Mike Smith inter iu aro de paĝoj.

74
00:03:41,180 --> 00:03:45,520
Kaj efektive, ni povus simpligi ĉi
algoritmo en tiuj linioj 7 kaj 8,

75
00:03:45,520 --> 00:03:49,860
kaj 10 kaj 11 por nur diras,
kiun mi prezentis ĉi tie en flava.

76
00:03:49,860 --> 00:03:52,210
En aliaj vortoj, se Mike
Forgxiston estas pli frue en la libro,

77
00:03:52,210 --> 00:03:55,004
ni ne bezonas specifi paŝo
paŝo nun kiel iri trovi lin.

78
00:03:55,004 --> 00:03:56,920
Ni ne devas specifi
reiri al la linio 3,

79
00:03:56,920 --> 00:03:58,960
Kial ni ne simple anstataŭe,
diru, pli ĝenerale,

80
00:03:58,960 --> 00:04:01,500
serĉi Mike en la
maldekstra duono de la libro.

81
00:04:01,500 --> 00:04:03,960
>> Male, se Mike estas
fakte poste en la libro,

82
00:04:03,960 --> 00:04:07,540
kial ni ne simple citi unquote serĉo
Mike en la dekstra duono de la libro.

83
00:04:07,540 --> 00:04:11,030
Alivorte, kial ni ne simple
ia puŝpeli al ni dirante,

84
00:04:11,030 --> 00:04:13,130
serĉi Mike en tiu
subaro de la libro,

85
00:04:13,130 --> 00:04:16,279
kaj lasi ĝin al nia ekzistanta
Algoritmo por diri nin

86
00:04:16,279 --> 00:04:18,750
kiel sercxi por Mike en
ke maldekstran duonon de la libro.

87
00:04:18,750 --> 00:04:20,750
Alivorte, nia
algoritmo laboras ĉu ĝi estas

88
00:04:20,750 --> 00:04:24,670
telefono libro de dikeco, de tiu
dikeco, aŭ ajna dikeco whatsoever.

89
00:04:24,670 --> 00:04:27,826
Do ni povas rikure
difini tiun algoritmon.

90
00:04:27,826 --> 00:04:29,950
En aliaj vortoj, sur la
ekrano tie, estas algoritmo

91
00:04:29,950 --> 00:04:33,130
por serĉi Mike Smith
inter la paĝoj de telefono libro.

92
00:04:33,130 --> 00:04:37,410
Do en linio 7 kaj 10, ni
nur diru precize tion.

93
00:04:37,410 --> 00:04:40,250
Kaj mi uzas tiun terminon momente
antaŭe, Kaj efektive, rekursio

94
00:04:40,250 --> 00:04:42,450
estas la buzzword por nun,
kaj estas tiu procezo

95
00:04:42,450 --> 00:04:47,210
fari ion cikla de iel
uzante kodon kiun vi jam havas,

96
00:04:47,210 --> 00:04:49,722
kaj nomante ĝin denove,
kaj denove, kaj denove.

97
00:04:49,722 --> 00:04:51,930
Nun ĝi estas tuj estos grava
ke ni iel fundo

98
00:04:51,930 --> 00:04:53,821
eksteren, kaj ne faras tion malfinie longa.

99
00:04:53,821 --> 00:04:56,070
Alie ni tuj
havas ja senfina ciklo.

100
00:04:56,070 --> 00:04:59,810
Sed ni vidu se ni povas pruntepreni tiun ideon
de rikuro, farante ion denove

101
00:04:59,810 --> 00:05:03,600
kaj denove kaj denove, solvi
la ordigado problemo tra merge

102
00:05:03,600 --> 00:05:05,900
varon, des pli efike.

103
00:05:05,900 --> 00:05:06,970
>> Do mi donos al vi kunfandi speco.

104
00:05:06,970 --> 00:05:07,920
Ni rigardu.

105
00:05:07,920 --> 00:05:10,850
Do jen _pseudocode_, kun
kiun ni povus apliki ordigado,

106
00:05:10,850 --> 00:05:12,640
uzante tiun algoritmon vokis merge varon.

107
00:05:12,640 --> 00:05:13,880
Kaj ĝi estas tute simple tio.

108
00:05:13,880 --> 00:05:15,940
Sur enigo de n eroj,
en aliaj vortoj, se vi estas

109
00:05:15,940 --> 00:05:18,830
donita n elementoj kaj nombrojn kaj
literoj aŭ nenial la enigo estas,

110
00:05:18,830 --> 00:05:22,430
se vi donita n eroj, se
n estas malpli ol 2, simple reveni.

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

112
00:05:22,930 --> 00:05:26,430
Ĉar se n estas malpli ol 2, ke
signifas ke mia listo de elementoj

113
00:05:26,430 --> 00:05:30,446
estas aŭ de amplekso 0 aŭ 1, kaj
en ambaŭ de tiuj bagatelaj okazoj,

114
00:05:30,446 --> 00:05:31,570
la listo estas jam ordo.

115
00:05:31,570 --> 00:05:32,810
Se ne estas lerta, ĝi estas ordo.

116
00:05:32,810 --> 00:05:35,185
Kaj se tie estas listo de longo
1, ĝi estas evidente ordigita.

117
00:05:35,185 --> 00:05:38,280
Do la algoritmo bezonas nur
vere fari ion interesan,

118
00:05:38,280 --> 00:05:40,870
se ni havas du aŭ pli
elementoj donita al ni.

119
00:05:40,870 --> 00:05:42,440
Do ni rigardu la magio tiam.

120
00:05:42,440 --> 00:05:47,500
Else ordigi la maldekstra duono de la elementoj,
tiam ordigi la dekstra duono de elementoj,

121
00:05:47,500 --> 00:05:49,640
tiam kunfandi la ordo duonoj.

122
00:05:49,640 --> 00:05:52,440
Kaj kio estas speco de menso fleksanta
tie, estas ke mi ne vere

123
00:05:52,440 --> 00:05:56,190
sxajne diris vin
ion nur ankoraŭ, ĉu ne?

124
00:05:56,190 --> 00:05:59,560
Ĉiuj mi diris estas, donita listo de
n eroj, ordigi la maldekstra duono,

125
00:05:59,560 --> 00:06:01,800
tiam la dekstran duonon, do
kunfandi la ordo duonoj,

126
00:06:01,800 --> 00:06:03,840
sed kie estas la efektiva sekreta saŭco?

127
00:06:03,840 --> 00:06:05,260
Kie estas la algoritmo?

128
00:06:05,260 --> 00:06:09,150
Bone ĝi rezultas ke tiuj du linioj
unua, varo lasis duonon de elementoj,

129
00:06:09,150 --> 00:06:13,970
kaj varo pravas duono de elementoj,
estas rekursiaj vokoj, tiel diri.

130
00:06:13,970 --> 00:06:16,120
>> Post ĉiu, ĉe tiu
punkto en tempo, ĉu mi havas

131
00:06:16,120 --> 00:06:18,950
algoritmo kun kiu
ordigi tuta amaso de elementoj?

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

133
00:06:19,450 --> 00:06:20,620
Ĝi estas ĝuste ĉi tie.

134
00:06:20,620 --> 00:06:25,180
Ĝi estas ĝuste sur la ekrano, kaj
do mi povas uzi tiun saman aron de paŝoj

135
00:06:25,180 --> 00:06:28,500
ordigi la maldekstra duono,
kiel mi povas la dekstra duono.

136
00:06:28,500 --> 00:06:30,420
Kaj ja, denove kaj denove.

137
00:06:30,420 --> 00:06:34,210
Do iumaniere, kaj ni baldaŭ
vidi tion, la magio de merge varo

138
00:06:34,210 --> 00:06:37,967
estas enigita en tiu finalo
linio, kunfandante la ordo duonoj.

139
00:06:37,967 --> 00:06:39,300
Kaj tio ŝajnas sufiĉe intuicia.

140
00:06:39,300 --> 00:06:41,050
Vi prenu du duonoj, kaj vi,
iel, kunfandi ilin kune,

141
00:06:41,050 --> 00:06:43,260
kaj ni vidos tiun
konkrete en momento.

142
00:06:43,260 --> 00:06:45,080
>> Sed tio estas kompleta algoritmo.

143
00:06:45,080 --> 00:06:46,640
Kaj ni vidos ekzakte kial.

144
00:06:46,640 --> 00:06:50,912
Nu supozu ke ni donis tiujn samajn
ok elementoj tie sur la ekrano, unu

145
00:06:50,912 --> 00:06:53,120
tra ok, sed ili estas
en ŝajne hazarda ordo.

146
00:06:53,120 --> 00:06:55,320
Kaj la celo ĉe mano estas
ordigi tiujn elementojn.

147
00:06:55,320 --> 00:06:58,280
Nu kiel mi iros pri
faranta ĝin uzanta, denove,

148
00:06:58,280 --> 00:07:00,407
kunfandi speco, kiel po ĉi _pseudocode_?

149
00:07:00,407 --> 00:07:02,740
Kaj denove, ingrain ĉi en
via menso, por nur momento.

150
00:07:02,740 --> 00:07:05,270
La unua kazo estas sufiĉe
bagatela, se ĝi estas malpli ol 2,

151
00:07:05,270 --> 00:07:07,060
simple reveni, ne estas laboro farenda.

152
00:07:07,060 --> 00:07:09,290
Do vere tie estas nur tri
paŝojn por vere teni en menso.

153
00:07:09,290 --> 00:07:11,081
Denove kaj denove, mi estas
tuj volas havi

154
00:07:11,081 --> 00:07:13,980
ordigi la maldekstra duono,
ordigi la dekstra duono,

155
00:07:13,980 --> 00:07:15,890
kaj tiam iam iliajn
du duonoj estas ordigataj

156
00:07:15,890 --> 00:07:18,710
Mi volas kunfandi ilin kune
en unu ordo listo.

157
00:07:18,710 --> 00:07:19,940
Observu do, ke en menso.

158
00:07:19,940 --> 00:07:21,310
>> Do jen la originala listo.

159
00:07:21,310 --> 00:07:23,510
Ni traktos tion kiel
ornamo, ni komencis

160
00:07:23,510 --> 00:07:25,800
en semajno du, kio estas
apuda bloko de memoro.

161
00:07:25,800 --> 00:07:28,480
En tiu kazo, enhavanta ok
nombroj, malantaŭo al malantaŭo al dorso.

162
00:07:28,480 --> 00:07:30,700
Kaj ni nun apliku merge varon.

163
00:07:30,700 --> 00:07:33,300
Do mi unue volas ordigi
la maldekstra duono de la listo,

164
00:07:33,300 --> 00:07:37,370
kaj ni, do,
temigi 4, 8, 6, kaj 2.

165
00:07:37,370 --> 00:07:41,000
>> Nun kiel mi iros pri
ordiga listo de grandeco 4?

166
00:07:41,000 --> 00:07:45,990
Nu mi devas nun konsideri
ordigado la maldekstra de la maldekstra duono.

167
00:07:45,990 --> 00:07:47,720
Denove, ni malantaŭenigi por nur momento.

168
00:07:47,720 --> 00:07:51,010
Se la _pseudocode_ estas tiu,
kaj Mi transdonis ok elementojn,

169
00:07:51,010 --> 00:07:53,230
8 estas evidente pli granda
ol aŭ egala al 2.

170
00:07:53,230 --> 00:07:54,980
Do kun la unua kazo ne validas.

171
00:07:54,980 --> 00:07:58,120
Do ordigi ok elementojn, mi unue
ordigi la maldekstra duono de elementoj,

172
00:07:58,120 --> 00:08:01,930
tiam mi ordigi la dekstra duono, tiam mi kunfandi
la du ordo duonoj, ĉiu de amplekso 4.

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

174
00:08:02,470 --> 00:08:07,480
>> Sed se vi ĵus rakontis al mi, ordigi la
maldekstra duono, kio estas nun de grandeco 4,

175
00:08:07,480 --> 00:08:09,350
kiel mi ordigi la maldekstra duono?

176
00:08:09,350 --> 00:08:11,430
Nu, se mi havas
enigo de kvar elementoj,

177
00:08:11,430 --> 00:08:14,590
Mi unue ordigi la maldekstra
du, tiam dekstre du,

178
00:08:14,590 --> 00:08:16,210
kaj tiam mi kunfandi ilin kune.

179
00:08:16,210 --> 00:08:18,700
Do denove, ĝi iĝas iom
de menso fleksanta ludon ĉi tie,

180
00:08:18,700 --> 00:08:21,450
ĉar vi, ia, devi
memoras kie vi estas en la rakonto,

181
00:08:21,450 --> 00:08:23,620
sed fine de la tago,
donita ajna nombro de elementoj,

182
00:08:23,620 --> 00:08:25,620
vi unue volas ordigi la
maldekstra duono, tiam la dekstra duono,

183
00:08:25,620 --> 00:08:26,661
tiam kunfandi ilin kune.

184
00:08:26,661 --> 00:08:28,630
Komencu fari ĝuste tion.

185
00:08:28,630 --> 00:08:30,170
Jen la enigo de ok elementoj.

186
00:08:30,170 --> 00:08:31,910
Nun ni rigardas la maldekstra duono tien.

187
00:08:31,910 --> 00:08:33,720
Kiel mi ordigi kvar elementoj?

188
00:08:33,720 --> 00:08:35,610
Nu mi unue ordigi la maldekstra duono.

189
00:08:35,610 --> 00:08:37,720
Nun kiel mi ordigi la maldekstra duono?

190
00:08:37,720 --> 00:08:39,419
Nu mi estis donita du elementoj.

191
00:08:39,419 --> 00:08:41,240
Do ni ordigi tiujn du elementojn.

192
00:08:41,240 --> 00:08:44,540
2 estas pli granda ol aŭ
egala al 2, kompreneble.

193
00:08:44,540 --> 00:08:46,170
Do tiu unua kazo ne validas.

194
00:08:46,170 --> 00:08:49,010
>> Do mi nun devas ordigi la maldekstra
duono de tiuj du elementoj.

195
00:08:49,010 --> 00:08:50,870
La maldekstra duono, kompreneble, estas nur 4.

196
00:08:50,870 --> 00:08:54,020
Do kiel mi ordigi liston de unu elemento?

197
00:08:54,020 --> 00:08:57,960
Nu nun, ke speciala baza kazo
supren supro, tiel diri, aplikiĝas.

198
00:08:57,960 --> 00:09:01,470
1 estas malpli ol 2, kaj mia
listo estas efektive de grandeco 1.

199
00:09:01,470 --> 00:09:02,747
Do mi simple reveni.

200
00:09:02,747 --> 00:09:03,580
Mi ne faras nenion.

201
00:09:03,580 --> 00:09:06,770
Kaj efektive, rigardu kion mi havas
farita, 4 jam ordo.

202
00:09:06,770 --> 00:09:09,220
Kiel mi jam
parte sukcesan tie.

203
00:09:09,220 --> 00:09:11,750
>> Nun ke ĝi similas specon de stultaj
aserti, sed ĝi estas vera.

204
00:09:11,750 --> 00:09:13,700
4 estas listo de amplekso 1.

205
00:09:13,700 --> 00:09:15,090
Ĝi estas jam ordo.

206
00:09:15,090 --> 00:09:16,270
Tio estas la maldekstra duono.

207
00:09:16,270 --> 00:09:18,010
Nun mi ordigi la dekstra duono.

208
00:09:18,010 --> 00:09:22,310
Mia enigo estas unu elemento, 8
simile, jam ordo.

209
00:09:22,310 --> 00:09:25,170
Stulta, tro, sed denove,
ĉi baza principo

210
00:09:25,170 --> 00:09:28,310
tuj permesos nin nun konstrui
aldone tiu sukcese.

211
00:09:28,310 --> 00:09:32,260
4 ordigataj 8 estas ordigataj nun
kio estis tiu fina paŝo?

212
00:09:32,260 --> 00:09:35,330
Do la tria kaj lasta paŝo, ajna
tempo vi ordigi liston, revokon,

213
00:09:35,330 --> 00:09:38,310
estis kunfandi la du duonoj,
maldekstre kaj dekstre.

214
00:09:38,310 --> 00:09:39,900
Do ni faru ĝuste tion.

215
00:09:39,900 --> 00:09:41,940
Mia maldekstra duono estas, kompreneble, 4.

216
00:09:41,940 --> 00:09:43,310
Mia dekstra duono estas 8.

217
00:09:43,310 --> 00:09:44,100
>> Do ni faru ĉi.

218
00:09:44,100 --> 00:09:46,410
Unue mi tuj rezervu
iu plia memoro,

219
00:09:46,410 --> 00:09:48,680
ke mi reprezentas ĉi tie,
kiel nur sekundara tabelo,

220
00:09:48,680 --> 00:09:49,660
tio sufiĉe granda por konveni tion.

221
00:09:49,660 --> 00:09:52,243
Sed vi povas imagi etendante
ke rektangulo la tuta longo

222
00:09:52,243 --> 00:09:53,290
se ni bezonas pli poste.

223
00:09:53,290 --> 00:09:58,440
Kiel mi prenos 4 kaj 8, kaj kunfandi
tiuj du listoj de grandeco 1 kune?

224
00:09:58,440 --> 00:10:00,270
Ankaŭ tie sufiĉe simpla.

225
00:10:00,270 --> 00:10:03,300
4 venas unue, tiam venas 8.

226
00:10:03,300 --> 00:10:07,130
Ĉar se mi volas ordigi la
maldekstra duono, tiam la dekstra duono,

227
00:10:07,130 --> 00:10:09,900
kaj poste kunfandi tiujn du duonoj
kune, en ordo ordo,

228
00:10:09,900 --> 00:10:11,940
4 venas unue, tiam venas 8.

229
00:10:11,940 --> 00:10:15,810
>> Do ni ŝajnas esti faranta progreson, eĉ
kvankam mi ne faris ajnan efektiva laboro.

230
00:10:15,810 --> 00:10:17,800
Sed memoru kie ni estas en la rakonto.

231
00:10:17,800 --> 00:10:19,360
Ni origine prenis ok elementoj.

232
00:10:19,360 --> 00:10:21,480
Ni ordo la maldekstra duono, kio estas 4.

233
00:10:21,480 --> 00:10:24,450
Poste ni ordo la maldekstra duono
de la maldekstra duono, 2.

234
00:10:24,450 --> 00:10:25,270
Kaj tie ni iru.

235
00:10:25,270 --> 00:10:26,920
Ni faris kun tiu paŝo.

236
00:10:26,920 --> 00:10:29,930
>> Do se ni ordo la
maldekstra duono de 2, nun ni

237
00:10:29,930 --> 00:10:32,130
devas ordigi la dekstra duono de 2.

238
00:10:32,130 --> 00:10:35,710
Do la dekstra duono de 2 estas
tiuj du valoroj tie, 6 kaj 2.

239
00:10:35,710 --> 00:10:40,620
Do ni nun prenu enigaĵoj de grandeco
2, kaj ordigi la maldekstra duono, kaj tiam

240
00:10:40,620 --> 00:10:42,610
la dekstra duono, kaj tiam
kunfandi ilin kune.

241
00:10:42,610 --> 00:10:45,722
Nu kiel mi ordigi liston de grandeco
1, enhavanta nur la numero 6?

242
00:10:45,722 --> 00:10:46,430
Mi jam faris.

243
00:10:46,430 --> 00:10:48,680
Tio listo de grandeco 1 estas ordo.

244
00:10:48,680 --> 00:10:52,140
>> Kiel mi ordigi alian liston de
grandeco 1, la tn dekstra duono.

245
00:10:52,140 --> 00:10:54,690
Nu, tro, jam ordo.

246
00:10:54,690 --> 00:10:56,190
La nombro 2 estas sola.

247
00:10:56,190 --> 00:11:00,160
Do nun mi havas du duonoj, maldekstra kaj
Bone, mi devas mem kunfandi ilin kune.

248
00:11:00,160 --> 00:11:01,800
Lasu min donu min iom da ekstra spaco.

249
00:11:01,800 --> 00:11:05,580
Kaj metis 2 en tie,
tiam 6 tien, tiel

250
00:11:05,580 --> 00:11:10,740
ordigado tiu listo, maldekstra kaj dekstra,
kaj kunfandante ĝin kune, finfine.

251
00:11:10,740 --> 00:11:12,160
Do mi estas en iomete pli bona formo.

252
00:11:12,160 --> 00:11:16,250
Mi ne faris, ĉar klare 4, 8, 2,
6 ne estas la fina ordigante ke mi volas.

253
00:11:16,250 --> 00:11:20,640
Sed mi nun havas du listojn de grandeco 2, ke
ambaux respektive solviĝis.

254
00:11:20,640 --> 00:11:24,580
Do nun se vi malantaŭenigi en via menso
okulo, kie kiuj lasas nin?

255
00:11:24,580 --> 00:11:28,520
Mi komencis kun ok elementojn, tiam mi
cxizis gxin malsupren al la maldekstra duono de 4,

256
00:11:28,520 --> 00:11:31,386
tiam la maldekstra duono de 2, kaj
tiam la dekstra duono de 2,

257
00:11:31,386 --> 00:11:34,510
Mi finis do ordigado maldekstren
duono de 2, kaj la dekstran duonon de 2,

258
00:11:34,510 --> 00:11:37,800
Do kio estas la tria kaj fina paŝo tie?

259
00:11:37,800 --> 00:11:41,290
Mi devas mem kunfandi kune
du listojn de grandeco 2.

260
00:11:41,290 --> 00:11:42,040
Do ni iru antaŭen.

261
00:11:42,040 --> 00:11:43,940
Kaj sur la ekrano tie, doni
mi iom plia memoro,

262
00:11:43,940 --> 00:11:47,170
kvankam teknike, rimarkos ke mi
atingis tutan faskon da malplenan spacon ĝis supro

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

264
00:11:47,670 --> 00:11:50,044
Se mi volas esti speciale
efika spaco saĝa,

265
00:11:50,044 --> 00:11:52,960
Mi povis nur komenci movanta la elementoj
tien kaj reen, supro kaj malsupro.

266
00:11:52,960 --> 00:11:55,460
Sed ĝuste por vida klareco,
Mi tuj metis ĝin malsupre

267
00:11:55,460 --> 00:11:56,800
teni aferojn bela kaj pura.

268
00:11:56,800 --> 00:11:58,150
>> Do mi havas du listojn de grandeco 2.

269
00:11:58,150 --> 00:11:59,770
La unua listo havas 4 kaj 8.

270
00:11:59,770 --> 00:12:01,500
La dua listo havas 2 kaj 6.

271
00:12:01,500 --> 00:12:03,950
Ni kunfandi tiujn
kune en ordo ordo.

272
00:12:03,950 --> 00:12:09,910
2, kompreneble, unue venas,
tiam 4, tiam 6, tiam 8.

273
00:12:09,910 --> 00:12:12,560
Kaj nun ni ŝajnas esti akiranta
ie interesa.

274
00:12:12,560 --> 00:12:15,720
Nun mi ordigitaj duono de la
listo, kaj hazarde, ĝi estas

275
00:12:15,720 --> 00:12:18,650
ĉiuj paraj nombroj, sed ke
estas ja nur koincido.

276
00:12:18,650 --> 00:12:22,220
Kaj mi nun ordo maldekstren
duono, tiel ke ĝi estas 2, 4, 6, kaj 8.

277
00:12:22,220 --> 00:12:23,430
Nenio estas el ordo.

278
00:12:23,430 --> 00:12:24,620
Kiu sentas same kiel progreso.

279
00:12:24,620 --> 00:12:26,650
>> Nun sentas mi havas
parolis ĉiam nun,

280
00:12:26,650 --> 00:12:29,850
do kio mankas vidi se ĉi
algoritmo estas ja pli efika.

281
00:12:29,850 --> 00:12:31,766
Sed ni tuj tra
ĝin super metode.

282
00:12:31,766 --> 00:12:34,060
Komputila kompreneble
farus tiel.

283
00:12:34,060 --> 00:12:34,840
Do kie ni estas?

284
00:12:34,840 --> 00:12:36,180
Ni komencis kun ok elementoj.

285
00:12:36,180 --> 00:12:37,840
Mi ordo la maldekstra duono de 4.

286
00:12:37,840 --> 00:12:39,290
Mi ŝajnas esti farita kun tiu.

287
00:12:39,290 --> 00:12:42,535
Do nun la sekva paŝo estas
ordigi la dekstra duono de 4.

288
00:12:42,535 --> 00:12:44,410
Kaj tiun parton ni povas iri
tra iom pli

289
00:12:44,410 --> 00:12:47,140
rapide, kvankam vi estas
bonvena malantaŭenigi aŭ paŭzo, ĵus

290
00:12:47,140 --> 00:12:49,910
pensi tra ĝi al
via propra ritmo, sed kion

291
00:12:49,910 --> 00:12:53,290
ni havas nun estas ebleco
do la ĝusta sama algoritmo sur kvar

292
00:12:53,290 --> 00:12:54,380
malsamaj nombroj.

293
00:12:54,380 --> 00:12:57,740
>> Do ni iru antaŭen kaj temigi
la dekstra duono, kiu estas tie.

294
00:12:57,740 --> 00:13:01,260
La maldekstra duono de tiu
dekstra duono, kaj nun la

295
00:13:01,260 --> 00:13:04,560
maldekstra duono de la maldekstra
duono de tiu dekstra duono,

296
00:13:04,560 --> 00:13:08,030
kaj kiel mi ordigi liston de grandeco
1 enhavanta nur la numero 1?

297
00:13:08,030 --> 00:13:09,030
Ĝi estas jam farita.

298
00:13:09,030 --> 00:13:11,830
Kiel mi fari same por listo
de grandeco 1 enhavanta nur 7?

299
00:13:11,830 --> 00:13:12,840
Ĝi estas jam farita.

300
00:13:12,840 --> 00:13:16,790
Paŝo tri por tiu duono tiam
estas kunfandi tiujn du elementojn

301
00:13:16,790 --> 00:13:20,889
en novan liston de grandeco 2, 1 kaj 7.

302
00:13:20,889 --> 00:13:23,180
Ŝajne ne faris cxion
ke multe interesa laboro.

303
00:13:23,180 --> 00:13:24,346
Ni vidu kion okazas poste.

304
00:13:24,346 --> 00:13:29,210
Mi nur ordigitaj la maldekstra duono de la
dekstra duono de mia originala enigo.

305
00:13:29,210 --> 00:13:32,360
Nun ni ordigi la dekstra
duono, kiun enhavas 5 kaj 3.

306
00:13:32,360 --> 00:13:35,740
Ni denove rigardu maldekstren
duono, ordigataj dekstra duono, ordigataj

307
00:13:35,740 --> 00:13:39,120
kaj kunfandi tiujn du kune,
en iu plia spaco,

308
00:13:39,120 --> 00:13:41,670
3 unue venas, tiam venas 5.

309
00:13:41,670 --> 00:13:46,190
Kaj tial nun, ni ordo la
maldekstra duono de la dekstra duono

310
00:13:46,190 --> 00:13:49,420
de la origina problemo, kaj
la dekstra duono de la dekstra duono

311
00:13:49,420 --> 00:13:50,800
de la originala problemo.

312
00:13:50,800 --> 00:13:52,480
Kio estas la tria kaj fina paŝo?

313
00:13:52,480 --> 00:13:54,854
Nu kunfandi tiujn du duonoj kune.

314
00:13:54,854 --> 00:13:57,020
Do lasu min atingi min iuj
ekstran spacon, sed, denove, mi

315
00:13:57,020 --> 00:13:58,699
povus esti uzante ke rezervaj spaco ĝis supro.

316
00:13:58,699 --> 00:14:00,490
Sed ni tuj daŭre
ĝin simpla vide.

317
00:14:00,490 --> 00:14:07,070
Lasu min enkunigi nun 1, kaj
tiam 3 kaj poste 5, kaj tiam 7.

318
00:14:07,070 --> 00:14:10,740
Per tio lasi min nun kun la
dekstran duonon de la originala problemo

319
00:14:10,740 --> 00:14:12,840
ke estas perfekte ordigita.

320
00:14:12,840 --> 00:14:13,662
>> Do kio restas?

321
00:14:13,662 --> 00:14:16,120
Mi sentas kiel mi tenas diranta la
samajn aferojn ree kaj ree,

322
00:14:16,120 --> 00:14:18,700
sed tio estas reflekta de la
fakto ke ni uzas rekursio.

323
00:14:18,700 --> 00:14:21,050
La procezo de uzi
algoritmo denove, kaj denove,

324
00:14:21,050 --> 00:14:23,940
sur malgrandaj subaroj de
la originala problemo.

325
00:14:23,940 --> 00:14:27,580
Do mi nun havas maldekstra ordo
duonon de la originala problemo.

326
00:14:27,580 --> 00:14:30,847
Mi rajtas ordo duone
de la originala problemo.

327
00:14:30,847 --> 00:14:32,180
Kio estas la tria kaj fina paŝo?

328
00:14:32,180 --> 00:14:33,590
Ho, ĝi estas kunfando.

329
00:14:33,590 --> 00:14:34,480
Do ni faru tion.

330
00:14:34,480 --> 00:14:36,420
Ni rezervu iun suplementan
memoro, sed mia dio, ni

331
00:14:36,420 --> 00:14:37,503
povis meti ĝin ie nun.

332
00:14:37,503 --> 00:14:40,356
Ni havas tiom da spaco disponebla
al ni, sed ni observu ĝin simpla.

333
00:14:40,356 --> 00:14:42,730
Anstataŭ iri reen kaj
eliras kun nia originala memoro,

334
00:14:42,730 --> 00:14:44,480
ni nur faros
vide malsupren tie sube,

335
00:14:44,480 --> 00:14:47,240
fini supren kunfandante la
maldekstra duono kaj la dekstra duono.

336
00:14:47,240 --> 00:14:49,279
>> Do kunfandante, kion mi devas fari?

337
00:14:49,279 --> 00:14:50,820
Mi deziras preni la elementojn en ordo.

338
00:14:50,820 --> 00:14:53,230
Do rigardante la maldekstra duono,
Mi vidas la unua nombro estas 2.

339
00:14:53,230 --> 00:14:55,230
Mi rigardas la dekstran duonon,
Mi vidas la unuan numeron

340
00:14:55,230 --> 00:14:58,290
estas 1, tiel evidente kion
numeron mi volas elŝiri,

341
00:14:58,290 --> 00:15:00,430
kaj metis unua en mia lerta fino?

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

343
00:15:01,449 --> 00:15:02,990
Nun mi volas demandi tion saman demandon.

344
00:15:02,990 --> 00:15:05,040
Sur la maldekstra duono, mi havas
ankoraŭ havas la numeron 2.

345
00:15:05,040 --> 00:15:07,490
Sur la dekstran duonon,
Mi havas la numeron 3.

346
00:15:07,490 --> 00:15:08,930
Kiun mi volas elekti?

347
00:15:08,930 --> 00:15:11,760
Kompreneble, numero 2 Kaj
nun rimarkas la kandidatoj

348
00:15:11,760 --> 00:15:13,620
Estas 4 maldekstre, 3 dekstre.

349
00:15:13,620 --> 00:15:15,020
Ni, kompreneble, elektu 3.

350
00:15:15,020 --> 00:15:18,020
Nun la kandidatoj estas 4 sur
la maldekstra, 5 dekstre.

351
00:15:18,020 --> 00:15:19,460
Ni, kompreneble, elektu 4.

352
00:15:19,460 --> 00:15:21,240
6 sur la maldekstra, 5 dekstre.

353
00:15:21,240 --> 00:15:22,730
Ni, kompreneble, elektu 5.

354
00:15:22,730 --> 00:15:25,020
6 maldekstre 7 dekstre.

355
00:15:25,020 --> 00:15:29,320
Ni elektas 6, kaj tiam ni
elekti 7, kaj tiam ni elektus 8.

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

357
00:15:30,100 --> 00:15:34,370
>> Do multegajn vortojn poste, ni
esti ordigitaj tiun liston de ok elementoj

358
00:15:34,370 --> 00:15:38,450
en listo de unu tra ok,
ke estas kreskanta kun ĉiu paŝo,

359
00:15:38,450 --> 00:15:40,850
sed kiom da tempo faris
ni bezonos por fari tion.

360
00:15:40,850 --> 00:15:43,190
Nu mi havas intence
Laid aferojn bilde

361
00:15:43,190 --> 00:15:46,330
tie, por ke ni povas ia
vidi aŭ aprezi la divido

362
00:15:46,330 --> 00:15:49,060
en konkeradon ke tio estis okazanta.

363
00:15:49,060 --> 00:15:52,830
>> Ja se vi retrorigardas al la maldormo,
Mi lasis ĉiujn tiujn punktita linioj

364
00:15:52,830 --> 00:15:55,660
en lokokupilojn, vi povas,
ia, vidu, en inversa ordo,

365
00:15:55,660 --> 00:15:58,800
se ia retrorigardas en
historio nun, mia originala listo

366
00:15:58,800 --> 00:16:00,250
estas, kompreneble, de grandeco 8.

367
00:16:00,250 --> 00:16:03,480
Kaj tiam antaŭe, mi estis
kontraktanta kun du listojn de grandeco 4,

368
00:16:03,480 --> 00:16:08,400
kaj tiam kvar listoj de amplekso 2,
kaj tiam ok listojn de grandeco 1.

369
00:16:08,400 --> 00:16:10,151
>> Do kio faras tiun,
ia, memorigas vin pri?

370
00:16:10,151 --> 00:16:11,858
Nu, ja, iu el
la algoritmoj ni havas

371
00:16:11,858 --> 00:16:14,430
rigardis ĝis nun, kie ni
breĉo, kaj dividiĝas, kaj dividiĝas,

372
00:16:14,430 --> 00:16:19,500
teni havanta aferojn denove, kaj
denove, rezultigas ĉi ĝenerala ideo.

373
00:16:19,500 --> 00:16:23,100
Kaj do estas io
logaritma okazas ĉi tie.

374
00:16:23,100 --> 00:16:26,790
Kaj ĝi ne estas sufiĉe log de n, sed
Tie estas logaritma komponanto

375
00:16:26,790 --> 00:16:28,280
al kion ni ĵus faris.

376
00:16:28,280 --> 00:16:31,570
>> Nun ni konsideru ke fakte estas.

377
00:16:31,570 --> 00:16:34,481
Do log de n, denove estis
grandan rultempo,

378
00:16:34,481 --> 00:16:36,980
kiam ni faris ion kiel
duuma serĉo, kiel ni nun nomas ĝin,

379
00:16:36,980 --> 00:16:40,090
la dividu kaj regu strategion
tra kiu ni trovis Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Nun teknike.

381
00:16:41,020 --> 00:16:43,640
Jen protokolo bazo 2 de n, eĉ
kvankam en plej math klasoj,

382
00:16:43,640 --> 00:16:45,770
10 estas kutime la bazo ke vi supozas.

383
00:16:45,770 --> 00:16:48,940
Sed komputikistoj preskaŭ ĉiam
pensi kaj paroli en terminoj de bazo 2,

384
00:16:48,940 --> 00:16:52,569
do ni ĝenerale nur diru loglibro de
n, anstataŭ log bazo 2 de n,

385
00:16:52,569 --> 00:16:55,110
sed ili estas ĝuste unu kaj la
sama en la mondo de komputilo

386
00:16:55,110 --> 00:16:57,234
scienco, kaj kiel flanken,
Tie estas konstanta faktoro

387
00:16:57,234 --> 00:17:01,070
diferenco inter la du, do estas
Moot ĉiuokaze, por pli formalaj motivoj.

388
00:17:01,070 --> 00:17:04,520
>> Sed nuntempe, kion ni zorgas
pri estas ĉi ekzemplo.

389
00:17:04,520 --> 00:17:08,520
Do ni ne pruvi per ekzemplo, sed ĉe
almenaŭ uzi ekzemplon de la nombroj

390
00:17:08,520 --> 00:17:10,730
ĉe mano kiel prudento ĉeko, se vi volas.

391
00:17:10,730 --> 00:17:14,510
Do antaŭe la formulo estis log bazo
2 de n, sed kion estas n tiukaze.

392
00:17:14,510 --> 00:17:18,526
Mi devis n originalaj nombroj, aŭ 8
de originala numero specife.

393
00:17:18,526 --> 00:17:20,359
Nun jam pasis iom
dum, sed mi estas sufiĉe

394
00:17:20,359 --> 00:17:25,300
certas ke log bazo 2
de la valoro 8 estas 3,

395
00:17:25,300 --> 00:17:29,630
kaj ja, kio estas agrabla pri tio estas
ke 3 estas ĝuste la nombro de tempoj

396
00:17:29,630 --> 00:17:33,320
ke vi povas dividi listo
de longo 8 denove, kaj denove,

397
00:17:33,320 --> 00:17:36,160
kaj denove, ĝis vi lasis
kun listoj de ĵus grandecon 1.

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

399
00:17:36,660 --> 00:17:40,790
8 iras al 4, iras al 2,
iras al 1, kaj tio estas

400
00:17:40,790 --> 00:17:43,470
reflekta ĝuste tiun
bildo ni devis nur antaŭ momento.

401
00:17:43,470 --> 00:17:47,160
Do iom prudento kontroli kiel al kie
la logaritmo estas fakte implikita.

402
00:17:47,160 --> 00:17:50,180
>> Do nun, kion alia estas implikita tie? n.

403
00:17:50,180 --> 00:17:53,440
Do rimarki ke ĉiu
fojon mi fendi la listo,

404
00:17:53,440 --> 00:17:58,260
kvankam en inversa ordo en historio
tie, mi estis ankoraŭ faranta n aferoj.

405
00:17:58,260 --> 00:18:02,320
Ke kunfando paŝo postulis ke
Mi tuŝas ĉiun el la nombroj,

406
00:18:02,320 --> 00:18:05,060
por gliti ĝin
lia taŭga loko.

407
00:18:05,060 --> 00:18:10,760
Do kvankam la alteco de tiu
diagramo estas de grandeco log n de n aŭ 3,

408
00:18:10,760 --> 00:18:13,860
specife, en aliaj vortoj,
Mi faris tri dividoj tie.

409
00:18:13,860 --> 00:18:18,800
Kiom laboro mi faris horizontale
laŭ tiu diagramo ĉiu tempo?

410
00:18:18,800 --> 00:18:21,110
>> Nu, mi faris n paŝoj de
labori, ĉar se mi havas

411
00:18:21,110 --> 00:18:24,080
ricevis kvar elementoj kaj kvar elementoj,
kaj mi bezonas kunfandi ilin kune.

412
00:18:24,080 --> 00:18:26,040
Mi bezonas iri tra
tiuj kvar kaj tiuj kvar,

413
00:18:26,040 --> 00:18:28,123
finfine kunfandi ilin
reen en ok elementoj.

414
00:18:28,123 --> 00:18:32,182
Se inverse Mi havas ok fingrojn
super tie, kiun mi ne, kaj ok

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- Se mi havas
ricevis kvar fingroj super tie,

416
00:18:34,390 --> 00:18:37,380
kiun mi faros, kvar fingroj
super tie, kiujn mi faras;

417
00:18:37,380 --> 00:18:40,590
tiam tio estas la sama
Ekzemple kiel antaŭe, se mi faras

418
00:18:40,590 --> 00:18:44,010
havas ok fingrojn kvazaŭ en
Entute kiun mi povas, ia, faru.

419
00:18:44,010 --> 00:18:47,950
Mi povas ekzakte fari tie,
tiam mi certe povas

420
00:18:47,950 --> 00:18:50,370
kunfandi ĉiuj tiuj listoj
de grandeco 1 kune.

421
00:18:50,370 --> 00:18:54,050
Sed mi certe devas rigardi
ĉe ĉiu elemento ekzakte unufoje.

422
00:18:54,050 --> 00:18:59,640
Do la alteco de ĉi tiu procezo estas log n,
la larĝo de tiu procezo, tiel diri,

423
00:18:59,640 --> 00:19:02,490
estas n, do kion ni ŝajnas
havi, finfine, estas

424
00:19:02,490 --> 00:19:06,470
kura tempo de amplekso n fojoj logo n.

425
00:19:06,470 --> 00:19:08,977
>> En aliaj vortoj, ni dividis
la listo, log n fojojn,

426
00:19:08,977 --> 00:19:11,810
sed ĉiun fojon ni faris tion, ni havis
tuŝi ĉiun de la elementoj

427
00:19:11,810 --> 00:19:13,560
por kunfandi ilin
ĉiuj kune, kiuj

428
00:19:13,560 --> 00:19:18,120
estis n paŝo, tial ni havas n fojoj logo n,
aŭ por komputila sciencisto dirus,

429
00:19:18,120 --> 00:19:20,380
asimptote, kiu
estus la granda vorto

430
00:19:20,380 --> 00:19:22,810
priskribi la supra
ligis sur rultempo,

431
00:19:22,810 --> 00:19:28,010
ni kuras en granda O
de log n tempo, por tiel diri.

432
00:19:28,010 --> 00:19:31,510
>> Nun tiu estas signifa, ĉar
memori kio la kuranta tempoj estis

433
00:19:31,510 --> 00:19:34,120
kun bobelo varo, kaj selektado
speco, kaj inserción varo,

434
00:19:34,120 --> 00:19:38,200
kaj eĉ kelkaj aliaj ke ekzistas,
n kvadratoj estis kie ni estis ĉe.

435
00:19:38,200 --> 00:19:39,990
Kaj vi povas, ia, vidu ĉi tie.

436
00:19:39,990 --> 00:19:45,720
Se n kvadratoj estas evidente n fojoj
n, sed ĉi tie ni havas n fojoj logo n,

437
00:19:45,720 --> 00:19:48,770
kaj ni jam scias el semajno
nulo, ke log n, la logaritma,

438
00:19:48,770 --> 00:19:50,550
estas pli bona ol io lineara.

439
00:19:50,550 --> 00:19:52,930
Post ĉiu, memoru la bildon
kun la ruĝa kaj la flava

440
00:19:52,930 --> 00:19:56,500
kaj la verda linioj kiuj ni tiris, la
verda logaritma linio estis multe pli malalta.

441
00:19:56,500 --> 00:20:00,920
Kaj sekve, multe pli bona kaj pli rapida
ol la rektan flavan kaj ruĝan linioj,

442
00:20:00,920 --> 00:20:05,900
n fojoj logo n, vere, bonaj
ol n × n, aŭ n kvadratoj.

443
00:20:05,900 --> 00:20:09,110
>> Do ni ŝajnas havi
identigitaj algoritmo merge

444
00:20:09,110 --> 00:20:11,870
speco kiu kuras en multe
rapida tempo, kaj efektive,

445
00:20:11,870 --> 00:20:16,560
jen kial, komence de ĉi tiu semajno, kiam
ni vidis, ke konkurso inter bobelo

446
00:20:16,560 --> 00:20:20,750
varon, selektado speco, kaj kunfandi
varon, merge varo vere, vere gajnis.

447
00:20:20,750 --> 00:20:23,660
Kaj efektive, ni eĉ ne atendu
por bobelo varo kaj selektado speco

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

449
00:20:24,790 --> 00:20:27,410
>> Nun ni prenu unu alia enirpermesilo
pro tio, de iomete pli

450
00:20:27,410 --> 00:20:31,030
formala perspektivo, nur en
kazo, ĉi resonas bone

451
00:20:31,030 --> 00:20:33,380
ol tiu alta nivelo diskuto.

452
00:20:33,380 --> 00:20:34,880
Do jen la algoritmon denove.

453
00:20:34,880 --> 00:20:36,770
Ni demandas nin,
kion la rultempo

454
00:20:36,770 --> 00:20:39,287
estas de ĉi algoritmoj, algoritmas diversaj paŝoj?

455
00:20:39,287 --> 00:20:41,620
Ni dividu ĝin en la unua
kazo kaj la dua kazo.

456
00:20:41,620 --> 00:20:46,280
La IF kaj la alia en la IF kazo,
Se n estas malpli ol 2, simple reveni.

457
00:20:46,280 --> 00:20:47,580
Sentas kiel konstanta tempo.

458
00:20:47,580 --> 00:20:50,970
Estas, ia, kiel du ŝtupoj,
Se n estas malpli ol 2, tiam revenu.

459
00:20:50,970 --> 00:20:54,580
Sed kiel ni diris lundon,
konstanta tempo, aŭ granda o de 1,

460
00:20:54,580 --> 00:20:57,130
eblas du paŝojn, tri
ŝtupoj, eĉ 1.000 ŝtupoj.

461
00:20:57,130 --> 00:20:59,870
Kio gravas estas ke ĝi estas
konstanta nombro de paŝoj.

462
00:20:59,870 --> 00:21:03,240
Do la flava elstarigita _pseudocode_
tie kuras en, ni nomas ĝin,

463
00:21:03,240 --> 00:21:04,490
konstanta tempo.

464
00:21:04,490 --> 00:21:06,780
Do pli formale, kaj
Ni tuj to-- ĉi

465
00:21:06,780 --> 00:21:09,910
estos la amplekso al kiu ni
formaligi tiun rajton now-- T de n,

466
00:21:09,910 --> 00:21:15,030
la rula tempo de problemo
ke prenas n somethings kiel enigo,

467
00:21:15,030 --> 00:21:19,150
egalas big o de unu,
Se n estas malpli ol 2.

468
00:21:19,150 --> 00:21:20,640
Do estas kondiĉa sur tio.

469
00:21:20,640 --> 00:21:24,150
Do esti klara, se n estas malpli ol
2, ni havas tre mallongajn listo, tiam

470
00:21:24,150 --> 00:21:29,151
la rula tempo, T de n, kie n estas
1 aŭ 0, en tiu tre specifa kazo,

471
00:21:29,151 --> 00:21:30,650
ĝi estas nur tuj estos konstanta tempo.

472
00:21:30,650 --> 00:21:32,691
Ĝi tuj prenu unu
paŝi, du paŝojn, ajn.

473
00:21:32,691 --> 00:21:33,950
Ĝi estas fiksita nombro de paŝoj.

474
00:21:33,950 --> 00:21:38,840
>> Do la suka parto nepre esti en
la alia kazo en la _pseudocode_.

475
00:21:38,840 --> 00:21:40,220
La alian kazon.

476
00:21:40,220 --> 00:21:44,870
Ordigi maldekstra duono de elementoj, ia dekstra
duono de elementoj, kunfandi ordo duonoj.

477
00:21:44,870 --> 00:21:46,800
Kiom longe faras ĉiu el tiuj ŝtupoj sekvu?

478
00:21:46,800 --> 00:21:49,780
Nu, se la kurado
tempo ordigi n elementoj

479
00:21:49,780 --> 00:21:53,010
estas, ni nomas ĝin tre
genéricamente, T de n,

480
00:21:53,010 --> 00:21:55,500
tiam ordigado maldekstren
duono de la elementoj

481
00:21:55,500 --> 00:21:59,720
Estas, ia, kiel diri,
T n dividita per 2,

482
00:21:59,720 --> 00:22:03,000
kaj simile ordigado la dekstra duono
de elementoj estas, speco de, kiel diri,

483
00:22:03,000 --> 00:22:06,974
T n dividita 2, kaj tiam
kunfandante la ordo duonoj.

484
00:22:06,974 --> 00:22:08,890
Nu, se mi havas iun
nombro de elementoj tie,

485
00:22:08,890 --> 00:22:11,230
kiel kvar, kaj iuj nombro
de elementoj tie, kiel kvar,

486
00:22:11,230 --> 00:22:14,650
kaj mi devas mem kunfandi ĉiu de tiuj kvar
en, kaj ĉiu el tiuj kvar en unu

487
00:22:14,650 --> 00:22:17,160
post la alia, tiel ke
finfine mi havas ok elementojn.

488
00:22:17,160 --> 00:22:20,230
Ĝi sentas ke estas granda O de n paŝoj?

489
00:22:20,230 --> 00:22:23,500
Se mi havas n fingroj kaj ĉiu el
ili devas esti kunfandita en loko,

490
00:22:23,500 --> 00:22:25,270
tio estas kiel alia n paŝoj.

491
00:22:25,270 --> 00:22:27,360
>> Do ja formulaically,
ni povas esprimi tiun,

492
00:22:27,360 --> 00:22:29,960
kvankam iom scarily unue
rigardo, sed estas io

493
00:22:29,960 --> 00:22:31,600
kiu kaptas ĝuste tiu logiko.

494
00:22:31,600 --> 00:22:35,710
La rultempo, T n, se n
estas pli granda ol aŭ egala al 2.

495
00:22:35,710 --> 00:22:42,500
En tiu kazo, la alian kazon, estas T de n
dividita per 2, plus T de n dividita per 2,

496
00:22:42,500 --> 00:22:45,320
plus granda O de n, iuj
lineara nombro de paŝoj,

497
00:22:45,320 --> 00:22:51,630
eble ĝuste n, eble 2 fojoj
n, sed estas krude, ordo de n.

498
00:22:51,630 --> 00:22:54,060
Tiel ke ankaŭ estas kiel ni povas
esprimi tiun formulaically.

499
00:22:54,060 --> 00:22:56,809
Nun vi ne scias tion, se
vi jam registris ĝin en vian menson,

500
00:22:56,809 --> 00:22:58,710
aŭ rigardi gxin en la
dorso de lernolibro, ke

501
00:22:58,710 --> 00:23:00,501
havu iom
cheat folio fine,

502
00:23:00,501 --> 00:23:03,940
sed tio ja tuj
donu al ni grandan o de n logo n,

503
00:23:03,940 --> 00:23:06,620
ĉar la rekursieca ke
vi vidas tie en la ekrano,

504
00:23:06,620 --> 00:23:09,550
se vi vere faris ĝin, kun
senfinan nombron de ekzemploj,

505
00:23:09,550 --> 00:23:13,000
aŭ vi faris formulaically, vi farus
vidi ke tiu, ĉar tiu formulo

506
00:23:13,000 --> 00:23:17,100
sin estas rekursie, kun t de
n super io dekstre

507
00:23:17,100 --> 00:23:21,680
kaj t de n super maldekstre, tiu povas
reale esti esprimita, finfine,

508
00:23:21,680 --> 00:23:24,339
tiel granda go de n logo n.

509
00:23:24,339 --> 00:23:26,130
Se ne konvinkis, ke estas
fajna por nun, nur

510
00:23:26,130 --> 00:23:28,960
preni sur fido, ke tio estas ja
kion tio ripetiĝo kondukas al,

511
00:23:28,960 --> 00:23:31,780
sed tiu estas nur iom pli de
matematika alproksimiĝo al rigardanta

512
00:23:31,780 --> 00:23:36,520
ĉe la rula tempo de merge varo
bazita sur lia _pseudocode_ sola.

513
00:23:36,520 --> 00:23:39,030
>> Nu, ni prenu iom de
elspiras el ĉiuj de tiu,

514
00:23:39,030 --> 00:23:41,710
kaj rigardu la
certaj iamaj senatano, kiu

515
00:23:41,710 --> 00:23:44,260
povus rigardi iomete familiara,
kiuj sidis kun Google Eric

516
00:23:44,260 --> 00:23:48,410
Schmidt, antaŭ kelka tempo, por intervjuo
sur scenejo, antaŭ tuta amaso

517
00:23:48,410 --> 00:23:53,710
de homoj, parolantaj finfine pri
temo, jen vere nun konata.

518
00:23:53,710 --> 00:23:54,575
Ni rigardu.

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

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt: Nun Senatano,
vi estas tie ĉe Google,

521
00:24:03,890 --> 00:24:09,490
kaj mi ŝatas pensi pri la
prezidanteco kiel dungointervjuo.

522
00:24:09,490 --> 00:24:11,712
Nun estas malfacile akiri taskon kiel prezidento.

523
00:24:11,712 --> 00:24:12,670
PREZIDANTO OBAMA: Dekstra.

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt: Kaj vi estas
tuj fari [inaudible] nun.

525
00:24:13,940 --> 00:24:15,523
Ĝi estas ankaŭ malfacile akiri laboron ĉe Google.

526
00:24:15,523 --> 00:24:17,700
PREZIDANTO OBAMA: Dekstra.

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt: Ni havas demandojn,
kaj ni petas niajn kandidatojn demandoj,

528
00:24:21,330 --> 00:24:24,310
kaj ĉi tiu estas de Larry Schwimmer.

529
00:24:24,310 --> 00:24:25,890
>> PREZIDANTO OBAMA: OK.

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

531
00:24:27,005 --> 00:24:28,130
Vi uloj pensas mi kidding?

532
00:24:28,130 --> 00:24:30,590
Ĝi estas ĝuste ĉi tie.

533
00:24:30,590 --> 00:24:33,490
Kio estas la plej efika vojo
ordigi miliono 32 bita entjeroj?

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

535
00:24:37,560 --> 00:24:38,979
>> PREZIDANTO OBAMA: Well--

536
00:24:38,979 --> 00:24:41,020
Eric Schmidt: Kelkfoje,
eble mi bedaŭras, maybe--

537
00:24:41,020 --> 00:24:42,750
PREZIDANTO OBAMA: Ne, ne,
ne, ne, ne, mi think--

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt: Tio ne it--

539
00:24:43,240 --> 00:24:45,430
PREZIDANTO OBAMA: Mi
pensas, mi kredas ke la bobelo

540
00:24:45,430 --> 00:24:46,875
speco estus la malĝusta vojo iri.

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

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

543
00:24:50,535 --> 00:24:52,200
Kiu diris lin tio?

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

545
00:24:54,020 --> 00:24:55,590
Mi ne forgesis la komputiko on--

546
00:24:55,590 --> 00:24:58,986
>> PREZIDANTO OBAMA: Ni jam
havas nian spionoj en tie.

547
00:24:58,986 --> 00:24:59,860
PROFESORO: Bone.

548
00:24:59,860 --> 00:25:03,370
Ni lasas malantaŭ ni nun la
teoria mondo de algoritmoj

549
00:25:03,370 --> 00:25:06,520
en la asimptota analitiko
el gxi kaj reveni al iuj temoj

550
00:25:06,520 --> 00:25:09,940
el semajno nulo kaj unu, kaj komenco
forigi iuj trejnado radoj,

551
00:25:09,940 --> 00:25:10,450
se vi volas.

552
00:25:10,450 --> 00:25:13,241
Por ke vi vere komprenas
finfine de la tero supren, kio estas

553
00:25:13,241 --> 00:25:16,805
daŭriganta sub la kapuĉo, kiam vi
skribi, kompili kaj ekzekuti programojn.

554
00:25:16,805 --> 00:25:19,680
Memori precipe, ke tio
la unua C programon ni rigardis,

555
00:25:19,680 --> 00:25:22,840
kanona, simpla programo
de varoj, relative parolante,

556
00:25:22,840 --> 00:25:24,620
kien, ĝi presas, Saluton Mondo.

557
00:25:24,620 --> 00:25:27,610
Kaj memoru, ke mi diris, la procezo
ke fontkodon iras tra

558
00:25:27,610 --> 00:25:28,430
Estas ĝuste tiu.

559
00:25:28,430 --> 00:25:31,180
Vi prenas vian fontkodon, transiru
ĝin tra kompililo, kiel Clang,

560
00:25:31,180 --> 00:25:34,650
kaj eksteren venas celkodo, ke
povus aspekti kiel ĉi, nuloj kaj

561
00:25:34,650 --> 00:25:37,880
ke la komputilo CPU, centra
prilaborado unuo aŭ cerbo,

562
00:25:37,880 --> 00:25:39,760
finfine komprenas.

563
00:25:39,760 --> 00:25:42,460
>> Ĝi turnas ke tio estas
Iom de simplificación,

564
00:25:42,460 --> 00:25:44,480
ke ni estas nun en
pozicio por inciteti dise

565
00:25:44,480 --> 00:25:46,720
kompreni kio vere estis
daŭriganta sub la kapuĉo

566
00:25:46,720 --> 00:25:48,600
ĉiufoje kiam vi kuros
Tin, aŭ pli ĝenerale,

567
00:25:48,600 --> 00:25:53,040
ĉiu tempo vi faras programon,
uzante Faru kaj CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
En aparta, aĵoj kiel
ĉi estas unua generita,

569
00:25:56,760 --> 00:25:58,684
kiam vi unue kompili vian programon.

570
00:25:58,684 --> 00:26:00,600
Alivorte, kiam vi
prenu vian fontkodon

571
00:26:00,600 --> 00:26:04,390
kaj kompili ĝin, kio estas unua
estanta outputted per Clang

572
00:26:04,390 --> 00:26:06,370
Estas io konata kiel asembleo kodo.

573
00:26:06,370 --> 00:26:08,990
Kaj fakte, ĝi aspektas precize kiel tiu.

574
00:26:08,990 --> 00:26:11,170
>> Mi kuris komando ĉe la
komandlinio antaŭe.

575
00:26:11,170 --> 00:26:16,260
Tin haltostreko ĉefurbo s hello.c,
kaj tio kreis dosieron

576
00:26:16,260 --> 00:26:19,490
por mi vokis hello.s,
interne de kiu estis ĝuste

577
00:26:19,490 --> 00:26:22,290
tiuj enhavoj, kaj iom pli
supre kaj iom pli sube,

578
00:26:22,290 --> 00:26:25,080
sed mi metis la plej sukaj
informojn tie sur la ekrano.

579
00:26:25,080 --> 00:26:29,190
Kaj se vi rigardas atente, vi vidos
almenaŭ kelkajn familiara ŝlosilvortoj.

580
00:26:29,190 --> 00:26:31,330
Ni havas ĉefan ĉe supro.

581
00:26:31,330 --> 00:26:35,140
Ni printf malsupren en la mezo.

582
00:26:35,140 --> 00:26:38,670
Kaj ni ankaŭ havas saluton mondo
backslash n inter citiloj sube.

583
00:26:38,670 --> 00:26:42,450
>> Kaj ĉio en ĉi
estas tre malalta nivelo instrukcioj

584
00:26:42,450 --> 00:26:45,500
ke la komputilo CPU komprenas.

585
00:26:45,500 --> 00:26:50,090
CPU instrukcioj kiuj movas memoro
ĉirkaŭ, ke ŝarĝo kordoj de memoro,

586
00:26:50,090 --> 00:26:52,750
kaj finfine, presaĵo
aferoj sur la ekrano.

587
00:26:52,750 --> 00:26:56,780
Nun kio okazas post kiam
tiu asembleo kodo estas generita?

588
00:26:56,780 --> 00:26:59,964
Finfine, vi ja
ankoraŭ generi celkodo.

589
00:26:59,964 --> 00:27:02,630
Sed la paŝoj kiuj havas vere
daŭras sub la kapuĉo

590
00:27:02,630 --> 00:27:04,180
rigardi iom pli kiel tiu.

591
00:27:04,180 --> 00:27:08,390
Fontkodon iĝas asembleo kodo,
kiu fariĝas objekto kodo,

592
00:27:08,390 --> 00:27:11,930
kaj la operativa vortoj tie estas ke,
kiam vi kompili vian fontkodon,

593
00:27:11,930 --> 00:27:16,300
eksteren venas asembleo kodo, kaj poste
kiam vi kolektos viajn asembleo kodo,

594
00:27:16,300 --> 00:27:17,800
eksteren venas celkodo.

595
00:27:17,800 --> 00:27:20,360
>> Nun Clang estas súper kompleksaj,
kiel multaj kompililoj,

596
00:27:20,360 --> 00:27:23,151
kaj ĝi faras ĉiu el tiuj ŝtupoj
kune, kaj tio ne nepre

597
00:27:23,151 --> 00:27:25,360
eligo ajna intera
dosieroj kiujn vi povas eĉ vidi.

598
00:27:25,360 --> 00:27:28,400
Ĝi ĵus kompilas aferojn,
kiu estas la ĝenerala termino kiu

599
00:27:28,400 --> 00:27:30,000
Priskribas ĉi tuta procezo.

600
00:27:30,000 --> 00:27:32,000
Sed se vi vere volas
esti aparta, ekzistas

601
00:27:32,000 --> 00:27:34,330
multe pli okazas tie ankaŭ.

602
00:27:34,330 --> 00:27:38,860
>> Sed ni ankaŭ konsideras nun ke eĉ
ke super simpla programo, hello.c,

603
00:27:38,860 --> 00:27:40,540
nomita funkcio.

604
00:27:40,540 --> 00:27:41,870
Ĝi vokis printf.

605
00:27:41,870 --> 00:27:46,900
Sed mi ne skribis printf ja
kiu venas kun C, tiel diri.

606
00:27:46,900 --> 00:27:51,139
Estas funkcio revokon tio
deklaris en norma io.h, kiu

607
00:27:51,139 --> 00:27:53,180
Estas kaplinio dosiero, kiu
estas temo ni vere

608
00:27:53,180 --> 00:27:55,780
plonĝi en pli profundo antaŭ longe.

609
00:27:55,780 --> 00:27:58,000
Sed header dosiero
tipe akompanitaj

610
00:27:58,000 --> 00:28:02,920
per kodo dosiero, fontkodo dosiero, do
multe kiel tie ekzistas normo io.h.

611
00:28:02,920 --> 00:28:05,930
>> Iam antaŭe, iu,
aŭ ies, ankaŭ skribis

612
00:28:05,930 --> 00:28:11,040
dosiero nomata norma io.c, en
kiu la efektiva difinoj,

613
00:28:11,040 --> 00:28:15,220
aŭ implementaciones de printf,
kaj gxibo de aliaj funkcioj,

614
00:28:15,220 --> 00:28:16,870
estas efektive skribita.

615
00:28:16,870 --> 00:28:22,140
Do donita ke, se ni konsideras havi
tie sur la maldekstra, hello.c, ke kiam

616
00:28:22,140 --> 00:28:26,250
kompilis, donas ni hello.s, eĉ se
Tin ne tedas ŝparado en loko

617
00:28:26,250 --> 00:28:31,360
ni povas vidi ĝin, kaj tiu asembleo kodo
gets kolektiĝis en hello.o, kiu

618
00:28:31,360 --> 00:28:34,630
Estas ja la defaŭltan nomon
donita whenever vi kompili fonto

619
00:28:34,630 --> 00:28:39,350
kodigi en celkodo, sed ne
tute preta ekzekuti ĝin,

620
00:28:39,350 --> 00:28:41,460
ĉar alia paŝo
devas okazi, kaj havas

621
00:28:41,460 --> 00:28:44,440
estis pasante por la lastaj
semajnojn, eble nekonata al vi.

622
00:28:44,440 --> 00:28:47,290
>> Specife ie
en CS50 IDE, kaj tiu,

623
00:28:47,290 --> 00:28:49,870
Ankaŭ estos iom de
simplificación momente,

624
00:28:49,870 --> 00:28:54,670
ekzistas, aŭ estis antaŭ longa tempo,
dosiero nomata norma io.c,

625
00:28:54,670 --> 00:28:58,440
ke iu kompilita en
norma io.s aŭ la ekvivalento,

626
00:28:58,440 --> 00:29:02,010
ke iu tiam kunvenigis
en norma io.o,

627
00:29:02,010 --> 00:29:04,600
aŭ ĝi rezultas enen
iomete malsama dosiero

628
00:29:04,600 --> 00:29:07,220
formato kiu povas havi malsamajn
dosiersufikso entute,

629
00:29:07,220 --> 00:29:11,720
sed teorie kaj koncepte, ĝuste
tiuj ŝtupoj devis okazi en iu formo.

630
00:29:11,720 --> 00:29:14,060
Kiu estas diri, ke nun
kiam mi estas skribanta programon,

631
00:29:14,060 --> 00:29:17,870
hello.c, ke nur diras, saluton mondo,
kaj Mi uzas aliulaj kodo

632
00:29:17,870 --> 00:29:22,480
kiel printf, kiu iam estis sur
tempo, en dosiero nomata norma io.c,

633
00:29:22,480 --> 00:29:26,390
tiam iel mi devas preni miajn
celkodo, mia nuloj kaj,

634
00:29:26,390 --> 00:29:29,260
kaj tiu persono objekto
kodo, aŭ nuloj kaj,

635
00:29:29,260 --> 00:29:34,970
kaj iel ligi ilin kune en
unu fina dosiero, nomata saluton, ke

636
00:29:34,970 --> 00:29:38,070
havas ĉiujn la nuloj kaj
ones de mia ĉefa funkcio,

637
00:29:38,070 --> 00:29:40,830
kaj ĉiuj la nuloj
kaj aĵoj por printf.

638
00:29:40,830 --> 00:29:44,900
>> Kaj ja, ke lasta procezo estas
nomita, kunligi vian celkodo.

639
00:29:44,900 --> 00:29:47,490
La eligo de kiu
estas plenumebla dosiero.

640
00:29:47,490 --> 00:29:49,780
Do juste la
fino de la tago, nenio

641
00:29:49,780 --> 00:29:52,660
ŝanĝiĝis ekde semajno unu, kiam ni
unue komencis kompili programojn.

642
00:29:52,660 --> 00:29:55,200
Efektive, ĉio ĉi estis
okazas sub la kapuĉo,

643
00:29:55,200 --> 00:29:57,241
sed nun ni estas en pozicio
Kie ni povas reale

644
00:29:57,241 --> 00:29:58,794
turmentus aparte tiujn diversajn ŝtupojn.

645
00:29:58,794 --> 00:30:00,710
Kaj efektive, fine
de la tago, ni ankoraŭ

646
00:30:00,710 --> 00:30:04,480
lasis kun nuloj kaj, kio
Estas efektive granda segue nun

647
00:30:04,480 --> 00:30:08,620
al alia kapablo de C, kiu
ni ne devis utiligi plej verŝajna

648
00:30:08,620 --> 00:30:11,250
ĝis nun, konata kiel bitlarĝa operatoroj.

649
00:30:11,250 --> 00:30:15,220
En aliaj vortoj, tiel malproksime, anytime ni havas
pritraktis datumoj en C aŭ variabloj en C,

650
00:30:15,220 --> 00:30:17,660
ni havis aĵojn kiel
signoj kaj floto kaj ins

651
00:30:17,660 --> 00:30:21,990
kaj sopiras kaj duobloj kaj similaj, sed
ĉiuj el tiuj estas almenaŭ ok bitoj.

652
00:30:21,990 --> 00:30:25,550
Ni neniam ankoraŭ povis
manipuli individuaj bitoj,

653
00:30:25,550 --> 00:30:28,970
kvankam individuo bito, ni
Know, povas reprezenti 0 kaj 1.

654
00:30:28,970 --> 00:30:32,640
Nun ĝi rezultas ke en C, oni
povas akiri aliron al individua bitoj,

655
00:30:32,640 --> 00:30:35,530
se vi scias la sintakson,
kun kiu akiri ilin.

656
00:30:35,530 --> 00:30:38,010
>> Do ni rigardu
ĉe bitlarĝa operatoroj.

657
00:30:38,010 --> 00:30:41,700
Do bildigis ĉi tie estas kelkaj simboloj kiuj
ni, speco de, ia, vidis antaŭe.

658
00:30:41,700 --> 00:30:45,580
Mi vidas simbolo, vertikala
trinkejo, kaj iuj aliaj ankaŭ,

659
00:30:45,580 --> 00:30:49,430
kaj memoras ke ampersand ampersand
Estas io ni vidis antaŭe.

660
00:30:49,430 --> 00:30:54,060
La logika KAJ operatoro, kie vi havas
du el ili kune, aŭ la logika AŬ

661
00:30:54,060 --> 00:30:56,300
operatoro, kie vi
havas du vertikalaj stangoj.

662
00:30:56,300 --> 00:31:00,550
Bitlarĝa operatoroj, kiun ni
vidi operacii sur bitoj individue,

663
00:31:00,550 --> 00:31:03,810
nur uzi ununuran ampersand, a
ununura vertikala trinkejo, la ĉapelo simbolo

664
00:31:03,810 --> 00:31:06,620
venas poste, la malgranda
tildo, kaj tiam foriris

665
00:31:06,620 --> 00:31:08,990
krampo lasis krampon, aŭ
dekstra krampo dekstra krampo.

666
00:31:08,990 --> 00:31:10,770
Ĉiu de ĉi tiuj havas malsamajn signifojn.

667
00:31:10,770 --> 00:31:11,950
>> Fakte, ni rigardu.

668
00:31:11,950 --> 00:31:16,560
Ni iru malnova lernejo hodiaŭ, kaj uzo
ekrano táctil de la pasintaj tempoj,

669
00:31:16,560 --> 00:31:18,002
konata kiel blanka tabulo.

670
00:31:18,002 --> 00:31:19,710
Kaj tiu blanka tabulo
tuj permesos nin

671
00:31:19,710 --> 00:31:27,360
esprimi iun sufiĉe simplaj simboloj,
aŭ prefere iuj sufiĉe simplaj formuloj,

672
00:31:27,360 --> 00:31:29,560
ke ni povas tiam finfine
levilforton, por

673
00:31:29,560 --> 00:31:33,230
aliri individuajn
bitoj ene C programon.

674
00:31:33,230 --> 00:31:34,480
Alivorte, ni faru tion.

675
00:31:34,480 --> 00:31:37,080
Ni unue diskuto por
momento pri ampersand,

676
00:31:37,080 --> 00:31:39,560
kiu estas la bitlarĝa KAJ operatoro.

677
00:31:39,560 --> 00:31:42,130
En aliaj vortoj, tiu estas
operatoro kiu permesas

678
00:31:42,130 --> 00:31:45,930
mi havi maldekstra ŝanĝiĝema
tipe, kaj dekstran ŝanĝiĝema,

679
00:31:45,930 --> 00:31:50,640
aŭ individuo valoro, ke se ni KAJ
ili kune, donas al mi finan rezulton.

680
00:31:50,640 --> 00:31:51,560
Do kion mi volas diri?

681
00:31:51,560 --> 00:31:54,840
Se en programo, vi havas variablo
kiu stokas unu el tiuj valoroj,

682
00:31:54,840 --> 00:31:58,000
aŭ ni tenas ĝin simpla, kaj nur
skribi el nuloj kaj individue,

683
00:31:58,000 --> 00:32:00,940
jen kiel la ampersand operatoro funkcias.

684
00:32:00,940 --> 00:32:06,400
0 ampersand 0 tuj egali 0.

685
00:32:06,400 --> 00:32:07,210
Nun kial estas tio?

686
00:32:07,210 --> 00:32:09,291
>> Ĝi estas tre simila al
Buleaj esprimoj,

687
00:32:09,291 --> 00:32:10,540
ke ni diskutis tiom.

688
00:32:10,540 --> 00:32:15,800
Se vi pensas finfine, la 0 estas
falsa, 0 estas falsa, malvera kaj malvera

689
00:32:15,800 --> 00:32:18,720
estas, kiel ni diskutis
logike, ankaŭ malvera.

690
00:32:18,720 --> 00:32:20,270
Do ni ricevas 0 tie ankaŭ.

691
00:32:20,270 --> 00:32:24,390
Se vi prenos 0 ampersand
1, bone ke, tro,

692
00:32:24,390 --> 00:32:29,890
tuj esti 0, ĉar por tio
maldekstra esprimo esti vera aŭ 1,

693
00:32:29,890 --> 00:32:32,360
ĝi devas esti vera kaj vera.

694
00:32:32,360 --> 00:32:36,320
Sed ĉi tie ni havas falsan
kaj vera, aŭ 0 kaj 1.

695
00:32:36,320 --> 00:32:42,000
Nun ree, se ni havas 1 ampersand
0, kiu ankaŭ tuj esti 0,

696
00:32:42,000 --> 00:32:47,240
kaj se ni havas 1-simbolo 1,
fine ni havas 1 bito.

697
00:32:47,240 --> 00:32:50,340
Do alivorte, ni ne faras
ion interesan kun ĉi operatoro

698
00:32:50,340 --> 00:32:51,850
nur ankoraŭ, ĉi-simbolo operatoro.

699
00:32:51,850 --> 00:32:53,780
Estas la bitlarĝa KAJ operatoro.

700
00:32:53,780 --> 00:32:57,290
Sed jen estas la ingrediencoj
per kiu ni povas fari

701
00:32:57,290 --> 00:32:59,240
interesaj aferoj, kiel ni baldaŭ vidos.

702
00:32:59,240 --> 00:33:02,790
>> Nun ni rigardu nur la sola
vertikala stango super tie sur la dekstra.

703
00:33:02,790 --> 00:33:06,710
Se mi havas 0 iom kaj mi
AŬ ĝin kun la bitlarĝa

704
00:33:06,710 --> 00:33:11,030
OR operatoro, alia 0 iom,
ke tuj doni al mi 0.

705
00:33:11,030 --> 00:33:17,540
Se mi prenos 0 brido kaj AŬ ĝin kun
a 1 bito, tiam mi tuj ricevas 1.

706
00:33:17,540 --> 00:33:19,830
Kaj fakte, nur por
klareco, lasu min reiri,

707
00:33:19,830 --> 00:33:23,380
Kaj miajn vertikala stangoj
ne eraris ĉar 1-a.

708
00:33:23,380 --> 00:33:26,560
Lasu min reverki ĉiujn
mia 1 estas iom pli

709
00:33:26,560 --> 00:33:32,700
klare, por ke ni sekva rigardu: se mi
esti ĉirkaŭ 1 aŭ 0, ke tuj esti 1,

710
00:33:32,700 --> 00:33:39,060
kaj se mi havas 1 aŭ 1 kiu,
tro, tuj esti 1.

711
00:33:39,060 --> 00:33:42,900
Do vi povas vidi logike ke la AŬ
operatoro kondutas tre malsame.

712
00:33:42,900 --> 00:33:48,070
Tio donas min 0 aŭ 0 donas min 0, sed
ĉiu alia kombino donas min 1.

713
00:33:48,070 --> 00:33:52,480
Tiom longe kiel mi havas unu 1 en la
formulo, la rezulto tuj estos 1.

714
00:33:52,480 --> 00:33:55,580
>> Kompare kun la KAJ
operatoro, la signo,

715
00:33:55,580 --> 00:34:00,940
nur se mi havas du 1-a en la
ekvacio, do mi reale preni ĉirkaŭ 1 el.

716
00:34:00,940 --> 00:34:02,850
Nun tie estas kelkaj aliaj
operatoroj ankaŭ.

717
00:34:02,850 --> 00:34:04,810
Unu el ili estas iom pli implikitaj.

718
00:34:04,810 --> 00:34:07,980
Do lasu min antaŭeniri kaj forviŝi
ĉi liberigi iun spacon.

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

720
00:34:13,020 --> 00:34:16,460
Kaj ni rigardu la
tekstkursoran simbolo, por nur momento.

721
00:34:16,460 --> 00:34:18,210
Tiu estas tipe
karaktero vi povas tajpi

722
00:34:18,210 --> 00:34:21,420
sur via klavaro okazigon Shift kaj
tiam unu el la nombroj atop via usonaj

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

724
00:34:22,250 --> 00:34:26,190
>> Do tiu estas la ekskluziva
OR operatoro, ekskluziva AŬ.

725
00:34:26,190 --> 00:34:27,790
Do ni nur vidis la OR operatoro.

726
00:34:27,790 --> 00:34:29,348
Tio estas la ekskluziva AŬ operatoro.

727
00:34:29,348 --> 00:34:30,639
Kio estas fakte la diferenco?

728
00:34:30,639 --> 00:34:34,570
Bone ni nur rigardas la formulo,
kaj uzi tion kiel ingrediencoj finfine.

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

730
00:34:37,690 --> 00:34:39,650
Mi tuj diros estas ĉiam 0.

731
00:34:39,650 --> 00:34:41,400
Jen la difino de XOR.

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

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 tuj esti 1,
kaj 1 XOR 1 tuj estos?

734
00:34:58,810 --> 00:34:59,890
Malĝusta?

735
00:34:59,890 --> 00:35:00,520
Aŭ dekstra?

736
00:35:00,520 --> 00:35:01,860
Mi ne scias.

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

738
00:35:02,810 --> 00:35:04,700
Nun kio okazas ĉi tie?

739
00:35:04,700 --> 00:35:06,630
Nu pensu pri la
nomo de tiu operatoro.

740
00:35:06,630 --> 00:35:09,980
Ekskluziva AŬ, tiel kiel la
nomo, ia, sugestas,

741
00:35:09,980 --> 00:35:13,940
la respondo estas nur tuj estos
ĉirkaŭ 1 se la enigoj estas ekskluzivaj,

742
00:35:13,940 --> 00:35:15,560
ekskluzive malsamaj.

743
00:35:15,560 --> 00:35:18,170
Do jen la enigoj estas la
samaj, do la eligo estas 0.

744
00:35:18,170 --> 00:35:20,700
Tie la enigoj estas la
samaj, do la eligo estas 0.

745
00:35:20,700 --> 00:35:25,640
Jen la eliroj estas malsama, ili
estas ekskluzivaj, do la eligo estas 1.

746
00:35:25,640 --> 00:35:28,190
Do ĝi estas tre simila al
KAJ, ĝi estas tre simila,

747
00:35:28,190 --> 00:35:32,760
aŭ prefere ĝi estas tre simila al
AŬ, sed nur en ekskluziva maniero.

748
00:35:32,760 --> 00:35:36,210
Ĉi tiu jam ne estas 1,
ĉar ni havas du 1-a,

749
00:35:36,210 --> 00:35:38,621
kaj ne ekskluzive, nur unu el ili.

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

751
00:35:39,120 --> 00:35:40,080
Kio pri la aliaj?

752
00:35:40,080 --> 00:35:44,220
Nu la supersigno, dume, estas
vere bela kaj simpla, dankeme.

753
00:35:44,220 --> 00:35:46,410
Kaj tiu estas unuloka
operatoro, kiu signifas

754
00:35:46,410 --> 00:35:50,400
ĝi estas aplikita al nur unu enigo,
unu argumento, por tiel diri.

755
00:35:50,400 --> 00:35:51,800
Ne al maldekstra kaj dekstra.

756
00:35:51,800 --> 00:35:56,050
Alivorte, se vi prenos de supersigno
0, la respondo estos la malo.

757
00:35:56,050 --> 00:35:59,710
Kaj se vi prenos supersigno de 1, la
respondo estos la malo.

758
00:35:59,710 --> 00:36:02,570
Do la supersigno operatoro estas
maniero nei iom,

759
00:36:02,570 --> 00:36:06,000
aŭ klakanta iom el
0 al 1, aŭ 1 al 0.

760
00:36:06,000 --> 00:36:09,820
>> Kaj tio lasas por ni fine
kun nur du finaj operatoroj,

761
00:36:09,820 --> 00:36:13,840
la tn maldekstra movo, kaj la
tn dekstra skipa operatoro.

762
00:36:13,840 --> 00:36:16,620
Ni rigardu kiel tiuj laboroj.

763
00:36:16,620 --> 00:36:20,780
La maldekstra skipa operatoro, skribita
kun du angulajn krampojn tiel,

764
00:36:20,780 --> 00:36:22,110
operacias kiel sekvas.

765
00:36:22,110 --> 00:36:27,390
Se mia enigo, aŭ mia argumento al la maldekstra
skipa operatoro estas sufiĉe simple 1.

766
00:36:27,390 --> 00:36:33,750
Kaj mi diru ke la komputilo
lasis movo ke 1, diru sep lokoj,

767
00:36:33,750 --> 00:36:37,150
la rezulto estas kvazaŭ mi
preni ke 1, kaj movi ĝin

768
00:36:37,150 --> 00:36:40,160
sep lokoj trans la
maldekstra, kaj defaŭlte,

769
00:36:40,160 --> 00:36:42,270
ni tuj supozi ke
la spaco dekstren

770
00:36:42,270 --> 00:36:44,080
tuj esti suplementata nuloj.

771
00:36:44,080 --> 00:36:50,316
Alivorte, 1 lasis movo 7 tuj
doni min ke 1, sekvita per 1, 2, 3,

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

773
00:36:54,060 --> 00:36:57,380
Do en maniero, ĝi permesas
preni malgrandan nombron kiel 1,

774
00:36:57,380 --> 00:37:00,740
kaj klare fari ĝin multe
multe, multe pli granda en tiu maniero,

775
00:37:00,740 --> 00:37:06,460
sed ni vere tuj vidos
pli ruza alproksimiĝojn por ĝi

776
00:37:06,460 --> 00:37:08,080
anstataŭe, tiel,

777
00:37:08,080 --> 00:37:08,720
>> Bone.

778
00:37:08,720 --> 00:37:10,060
Estas tio por semajno tri.

779
00:37:10,060 --> 00:37:11,400
Ni vidos vin proksima fojo.

780
00:37:11,400 --> 00:37:12,770
Ĉi estis CS50.

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

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

783
00:37:22,243 --> 00:37:25,766
>> Parolanto 1: Li estis ĉe la manĝeto
bari manĝi varman fudge sundae.

784
00:37:25,766 --> 00:37:28,090
Li havis ĝin sur lian vizaĝon.

785
00:37:28,090 --> 00:37:30,506
Li portas ke ĉokolado kiel barbo

786
00:37:30,506 --> 00:37:31,756
Parolanto 2: Kion vi faras?

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

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

789
00:37:33,500 --> 00:37:36,800
>> Parolanto 2: Ĉu vi ĵus duobla ekfalo?

790
00:37:36,800 --> 00:37:38,585
Vi duobla trempis la blato.

791
00:37:38,585 --> 00:37:39,460
Parolanto 3: Pardonu.

792
00:37:39,460 --> 00:37:44,440
Parolanto 2: Vi trempis la blato, vi
prenis mordon, kaj vi trempis denove.

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

794
00:37:44,940 --> 00:37:48,440
Parolanto 2: Do jen kiel meti
via tuta busxo bone ekfalo.

795
00:37:48,440 --> 00:37:52,400
Sekvanta tempo vi prenas blato,
nur trempu gxin unufoje, kaj fini ĝin.

796
00:37:52,400 --> 00:37:53,890
>> Parolanto 3: Vi scias kion, Dan?

797
00:37:53,890 --> 00:37:58,006
Vi trempu la maniero kiun vi volas trempi.

798
00:37:58,006 --> 00:38:01,900
Mi trempos la vojo ke mi volas trempu.

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