1
00:00:00,000 --> 00:00:00,488

2
00:00:00,488 --> 00:00:10,800
>> [MUZIKO ludi]

3
00:00:10,800 --> 00:00:13,500
DAVID Malan: Bone.

4
00:00:13,500 --> 00:00:14,670
Bone, bonvenigas dorso.

5
00:00:14,670 --> 00:00:18,120
Do tiu estas Semajno 4, la komenco
gxia jam.

6
00:00:18,120 --> 00:00:21,320
Kaj vi memoras, ke pasintsemajne, ni metis
kodi flanken por nur iom

7
00:00:21,320 --> 00:00:24,240
kaj ni komencis paroli iom pli
alta nivelo, pri aferoj kiel

8
00:00:24,240 --> 00:00:28,130
serĉi kaj ordigi, kiu kvankam
iom simplaj ideoj, estas

9
00:00:28,130 --> 00:00:31,840
reprezentanto de klaso de problemoj
vi komencos solvi aparte

10
00:00:31,840 --> 00:00:34,820
kiel vi komencas pensi fino
projektoj kaj interesaj solvoj vi

11
00:00:34,820 --> 00:00:36,760
eble devus reala mondo problemojn.

12
00:00:36,760 --> 00:00:39,490
Nun bobelo varo estis unu el la plej simpla
tiaj algoritmoj, kaj ĝi

13
00:00:39,490 --> 00:00:42,900
laboris por havi tiujn malgrandajn nombrojn
en lerta aŭ en tabelo speco de

14
00:00:42,900 --> 00:00:46,530
bobelo sian vojon sur la supron, kaj la
grandaj nombroj movi sian vojon malsupren al

15
00:00:46,530 --> 00:00:47,930
la fino de tiu listo.

16
00:00:47,930 --> 00:00:50,650
>> Kaj memoru ke ni povus bildigi
bobelo speco iom

17
00:00:50,650 --> 00:00:52,310
iu kiel ĉi tio.

18
00:00:52,310 --> 00:00:53,640
Do lasu min antaŭeniri kaj klaku Start.

19
00:00:53,640 --> 00:00:55,350
Mi antaŭselektita bobelo varo.

20
00:00:55,350 --> 00:00:58,920
Kaj se vi memoras, ke la alta blua
linioj reprezentas grandaj nombroj, malgranda

21
00:00:58,920 --> 00:01:03,300
bluaj linioj reprezentas malgrandaj nombroj, kiel
ni iru tra tiu denove kaj denove kaj

22
00:01:03,300 --> 00:01:07,680
denove, komparas du trinkejoj apud ĉiu
aliaj en ruĝa, ni tuj interŝanĝi la

23
00:01:07,680 --> 00:01:11,010
plej granda kaj la plej malgranda se
ili estas el ordo.

24
00:01:11,010 --> 00:01:14,150
>> Do tiu iros kaj iros kaj iri
on, kaj vi vidos, ke la pli granda

25
00:01:14,150 --> 00:01:16,700
elementoj faras sian vojon al la
rajto, kaj la plej malgranda eroj estas

26
00:01:16,700 --> 00:01:17,900
fari sian vojon al la maldekstra.

27
00:01:17,900 --> 00:01:21,380
Sed ni komencis kvantigi
la efikeco, la

28
00:01:21,380 --> 00:01:22,970
kvaliton de ĉi tiu algoritmo.

29
00:01:22,970 --> 00:01:25,200
Kaj ni diris ke en la plej malbona
kazo, ĉi tiu algoritmo prenis

30
00:01:25,200 --> 00:01:27,940
proksimume kiom da paŝoj?

31
00:01:27,940 --> 00:01:28,980
>> Do la n kvadratoj.

32
00:01:28,980 --> 00:01:30,402
Kaj kio estis n?

33
00:01:30,402 --> 00:01:31,650
>> Spektantaro: Nombro da elementoj.

34
00:01:31,650 --> 00:01:32,790
>> DAVID Malan: Do la n estis la
nombro de elementoj.

35
00:01:32,790 --> 00:01:33,730
Kaj tiel ni faros ĉi ofte.

36
00:01:33,730 --> 00:01:36,650
Ajna tempo ni volas paroli pri la grandeco
de problemo aŭ la grandeco de

37
00:01:36,650 --> 00:01:39,140
enigo, aŭ la kvanto de tempo necesa
por produkti eliro, ni nur

38
00:01:39,140 --> 00:01:41,610
ĝeneraligita ajn
la enigo estas kiel n.

39
00:01:41,610 --> 00:01:45,970
Do denove en Semajno 0, la nombro paĝoj
en la telefono libro estis n.

40
00:01:45,970 --> 00:01:47,550
La nombro de studentoj
en la ĉambro estis n.

41
00:01:47,550 --> 00:01:49,630
Do jen, tro, ni sekvi
ke mastro.

42
00:01:49,630 --> 00:01:52,800
>> Nun n kvadratoj estas ne aparte
rapida, do ni provis fari pli bone.

43
00:01:52,800 --> 00:01:55,970
Kaj tiel ni rigardis paro de
aliaj algoritmoj, inter kiuj

44
00:01:55,970 --> 00:01:57,690
estis selektado varo.

45
00:01:57,690 --> 00:01:59,180
Do selektado varo estis
iom malsama.

46
00:01:59,180 --> 00:02:03,130
Ĝi estis preskaŭ pli simpla, mi kuraĝas diri,
per kiu mi komencis je la komenco de la

47
00:02:03,130 --> 00:02:06,740
Listo de niaj volontuloj kaj mi ĵus denove
kaj denove kaj denove iris tra

48
00:02:06,740 --> 00:02:10,060
la listo, plukinte el la plej malgranda
elemento samtempe kaj metante lin aŭ

49
00:02:10,060 --> 00:02:13,040
ŝi komence de la listo.

50
00:02:13,040 --> 00:02:16,410
>> Sed tio ankaŭ, iam ni komencis pensi
tra la matematiko kaj pli granda

51
00:02:16,410 --> 00:02:19,860
bildo, pensis pri kiom da fojoj
Mi tuj tien kaj reen kaj reen

52
00:02:19,860 --> 00:02:24,090
kaj reen, ni diris en la plej malbona kazo,
selektado varon, ankaŭ, estis kio?

53
00:02:24,090 --> 00:02:24,960
n akordis.

54
00:02:24,960 --> 00:02:27,490
Nun en la reala mondo, ĝi povus
reale esti bagatele rapida.

55
00:02:27,490 --> 00:02:30,620
Ĉar denove, mi ne devis subteni
backtracking fojon mi estis ordigitaj la

56
00:02:30,620 --> 00:02:31,880
plej malgranda eroj.

57
00:02:31,880 --> 00:02:35,090
Sed se ni pensas pri tre granda n, kaj
se vi speco de fari el la matematiko, kiel

58
00:02:35,090 --> 00:02:39,170
Mi faris sur la tabulo, kun la n kvadratoj
minus io, ĉio alia

59
00:02:39,170 --> 00:02:41,850
krom la n kvadratoj, fojo n
ricevas vere granda, ne

60
00:02:41,850 --> 00:02:42,850
vere gravas tiel.

61
00:02:42,850 --> 00:02:45,470
Do kiel komputikistoj, ni ordigi de
turnu la okulojn al la plej malgranda

62
00:02:45,470 --> 00:02:49,220
faktoroj kaj fokuso nur sur la faktoron
esprimo kiu tuj fari

63
00:02:49,220 --> 00:02:50,330
la plej granda diferenco.

64
00:02:50,330 --> 00:02:52,840
>> Nu, laste, ni rigardis
ĉe inserción varo.

65
00:02:52,840 --> 00:02:56,620
Kaj tio estis simila en spirito, sed
anstataŭ iri tra ripete kaj

66
00:02:56,620 --> 00:03:01,250
selektu la plej malgranda ero unu ĉe
tempo, mi anstataŭe prenis la manon, kiun Mi

67
00:03:01,250 --> 00:03:04,070
komercis, kaj mi decidis, ĉiuj
Bone, vi apartenas ĉi tie.

68
00:03:04,070 --> 00:03:06,160
Poste mi iris al la sekva elemento
kaj ili decidis ke li aŭ

69
00:03:06,160 --> 00:03:07,470
ŝi apartenis tie.

70
00:03:07,470 --> 00:03:08,810
Kaj poste mi kopiis kaj plu.

71
00:03:08,810 --> 00:03:11,780
Kaj mi povus al, survoje,
ŝanĝi tiuj infanoj por

72
00:03:11,780 --> 00:03:13,030
fari lokon al ili.

73
00:03:13,030 --> 00:03:16,880
Do tio estis speco de la mensa renversigon
de selektado varo kiu ni

74
00:03:16,880 --> 00:03:18,630
vokis inserción varo.

75
00:03:18,630 --> 00:03:20,810
>> Tiuj temoj okazi
en la reala mondo.

76
00:03:20,810 --> 00:03:23,640
Nur antaŭ kelkaj jaroj, kiam iu
senatano kuris al prezidanto,

77
00:03:23,640 --> 00:03:27,160
Eric Schmidt, en la tempo de la ĝenerala direktoro de
Google, efektive havis la ŝancon

78
00:03:27,160 --> 00:03:28,040
intervjui lin.

79
00:03:28,040 --> 00:03:32,010
Kaj ni pensis ke ni volas dividi tiun YouTube
detranĉi al vi tie, se ni povus turni supren

80
00:03:32,010 --> 00:03:32,950
la volumon.

81
00:03:32,950 --> 00:03:39,360
>> [VIDEO reprodukto]

82
00:03:39,360 --> 00:03:44,620
>> -Nun, Senatano, vi estas ĉi tie en Google,
kaj mi ŝatas pensi pri la prezidanteco

83
00:03:44,620 --> 00:03:46,042
kiel laboron intervjuo.

84
00:03:46,042 --> 00:03:47,770
>> [Ridado]

85
00:03:47,770 --> 00:03:50,800
>> -Nun estas malfacile akiri
laboron kiel prezidanto.

86
00:03:50,800 --> 00:03:52,480
Kaj vi iros tra
la rigorecoj nun.

87
00:03:52,480 --> 00:03:54,330
Ĝi estas ankaŭ malfacile atingi laboron ĉe Google.

88
00:03:54,330 --> 00:03:59,610
Ni havas demandojn kaj ni petas
niaj kandidatoj demandoj.

89
00:03:59,610 --> 00:04:02,250
Kaj ĉi tiu estas de Larry Schwimmer.

90
00:04:02,250 --> 00:04:05,325
>> [Ridado]

91
00:04:05,325 --> 00:04:06,400
-Vi infanoj pensas ke mi ŝercas?

92
00:04:06,400 --> 00:04:08,750
Ĝi estas ĉi tie.

93
00:04:08,750 --> 00:04:12,110
Kio estas la plej efika maniero
ordigi miliono du bitoj entjeroj?

94
00:04:12,110 --> 00:04:15,810
>> [Ridado]

95
00:04:15,810 --> 00:04:18,260
>> -Nu, uh -

96
00:04:18,260 --> 00:04:19,029
>> -I'm sorry.

97
00:04:19,029 --> 00:04:19,745
Eble ni devus -

98
00:04:19,745 --> 00:04:21,000
>> -Ne, ne, ne, ne, ne.

99
00:04:21,000 --> 00:04:21,470
>> -Tio ne estas -

100
00:04:21,470 --> 00:04:22,185
Akcepti.

101
00:04:22,185 --> 00:04:25,328
>> -Mi kredas ke la bobelo speco estus
esti la malĝusta maniero iri.

102
00:04:25,328 --> 00:04:26,792
>> [Ridado]

103
00:04:26,792 --> 00:04:28,510
>> [Huraado kaj aplaŭdoj]

104
00:04:28,510 --> 00:04:31,211
>> -Venu, kiu rakontis al li tion?

105
00:04:31,211 --> 00:04:32,155
Akcepti.

106
00:04:32,155 --> 00:04:33,350
>> [FINO reprodukto de vídeo]

107
00:04:33,350 --> 00:04:35,070
>> DAVID Malan: Do vi havas ĝin.

108
00:04:35,070 --> 00:04:39,600
Do ni komencis kvantigi tiuj kurante
tempoj, por tiel diri, per io

109
00:04:39,600 --> 00:04:43,480
vokis asimptota skribmaniero, kiu estas
nur referenco al nia speco de turnante

110
00:04:43,480 --> 00:04:47,420
blinda okulo al tiuj malgrandaj faktoroj kaj
nur rigardante la rula tempo,

111
00:04:47,420 --> 00:04:51,250
la agado de ĉi tiuj algoritmoj,
kiel n prenas vere granda tempo.

112
00:04:51,250 --> 00:04:55,110
Kaj tiel ni enkondukis granda O. Kaj granda O
reprezentis iu kiun ni pensis

113
00:04:55,110 --> 00:04:57,000
de kiel supera baro.

114
00:04:57,000 --> 00:04:59,570
Kaj efektive, Barry, ĉu ni povas malsupreniri
ol la mic iomete?

115
00:04:59,570 --> 00:05:01,040
>> Ni pensis pri ĉi tiu estas supera baro.

116
00:05:01,040 --> 00:05:04,710
Tiel granda O de n kvadratoj signifas ke en
la plej malbona kazo, iun kiel

117
00:05:04,710 --> 00:05:07,780
selektado speco prenus
n kvadrata paŝoj.

118
00:05:07,780 --> 00:05:10,310
Aŭ ion similan inserción speco
farus n kvadratoj paŝoj.

119
00:05:10,310 --> 00:05:15,150
Nun por iu kiel inserción
varon, kio estis la plej malbona kazo?

120
00:05:15,150 --> 00:05:18,200
Donita aro, kio estas la plej malbona
ebla scenaro, ke vi povus trovi

121
00:05:18,200 --> 00:05:20,650
mem alfrontis kun?

122
00:05:20,650 --> 00:05:21,860
>> Estas tute malantaŭen, ĉu ne?

123
00:05:21,860 --> 00:05:24,530
Ĉar se ĝi estas tute malantaŭen,
vi devas fari tutan multe da laboro.

124
00:05:24,530 --> 00:05:26,420
Ĉar se vi estas tute malantaŭen,
vi tuj trovos la

125
00:05:26,420 --> 00:05:28,840
plej granda elemento tie, eĉ se
ĝi apartenas tie.

126
00:05:28,840 --> 00:05:31,140
Do vi intencas diri, gravas, ĉe
ĉi tiu momento en tempo, vi apartenas ĉi tie,

127
00:05:31,140 --> 00:05:32,310
tiel vi lasas ĝin sola.

128
00:05:32,310 --> 00:05:35,425
>> Tiam vi rimarkos, ho, malbenita, mi devas
movi tiun iomete pli malgranda elemento

129
00:05:35,425 --> 00:05:36,470
maldekstre de vi.

130
00:05:36,470 --> 00:05:38,770
Do mi devos fari tion denove
kaj denove kaj denove.

131
00:05:38,770 --> 00:05:41,410
Kaj se mi iradis tien kaj reen, vi
estus ordigi de senti la agado de

132
00:05:41,410 --> 00:05:45,540
ke algoritmo, ĉar senĉese estas mi
miksanta ĉiuj aliaj malsupren en la

133
00:05:45,540 --> 00:05:46,510
tabelo por fari lokon por ĝi.

134
00:05:46,510 --> 00:05:47,750
Do jen la plej malbona kazo.

135
00:05:47,750 --> 00:05:48,570
>> Kontraŭe -

136
00:05:48,570 --> 00:05:50,320
kaj ĉi tiu estis cliffhanger lasta fojo -

137
00:05:50,320 --> 00:05:54,065
ni diris ke inserción speco
Estis omega de kio?

138
00:05:54,065 --> 00:05:57,530
Kio estas la plej kazo kurado
tempo de inserción speco?

139
00:05:57,530 --> 00:05:58,520
Do ĝi estas reale n.

140
00:05:58,520 --> 00:06:00,980
Tio estis la celo, ke ni lasis
sur la tabulo lasta fojo.

141
00:06:00,980 --> 00:06:03,160
>> Kaj estas omega de n ĉar por kio?

142
00:06:03,160 --> 00:06:06,630
Nu, en la plej bona kazo, kio estas
inserción speco tuj estos transdonita?

143
00:06:06,630 --> 00:06:09,830
Nu, lerta, ke estas tute ordo
jam, minimuma laboro por fari.

144
00:06:09,830 --> 00:06:12,460
Sed kio estas neta pri inserción speco
estas ke ĉar ĝi komenciĝas ĉi tie kaj

145
00:06:12,460 --> 00:06:15,340
decidas, ho, vi estas la nombro
unu, vi apartenas ĉi tie.

146
00:06:15,340 --> 00:06:16,970
Ho, kia bona fortuno.

147
00:06:16,970 --> 00:06:17,740
>> Vi estas la numero du.

148
00:06:17,740 --> 00:06:19,030
Vi apartenas ankaŭ ĉi tie.

149
00:06:19,030 --> 00:06:21,010
Numero tri, eĉ pli bone,
vi apartenas ĉi tie.

150
00:06:21,010 --> 00:06:25,210
Tuj kiam ĝi alvenas al la fino de la
listo, por inserción speco de _pseudocode_

151
00:06:25,210 --> 00:06:28,010
ke ni promenis tra parole
lasta fojo, ĝi estas farita.

152
00:06:28,010 --> 00:06:32,790
Sed selektado varon, per kontrasto,
tenis fari kion?

153
00:06:32,790 --> 00:06:35,260
>> Tenis irante tra la listo
denove kaj denove kaj denove.

154
00:06:35,260 --> 00:06:39,160
Ĉar la ŝlosilo komprenon estis nur
iam vi rigardis la tutan vojon al la

155
00:06:39,160 --> 00:06:42,500
fino de la listo vi povas esti certa
ke la elemento vi selektis estis

156
00:06:42,500 --> 00:06:45,560
ja la nuntempe plej malgranda ero.

157
00:06:45,560 --> 00:06:48,920
Do tiuj malsamaj mensaj modeloj fino
cedante iuj tre reala mondo

158
00:06:48,920 --> 00:06:53,130
diferencoj por ni, tiel kiel tiuj
teoria asimptota diferencoj.

159
00:06:53,130 --> 00:06:56,910
>> Do nur por recap do granda O de n
kvadrata, ni vidis kelkajn tiajn

160
00:06:56,910 --> 00:06:58,350
algoritmoj tiom.

161
00:06:58,350 --> 00:06:59,580
Granda a de n?

162
00:06:59,580 --> 00:07:02,870
Kio estas algoritmo kiu povis
esti dirita al esti granda O de n?

163
00:07:02,870 --> 00:07:06,930
En la plej malbona kazo, ĝi prenas
lineara nombro da paŝoj.

164
00:07:06,930 --> 00:07:07,810
>> OK, lineara serĉo.

165
00:07:07,810 --> 00:07:10,470
Kaj en la plej malbona kazo, kie estas la
elemento vi serĉas kiam

166
00:07:10,470 --> 00:07:12,950
aplikante lineara serĉo?

167
00:07:12,950 --> 00:07:14,680
>> OK, en la plej malbona kazo,
ĝi ne estas ankoraŭ tie.

168
00:07:14,680 --> 00:07:17,000
Aŭ en la dua plej malbona kazo, ĝi estas
tuta vojo al la fino, kiu estas

169
00:07:17,000 --> 00:07:18,880
pli-aŭ-minus unu-paŝo diferencon.

170
00:07:18,880 --> 00:07:21,180
Do, je la fino de la tago,
ni povas diri estas lineara.

171
00:07:21,180 --> 00:07:23,910
Granda a de n devus esti lineara serĉo,
ĉar en la plej malbona kazo, la

172
00:07:23,910 --> 00:07:26,610
elemento estas eĉ ne ekzistas aŭ estas
tuta vojo al la fino.

173
00:07:26,610 --> 00:07:29,370
>> Nu, granda O de logo de n.

174
00:07:29,370 --> 00:07:32,760
Ni ne parolas tre detale pri
ĉi tio, sed ni vidis ĉi tion antaŭe.

175
00:07:32,760 --> 00:07:36,840
Kio kuras en tn logaritma
tempo, en la plej malbona kazo?

176
00:07:36,840 --> 00:07:38,500
>> Jes, tiel duuma serĉo.

177
00:07:38,500 --> 00:07:42,930
Kaj duuma serĉo en la plej malbona kazo
povus havi la elemento ie en

178
00:07:42,930 --> 00:07:45,640
la meza, aŭ ie
ene de la tabelo.

179
00:07:45,640 --> 00:07:48,040
Sed vi nur trovos ĝin iam vi
dividi la liston en duono, en

180
00:07:48,040 --> 00:07:48,940
duono, la duono, la duono.

181
00:07:48,940 --> 00:07:50,200
Kaj tiam voilà, estas tie.

182
00:07:50,200 --> 00:07:52,500
Aŭ denove, plej malbona kazo,
ĝi ne estas ankoraŭ tie.

183
00:07:52,500 --> 00:07:56,770
Sed vi ne scias ke ĝi ne estas tie
ĝis vi ia atingi tiun lastan

184
00:07:56,770 --> 00:08:00,470
fundo-plej elementojn per _halving_
kaj _halving_ kaj _halving_.

185
00:08:00,470 --> 00:08:01,400
>> Granda a de 1.

186
00:08:01,400 --> 00:08:03,540
Do ni povus granda O de 2, granda O de 3.

187
00:08:03,540 --> 00:08:06,260
Anytime vi volas nur konstanta numeron,
ni simple ordigi de iom simpligi

188
00:08:06,260 --> 00:08:07,280
ke kiel granda O de 1.

189
00:08:07,280 --> 00:08:10,440
Kvankam se realisme, preno
2 aŭ eĉ 100 paŝoj, se estas

190
00:08:10,440 --> 00:08:13,680
konstanta nombro da paŝoj,
ni simple diru granda O de 1.

191
00:08:13,680 --> 00:08:15,930
Kio estas algoritmo kiu estas
en granda a de 1?

192
00:08:15,930 --> 00:08:18,350
>> Spektantaro: Trovanta la longo
de variablo.

193
00:08:18,350 --> 00:08:21,090
>> DAVID Malan: Trovanta la
longo de variablo?

194
00:08:21,090 --> 00:08:23,870
>> Spektantaro: Ne, la longo
se ĝi estas jam ordo.

195
00:08:23,870 --> 00:08:24,160
>> DAVID Malan: Bonan.

196
00:08:24,160 --> 00:08:27,850
Bone, do trovi la longo de io
se la longo de tiu io, kiel

197
00:08:27,850 --> 00:08:30,020
tabelo, estas stokita en iu variablo.

198
00:08:30,020 --> 00:08:33,380
Ĉar vi povas simple legis la variablo,
aŭ presi la variablo, aux

199
00:08:33,380 --> 00:08:34,960
nur ĝenerale konsentas, ke variablo.

200
00:08:34,960 --> 00:08:37,299
Kaj voilà, kiu prenas konstantan tempo.

201
00:08:37,299 --> 00:08:38,909
>> Por kontrasto, pensu reen al skrapi.

202
00:08:38,909 --> 00:08:42,460
Pensu reen al la unua semajno de C,
nomante nur printf kaj presi

203
00:08:42,460 --> 00:08:46,240
iun sur la ekrano estas nediskuteble
konstanta tempo, ĉar ĝi nur prenas

204
00:08:46,240 --> 00:08:50,880
iu numero de CPU cikloj montri
ke teksto sur la ekrano.

205
00:08:50,880 --> 00:08:52,720
Aŭ atendu - faras ĝin?

206
00:08:52,720 --> 00:08:56,430
Kiel alia eble ni modeligi la
agado de printf?

207
00:08:56,430 --> 00:09:00,420
Ĉu iu ŝatus malkonsentas, ke
eble ĝi ne estas vere konstanta tempo?

208
00:09:00,420 --> 00:09:03,600
En kiu senco povus printf estas kurante
tempo, vere presi ĉenon sur

209
00:09:03,600 --> 00:09:05,580
la ekrano, esti io
alia ol konstanta.

210
00:09:05,580 --> 00:09:07,860
>> Spektantaro: [inaudibles].

211
00:09:07,860 --> 00:09:08,230
>> DAVID Malan: Jes.

212
00:09:08,230 --> 00:09:09,300
Do ĝi dependas nia perspektivo.

213
00:09:09,300 --> 00:09:13,390
Se ni vere pensas pri la enigo al
printf kiel la kordo, kaj

214
00:09:13,390 --> 00:09:16,380
do ni mezuri la grandecon de tiu
enigo de ĝia longo - do ni nomas

215
00:09:16,380 --> 00:09:17,780
ke longo n tiel -

216
00:09:17,780 --> 00:09:21,990
nediskuteble, printf estas sin granda O de n
ĉar tuj prenos vin n paŝoj

217
00:09:21,990 --> 00:09:24,750
por presi ĉiu el tiuj n
karakterojn, plej probabla.

218
00:09:24,750 --> 00:09:27,730
Almenaŭ en la mezuro ke ni supozi
ke eble ĝi estas uzanta por buklo

219
00:09:27,730 --> 00:09:28,560
sub la kapuĉo.

220
00:09:28,560 --> 00:09:30,860
>> Sed ni devus rigardi ke
kodi kompreni ĝin pli bone.

221
00:09:30,860 --> 00:09:33,650
Kaj efektive, post kiam vi infanoj komencu
analizi vian propran algoritmoj, vi

222
00:09:33,650 --> 00:09:34,900
laŭvorte fari ĝuste tion.

223
00:09:34,900 --> 00:09:37,765
Speco de okulo via kodo kaj opinias
pri - bone, mi havas buklo

224
00:09:37,765 --> 00:09:41,870
ĉi tie aŭ Mi havas nestitaj maŝojn tie,
ke tuj faros n aĵoj n fojoj,

225
00:09:41,870 --> 00:09:46,050
kaj vi povas ordigi de racio vian vojon
tra la kodon, eĉ se ĝi estas

226
00:09:46,050 --> 00:09:47,980
_pseudocode_ kaj ne reala kodo.

227
00:09:47,980 --> 00:09:49,730
>> Do kio pri omega de n kvadratoj?

228
00:09:49,730 --> 00:09:53,582
Kio estis algoritmo kiu en la plej bona
kazo, ankoraŭ prenis n kvadrataj gradoj?

229
00:09:53,582 --> 00:09:54,014
Jes?

230
00:09:54,014 --> 00:09:54,880
>> Spektantaro: [inaudibles].

231
00:09:54,880 --> 00:09:55,900
>> DAVID Malan: Do selektado varo.

232
00:09:55,900 --> 00:09:59,150
Ĉar en tiu problemo vere reduktita
al la fakto ke denove, mi ne scias

233
00:09:59,150 --> 00:10:02,600
Mi trovis la nuna malgranda ĝis
Mi kontrolis ĉiujn Darn elementoj.

234
00:10:02,600 --> 00:10:08,050
Do omega de, ekzemple, n, ni
nur suprenvenis kun tiu.

235
00:10:08,050 --> 00:10:09,300
Insertion varo.

236
00:10:09,300 --> 00:10:12,370
Se la listo okazas esti ordo
Jam, en la plej bona kazo nur devas

237
00:10:12,370 --> 00:10:15,090
por fari unu pasas tra ĝi,
je kiu punkto ni estas certa.

238
00:10:15,090 --> 00:10:17,890
Kaj tiam tiu povus diri
esti lineara, sekura.

239
00:10:17,890 --> 00:10:20,570
>> Kio pri omega de 1?

240
00:10:20,570 --> 00:10:23,790
Kio, en la plej bona kazo, povus preni
konstanta nombro da paŝoj?

241
00:10:23,790 --> 00:10:27,220
Do lineara serĉo, se vi simple akiri bonŝanca
kaj la elemento vi serĉas

242
00:10:27,220 --> 00:10:31,000
Estas ĝuste en la komenco de la listo,
se tio estas kie vi estas startanta via

243
00:10:31,000 --> 00:10:33,070
lineara trairado de tiu listo.

244
00:10:33,070 --> 00:10:35,180
>> Kaj ĉi tiu estas vera de
nombro de aĵoj.

245
00:10:35,180 --> 00:10:37,660
Ekzemple, eĉ duumaj
serĉo estas omega de 1.

246
00:10:37,660 --> 00:10:40,310
Pro kio se vi ricevas vere Darn
sorton kaj smack-DAB en la mezo de

247
00:10:40,310 --> 00:10:42,950
via tabelo estas la nombro
vi serĉas?

248
00:10:42,950 --> 00:10:45,730
Do vi povas akiri bonŝanca tie, kiel bone.

249
00:10:45,730 --> 00:10:49,190
>> Ĉi tiu, laste, omega de n logo n.

250
00:10:49,190 --> 00:10:52,573
Do n logo n, ni ne vere
paroli ankoraŭ, sed -

251
00:10:52,573 --> 00:10:53,300
>> Spektantaro: Kunfandi speco?

252
00:10:53,300 --> 00:10:53,960
>> DAVID Malan: Merge varo.

253
00:10:53,960 --> 00:10:56,920
Tio estis la cliffhanger de lasta fojo,
kie oni proponis, kaj ni montris

254
00:10:56,920 --> 00:10:58,600
vide, ke ekzistas algoritmoj.

255
00:10:58,600 --> 00:11:02,470
Kaj kunfandi speco de nur unu tia
algoritmo kiu estas fundamente rapida

256
00:11:02,470 --> 00:11:03,450
ol iuj el tiuj aliaj infanoj.

257
00:11:03,450 --> 00:11:07,800
Fakte, kunfandi mallonga ne estas nur en la
bona kazo n logo n, en la plej malbona

258
00:11:07,800 --> 00:11:09,460
kazo n logo n.

259
00:11:09,460 --> 00:11:14,540
Kaj kiam vi havas ĉi koincido de
omega kaj granda O estas la sama afero?

260
00:11:14,540 --> 00:11:17,310
Ni povas vere priskribi ke kiel kio estas
vokis theta, kvankam ĝi estas

261
00:11:17,310 --> 00:11:18,220
iom malpli komunaj.

262
00:11:18,220 --> 00:11:21,730
Sed tio nur signifas la du baroj,
en ĉi tiu kazo, estas la sama.

263
00:11:21,730 --> 00:11:25,770
>> Do kunfandi varon, kion faras tiu
vere boli malsupren al por ni?

264
00:11:25,770 --> 00:11:27,000
Nu, memoru la motivado.

265
00:11:27,000 --> 00:11:30,340
Lasu min eltiri alian kuraĝigo kiu
Ni ne rigardu lasta fojo.

266
00:11:30,340 --> 00:11:33,390
Ĉi tiu, sama ideo, sed
ĝi estas iom pli granda.

267
00:11:33,390 --> 00:11:36,160
Kaj mi tuj iros antaŭen kaj atentigi
unua - ni havas inserción speco de

268
00:11:36,160 --> 00:11:39,410
supre maldekstre, tiam selektado varon,
bobelo varon, paro de aliaj varoj -

269
00:11:39,410 --> 00:11:42,670
konko kaj rapidaj - ke ni ne parolis
pri, kaj amaso kaj kunfandi varo.

270
00:11:42,670 --> 00:11:47,090
>> Do almenaŭ provi enfokusigi viajn okulojn
la supro tri sur la maldekstra kaj poste

271
00:11:47,090 --> 00:11:49,120
kunfandi speco kiam mi premas
tiu verda sago.

272
00:11:49,120 --> 00:11:51,900
Sed mi permesos ĉiuj ili kuras, nur por
doni al vi la senton de la diverseco de

273
00:11:51,900 --> 00:11:53,980
algoritmoj kiuj ekzistas en la mondo.

274
00:11:53,980 --> 00:11:56,180
Mi tuj liberigos tiun run
por nur kelkajn sekundojn.

275
00:11:56,180 --> 00:11:59,640
Kaj se vi enfokusigi la okulojn - elektu
algoritmo, enfokusigi ĝin por nur

276
00:11:59,640 --> 00:12:02,970
duaj - vi komencos vidi la
mastro ke ĝi estas apliko.

277
00:12:02,970 --> 00:12:04,530
>> Kunfandi varon, avizo, estas farita.

278
00:12:04,530 --> 00:12:06,430
Multigu varon, rapida varon, konko -

279
00:12:06,430 --> 00:12:09,480
do ŝajnas al ni enkondukis la tri
plej malbona algoritmoj pasintsemajne.

280
00:12:09,480 --> 00:12:12,960
Sed tio estas bone, ke ni estas ĉi tie hodiaŭ
rigardi merge varon, kiu estas unu el

281
00:12:12,960 --> 00:12:16,500
des pli facile ones estas rigardi, eĉ
kvankam ĝi probable estos fleksi via menso

282
00:12:16,500 --> 00:12:17,490
malmulta.

283
00:12:17,490 --> 00:12:21,130
Ĉi tie ni povas vidi kiom da
selektado speco sucks.

284
00:12:21,130 --> 00:12:24,600
>> Sed sur la turnon flanko, estas
vere facile apliki.

285
00:12:24,600 --> 00:12:28,160
Kaj eble por P Serio 3, kiu estas unu el la
algoritmoj vi elektis por apliki

286
00:12:28,160 --> 00:12:28,960
por la normo eldono.

287
00:12:28,960 --> 00:12:30,970
Perfekte bone, perfekte ĝustaj.

288
00:12:30,970 --> 00:12:35,210
>> Sed denove, kiel n prenas granda, se vi
elekti apliki pli rapida algoritmo

289
00:12:35,210 --> 00:12:39,020
kiel kunfandi varon, prognozoj estas en pli granda kaj
granda enigoj, via kodo estas nur

290
00:12:39,020 --> 00:12:39,800
tuj kuri pli rapide.

291
00:12:39,800 --> 00:12:41,090
Via retejo estas tuj pli bone funkcii.

292
00:12:41,090 --> 00:12:42,650
Via uzantoj tuj estos pli feliĉa.

293
00:12:42,650 --> 00:12:45,280
Kaj tiel estas tiuj efektoj
de reale donante

294
00:12:45,280 --> 00:12:47,350
ni iom pli profunde pensis.

295
00:12:47,350 --> 00:12:49,990
>> Do ni rigardu kion kunfandi
varo estas reale okazas.

296
00:12:49,990 --> 00:12:52,992
La malvarmeta estas kiu kunfandi
varo estas ĝuste ĉi tiu.

297
00:12:52,992 --> 00:12:56,300
Jen, denove, kion ni nomas
_pseudocode_, _pseudocode_ estaĵo

298
00:12:56,300 --> 00:12:57,720
Esperanto-simila sintakso.

299
00:12:57,720 --> 00:12:59,890
Kaj la simpleco estas
speco de fascina.

300
00:12:59,890 --> 00:13:02,840
>> Do enigo de n elementoj - tiel ke
nur signifas, jen tabelo.

301
00:13:02,840 --> 00:13:04,000
Ĝi atingis n aĵoj en ĝi.

302
00:13:04,000 --> 00:13:05,370
Tio estas ĉio ni dirante tie.

303
00:13:05,370 --> 00:13:07,560
>> Se n estas malpli ol 2, reveni.

304
00:13:07,560 --> 00:13:08,640
Do tio estas nur la bagatela afero.

305
00:13:08,640 --> 00:13:12,580
Se n estas malpli ol 2, tiam evidente estas
1 aŭ 0, en kiu kazo la afero

306
00:13:12,580 --> 00:13:14,780
Jam ordo aŭ neekzistanta,
tiel simple reveni.

307
00:13:14,780 --> 00:13:15,900
Estas nenio por fari.

308
00:13:15,900 --> 00:13:18,360
Do tio estas simpla kazo desxiri malproksime.

309
00:13:18,360 --> 00:13:20,110
>> Alie, ni havas tri paŝoj.

310
00:13:20,110 --> 00:13:23,650
Ordigi la maldekstra duono de la elementoj, speco
la dekstra duono de la elementoj,

311
00:13:23,650 --> 00:13:26,650
kaj poste kunfandi la ordo duonoj.

312
00:13:26,650 --> 00:13:29,400
Kio estas interese estas, ke
Mi estas speco de punting, ĉu ne?

313
00:13:29,400 --> 00:13:32,300
Estas speco de cirkla difino
al ĉi algoritmo.

314
00:13:32,300 --> 00:13:35,986
En kiu senco ĉi tiu algoritmo estas
difino cirkuli?

315
00:13:35,986 --> 00:13:37,850
>> Spektantaro: [inaudibles].

316
00:13:37,850 --> 00:13:41,670
>> DAVID Malan: Jes, mia ordigado algoritmo,
du de liaj paŝoj estas "speco

317
00:13:41,670 --> 00:13:44,640
io. "Kaj tial petas la
demando, nu, kion mi povos uzi

318
00:13:44,640 --> 00:13:46,460
ordigi la maldekstra duono
kaj la dekstra duono?

319
00:13:46,460 --> 00:13:49,600
Kaj la beleco estas, ke kvankam
denove, ĉi tiu estas la menso-fleksante

320
00:13:49,600 --> 00:13:54,030
parto potenciale, vi povas uzi saman
algoritmo por ordigi la maldekstra duono.

321
00:13:54,030 --> 00:13:54,700
>> Sed atendu momenton.

322
00:13:54,700 --> 00:13:57,070
Kiam vi diris ordigi la
maldekstra duono, kio estas la du

323
00:13:57,070 --> 00:13:58,240
paŝoj tuj estos poste?

324
00:13:58,240 --> 00:14:00,550
Ni ordigi la maldekstra duono de la
maldekstra duono kaj la rajto

325
00:14:00,550 --> 00:14:01,420
duonon de la maldekstra duono.

326
00:14:01,420 --> 00:14:04,430
Malbenita, kiel mi ordigi tiujn du
duonoj aux kazernoj, nun?

327
00:14:04,430 --> 00:14:05,260
>> Sed tio estas okej.

328
00:14:05,260 --> 00:14:07,830
Ni havas ordiga algoritmo tie.

329
00:14:07,830 --> 00:14:10,660
Kaj eĉ se vi povus maltrankviligi ĉe
unue tio estas speco de senfina

330
00:14:10,660 --> 00:14:12,780
buklo, estas ciklo tio neniam
tuj enfluos - tuj

331
00:14:12,780 --> 00:14:15,770
fini unufoje kio okazas?

332
00:14:15,770 --> 00:14:16,970
Iam n estas malpli ol 2.

333
00:14:16,970 --> 00:14:19,180
Kiu eventuale okazos,
ĉar se vi observos kaj _halving_

334
00:14:19,180 --> 00:14:23,020
_halving_ en _halving_ tiuj duonoj, verŝajne
eventuale vi tuj enfluos

335
00:14:23,020 --> 00:14:25,350
kun nur 1 aŭ 0 elementoj.

336
00:14:25,350 --> 00:14:28,500
Je kiu punkto, ĉi tiu algoritmo
Diras vi faris.

337
00:14:28,500 --> 00:14:31,020
>> Do la vera magio en tiu
algoritmo ŝajnas esti en

338
00:14:31,020 --> 00:14:33,470
tiu fina paŝo, kunfandante.

339
00:14:33,470 --> 00:14:37,190
Tiu simpla ideo nur kunfandi du
aferoj, tio estas kio finfine irante

340
00:14:37,190 --> 00:14:40,920
por permesi al ni ordigi tabelo de,
diru, ok elementoj.

341
00:14:40,920 --> 00:14:44,410
Do mi havas ok pli streso pilkojn supren
ĉi tie, ok pecoj de papero, kaj unu

342
00:14:44,410 --> 00:14:45,500
Google Vitra -

343
00:14:45,500 --> 00:14:46,140
kiun mi ricevas gardi.

344
00:14:46,140 --> 00:14:46,960
>> [Ridado]

345
00:14:46,960 --> 00:14:48,970
>> DAVID Malan: Se ni povus preni ok
volontuloj, kaj ni vidu, se ni povas

346
00:14:48,970 --> 00:14:51,430
ludi ĉi, do.

347
00:14:51,430 --> 00:14:52,500
Wow, OK.

348
00:14:52,500 --> 00:14:53,565
Komputika fariĝas amuzo.

349
00:14:53,565 --> 00:14:54,320
Ĉio bone.

350
00:14:54,320 --> 00:14:57,770
Do kiel pri vi tri,
grandaj manoj tie supre.

351
00:14:57,770 --> 00:14:58,580
Kvar en la dorso.

352
00:14:58,580 --> 00:15:02,220
Kaj kion pri ni faros vin
tri en tiu vico?

353
00:15:02,220 --> 00:15:03,390
Kaj kvar en la fronto.

354
00:15:03,390 --> 00:15:04,920
Do vi ok, venu supren.

355
00:15:04,920 --> 00:15:12,060
>> [Ridado]

356
00:15:12,060 --> 00:15:13,450
>> DAVID Malan: Mi estas reale
ne certas kion ĝi estas.

357
00:15:13,450 --> 00:15:14,810
Ĉu la streso pilkoj?

358
00:15:14,810 --> 00:15:16,510
La tablo lampojn?

359
00:15:16,510 --> 00:15:18,650
La materialo?

360
00:15:18,650 --> 00:15:19,680
La interreto?

361
00:15:19,680 --> 00:15:20,160
>> Akcepti.

362
00:15:20,160 --> 00:15:21,310
Do venu supren.

363
00:15:21,310 --> 00:15:22,310
Kiu ŝatus -

364
00:15:22,310 --> 00:15:23,570
teni venas supren.

365
00:15:23,570 --> 00:15:24,240
Ni vidu.

366
00:15:24,240 --> 00:15:26,460
Kaj ĉi tio metas vin en situo -

367
00:15:26,460 --> 00:15:27,940
vi estas en loko unu.

368
00:15:27,940 --> 00:15:28,670
Uh-oh, atendu momenton.

369
00:15:28,670 --> 00:15:30,760
1, 2, 3, 4, 5, 6, 7 - ho, bona.

370
00:15:30,760 --> 00:15:31,310
Bone, ni estas bona.

371
00:15:31,310 --> 00:15:35,130
Bone, do ĉiuj havas sidejon,
sed ne sur la Google Pokalo.

372
00:15:35,130 --> 00:15:36,475
Lasu min vosto tiuj supren.

373
00:15:36,475 --> 00:15:37,115
Kio estas via nomo?

374
00:15:37,115 --> 00:15:37,440
>> Michelle: Michelle.

375
00:15:37,440 --> 00:15:38,090
>> DAVID Malan: Michelle?

376
00:15:38,090 --> 00:15:42,000
Bone, vi akiras por simili
la geek, se tio estas okej.

377
00:15:42,000 --> 00:15:44,625
Nu, mi ne faras tro, mi supozas,
por nur momento.

378
00:15:44,625 --> 00:15:45,875
Bone, atendas.

379
00:15:45,875 --> 00:15:48,510

380
00:15:48,510 --> 00:15:50,950
Ni estis provante supreniru kun
uzi kazo por Google Pokalo, kaj ni

381
00:15:50,950 --> 00:15:53,750
pensis ke estus amuze nur faru
tiu, kiam homoj estas scenejo.

382
00:15:53,750 --> 00:15:57,120
Ni registros la mondo
de lia perspektivo.

383
00:15:57,120 --> 00:15:58,410
Ĉio bone.

384
00:15:58,410 --> 00:15:59,830
Ne verŝajne kio Google intencita.

385
00:15:59,830 --> 00:16:02,260
Bone, se vi ne atentas portante
tiu por la sekvanta mallerta minutoj,

386
00:16:02,260 --> 00:16:03,150
kiu estus mirinda.

387
00:16:03,150 --> 00:16:08,620
>> Bone, do ni havas ĉi tie tabelo de
elementoj, kaj tiu tabelo, kiel por la

388
00:16:08,620 --> 00:16:11,480
pecoj de papero en ĉi tiuj uloj '
manoj, nuntempe Unsorted.

389
00:16:11,480 --> 00:16:12,050
>> Michelle: Ho, tio estas tiom stranga.

390
00:16:12,050 --> 00:16:12,810
>> DAVID Malan: Estas sufiĉe multe hazardo.

391
00:16:12,810 --> 00:16:15,760
Kaj en nur momente, ni tuj provi
apliki kunfandi speco kune

392
00:16:15,760 --> 00:16:17,950
kaj vidu kie tiu ŝlosilo komprenon estas.

393
00:16:17,950 --> 00:16:21,970
Kaj la artifiko ĉi tie kun merge varo estas
iu kiun ni ne supozis ankoraŭ.

394
00:16:21,970 --> 00:16:24,030
Ni vere bezonas iun
plia spaco.

395
00:16:24,030 --> 00:16:26,650
Do kio okazas al esti aparte
interesa pri tio estas, ke tiuj

396
00:16:26,650 --> 00:16:29,270
infanoj tuj movi iom
iom, ĉar mi tuj supozi ke

397
00:16:29,270 --> 00:16:31,880
ekzistas ekstra tabelo de spaco,
diri, ĝuste malantaŭ ili.

398
00:16:31,880 --> 00:16:34,570
>> Do, se ili estas malantaŭ lia seĝo,
tio estas la malĉefa tabelo.

399
00:16:34,570 --> 00:16:36,960
Se ili estas sidas ĉi tie, tio estas
la ĉefa tabelo.

400
00:16:36,960 --> 00:16:40,170
Sed tio estas rimedo, kiun ni havas
ne leveraged tiel for kun bobelo

401
00:16:40,170 --> 00:16:42,040
varo, kun elekto varon,
kun inserción varo.

402
00:16:42,040 --> 00:16:44,600
Memori pasintsemajne, ĉiuj nur
speco de ludkartaro en loko.

403
00:16:44,600 --> 00:16:46,840
Ili ne uzis neniu plia memoro.

404
00:16:46,840 --> 00:16:49,310
Ni faris spacon por homoj de
movi homoj ĉirkaŭe.

405
00:16:49,310 --> 00:16:50,580
>> Do tiu estas ŝlosila komprenon, ankaŭ.

406
00:16:50,580 --> 00:16:53,410
Estas ĉi tiu kompromiso, ĝenerale en
komputiko, de rimedoj.

407
00:16:53,410 --> 00:16:55,800
Se vi volas rapidigi ion
kiel tempo, vi tuj

408
00:16:55,800 --> 00:16:56,900
devas pagi prezon.

409
00:16:56,900 --> 00:17:00,750
Kaj unu el tiuj prezoj estas tre ofte
spaco, la kvanto de memoro aŭ malmola

410
00:17:00,750 --> 00:17:01,700
diskspaco ke vi uzas.

411
00:17:01,700 --> 00:17:03,640
Aŭ, sincere, la kvanto
de programisto tempo.

412
00:17:03,640 --> 00:17:06,700
Kiom da tempo prenas al vi, la homo,
al reale efektivigi iujn pli

413
00:17:06,700 --> 00:17:07,829
komplika algoritmo.

414
00:17:07,829 --> 00:17:09,760
Sed por hodiaŭ, la kompromiso
estas tempo kaj spaco.

415
00:17:09,760 --> 00:17:11,930
>> Do se vi infanoj povus simple teni vian
nombroj do ni povas vidi ke vi estas

416
00:17:11,930 --> 00:17:15,839
ja kongruas 4, 2, 6, 1, 3, 7, 8.

417
00:17:15,839 --> 00:17:16,599
Bonega.

418
00:17:16,599 --> 00:17:19,520
Do mi tuj provos orquestar
aĵoj, se vi infanoj povas simple

419
00:17:19,520 --> 00:17:21,800
sekvas mian plumbo tie.

420
00:17:21,800 --> 00:17:26,650
>> Do mi tuj apliki, unue, la
unua paŝo de la _pseudocode_, kiu estas

421
00:17:26,650 --> 00:17:29,440
sur enigo de n eroj, se n estas
malpli ol 2, tiam revenu.

422
00:17:29,440 --> 00:17:31,370
Evidente, ke ne
validas, do ni pluiru.

423
00:17:31,370 --> 00:17:33,340
Do ordigi la maldekstra duono de la elementoj.

424
00:17:33,340 --> 00:17:36,220
Do tio signifas ke mi tuj enfokusigi mia
atenton por nur momente sur tiuj

425
00:17:36,220 --> 00:17:37,310
kvar infanoj tie.

426
00:17:37,310 --> 00:17:39,774
Bone, kion mi sekva fari?

427
00:17:39,774 --> 00:17:40,570
>> Spektantaro: ordigi la maldekstra duono.

428
00:17:40,570 --> 00:17:42,780
>> DAVID Malan: Do nun mi devas ordigi
la maldekstra duono de tiuj infanoj.

429
00:17:42,780 --> 00:17:45,580
Ĉar denove, supozi al vi mem la
celo estas ordigi la maldekstra duono.

430
00:17:45,580 --> 00:17:46,440
Kiel vi faris tion?

431
00:17:46,440 --> 00:17:49,140
Nur sekvi la instrukciojn, eĉ
kvankam ni faras ĝin denove.

432
00:17:49,140 --> 00:17:50,160
Do ordigi la maldekstra duono.

433
00:17:50,160 --> 00:17:52,030
Nun mi ordiga tiuj du infanoj.

434
00:17:52,030 --> 00:17:53,563
Kio venas tuj?

435
00:17:53,563 --> 00:17:54,510
>> Spektantaro: ordigi la maldekstra duono.

436
00:17:54,510 --> 00:17:55,460
>> DAVID Malan: ordigi la maldekstra duono.

437
00:17:55,460 --> 00:18:00,680
Do nun ĉi tiuj, tiu seĝo ĉi tie,
estas listo de amplekso 1.

438
00:18:00,680 --> 00:18:01,365
Kaj kio estas via nomo denove?

439
00:18:01,365 --> 00:18:02,390
>> PRINCINO lekanto: Princino Lekanto.

440
00:18:02,390 --> 00:18:03,690
>> DAVID Malan: Princino Lekanto estas ĉi tie.

441
00:18:03,690 --> 00:18:07,470
Kaj tiel ŝi jam ordo, ĉar
la listo estas de amplekso 1.

442
00:18:07,470 --> 00:18:09,490
Kion mi sekva fari?

443
00:18:09,490 --> 00:18:13,680
OK, revenu, ĉar tiu listo estas de
grandeco 1, kiu estas malpli ol 2.

444
00:18:13,680 --> 00:18:14,320
Tiam kio estas la sekva paŝo?

445
00:18:14,320 --> 00:18:17,490
Kaj nun vi devas speco de
backtrack en via menso.

446
00:18:17,490 --> 00:18:19,340
>> Ordigi la dekstran duonon, kiu estas -

447
00:18:19,340 --> 00:18:19,570
kio estas via nomo?

448
00:18:19,570 --> 00:18:20,220
>> Linda: Linda.

449
00:18:20,220 --> 00:18:20,980
>> DAVID Malan: Linda.

450
00:18:20,980 --> 00:18:23,210
Kaj do kion ni faru nun ke
ni havas liston de amplekso 1?

451
00:18:23,210 --> 00:18:24,440
>> Spektantaro: Reveno.

452
00:18:24,440 --> 00:18:24,760
>> DAVID Malan: Zorga.

453
00:18:24,760 --> 00:18:29,540
Ni revenos unua, kaj nun la tria
paŝo - kaj se mi specon de bildigas ĝin

454
00:18:29,540 --> 00:18:33,490
brakumante la du seĝoj nun, nun mi
devas mem kunfandi tiujn du elementoj.

455
00:18:33,490 --> 00:18:35,530
Do nun, bedaŭrinde, la elementoj
estas ekstere de ordo.

456
00:18:35,530 --> 00:18:39,920
Sed tio estas kie la kunfandi procezo
komencas akiri konvinka.

457
00:18:39,920 --> 00:18:42,410
>> Do se vi infanoj povis ekstari por nur
momento, mi tuj bezonas vin, en

458
00:18:42,410 --> 00:18:44,170
Nuntempe, por treti malantaux vian seĝon.

459
00:18:44,170 --> 00:18:46,480
Kaj se Linda, ĉar 2 estas
pli malgranda ol 4, kial ne

460
00:18:46,480 --> 00:18:48,130
vi venis ĉirkaŭ la unua?

461
00:18:48,130 --> 00:18:48,690
Restu tie.

462
00:18:48,690 --> 00:18:50,520
Do Bela, vi alvenis ĉirkaŭ unue.

463
00:18:50,520 --> 00:18:53,820
>> Nun en la realo, se estas nur tabelo
ni povus simple movi sxin en reala tempo

464
00:18:53,820 --> 00:18:55,360
el tiu ĉi seĝo ĉi loko.

465
00:18:55,360 --> 00:18:57,770
Do imagu, ke prenis iu konstanto
nombro de paŝoj 1.

466
00:18:57,770 --> 00:18:58,480
Kaj nun -

467
00:18:58,480 --> 00:19:01,490
sed ni bezonas meti vin en
la unua loko tie.

468
00:19:01,490 --> 00:19:03,930
>> Kaj nun se vi povus veni ĉirkaŭe,
tiel, ni tuj

469
00:19:03,930 --> 00:19:06,300
esti en loko du.

470
00:19:06,300 --> 00:19:09,120
Kaj eĉ se tio sentas kiel ĝi estas
preni iom da tempo, kio estas agrabla nun estas

471
00:19:09,120 --> 00:19:14,710
ke la maldekstra duono de la
maldekstra duono estas nun ordo.

472
00:19:14,710 --> 00:19:18,010
Do kio estas la sekva paŝo, se ni nun
malantaŭenigi plu en la rakonto?

473
00:19:18,010 --> 00:19:18,980
>> Spektantaro: Dekstra duono.

474
00:19:18,980 --> 00:19:19,900
>> DAVID Malan: ordigi la dekstra duono.

475
00:19:19,900 --> 00:19:21,320
Do you guys devas fari tion, tiel.

476
00:19:21,320 --> 00:19:23,510
Do, se vi povus ekstari
por nur momenta?

477
00:19:23,510 --> 00:19:25,192
Kaj kio estas via nomo?

478
00:19:25,192 --> 00:19:25,540
>> Jess: Jess.

479
00:19:25,540 --> 00:19:25,870
>> DAVID Malan: Jess.

480
00:19:25,870 --> 00:19:29,720
Bone, do Jess estas nun la maldekstra
duono de la dekstra duono.

481
00:19:29,720 --> 00:19:31,400
Kaj tiel ŝi estas listo de amplekso 1.

482
00:19:31,400 --> 00:19:32,380
Ŝi evidente ordo.

483
00:19:32,380 --> 00:19:33,070
Kaj via nomo denove?

484
00:19:33,070 --> 00:19:33,630
>> Michelle: Michelle.

485
00:19:33,630 --> 00:19:35,340
>> DAVID Malan: Michelle estas evidente
listo de amplekso 1.

486
00:19:35,340 --> 00:19:36,050
Ŝi jam ordo.

487
00:19:36,050 --> 00:19:38,690
Do nun la magion okazas,
la kunfandi procezo.

488
00:19:38,690 --> 00:19:39,790
Do, kiu tuj veni antaŭe?

489
00:19:39,790 --> 00:19:41,560
Evidente Michelle.

490
00:19:41,560 --> 00:19:43,280
Do se vi povus veni ĉirkaŭ dorso.

491
00:19:43,280 --> 00:19:47,090
La spaco ni havas disponebla por ŝi nun
estas ĝuste malantaŭ tiu seĝo tie.

492
00:19:47,090 --> 00:19:51,580
Kaj nun se vi povus veni reen kiel bone,
ni nun havas, esti klara, du

493
00:19:51,580 --> 00:19:53,810
duonoj, ĉiu de amplekso 2 -

494
00:19:53,810 --> 00:19:57,090
kaj ĝuste por bildigo de sake, se vi
povus fari iom da spaco -

495
00:19:57,090 --> 00:19:59,780
tiu eliris duono tie, unu
dekstra duono tien.

496
00:19:59,780 --> 00:20:01,160
>> Malantaŭenigi plu en la rakonto.

497
00:20:01,160 --> 00:20:02,270
Kio paŝo estas poste?

498
00:20:02,270 --> 00:20:03,030
>> Spektantaro: Merge.

499
00:20:03,030 --> 00:20:04,160
>> DAVID Malan: Do nun ni devas mem kunfandi.

500
00:20:04,160 --> 00:20:07,490
Do okej, do nun, feliĉe, ni
nur liberigita ĝis kvar seĝoj.

501
00:20:07,490 --> 00:20:11,480
Do ni uzis duoble da memoro, sed
ni povas doni flip-flopping inter

502
00:20:11,480 --> 00:20:12,330
la du tabeloj.

503
00:20:12,330 --> 00:20:14,190
Do kiu nombro estas veni antauxe?

504
00:20:14,190 --> 00:20:14,850
Do Michelle, evidente.

505
00:20:14,850 --> 00:20:16,680
Do venu ĉirkaŭe kaj prenu
Via sidejo ĉi tie.

506
00:20:16,680 --> 00:20:19,120
Kaj tiam nombro 2 estas evidente
sekva, do vi venis ĉi tien.

507
00:20:19,120 --> 00:20:21,520
Numero 4, numero 6.

508
00:20:21,520 --> 00:20:23,390
Kaj denove, kvankam tie estas
iomete da marŝante implikitaj,

509
00:20:23,390 --> 00:20:26,010
vere, tiuj povus okazi tuj,
movante unu -

510
00:20:26,010 --> 00:20:26,880
Bone, bone ludis.

511
00:20:26,880 --> 00:20:28,350
>> [Ridado]

512
00:20:28,350 --> 00:20:29,680
>> DAVID Malan: Kaj nun ni estas
en sufiĉe bona formo.

513
00:20:29,680 --> 00:20:34,910
La maldekstra duono de la tuta
enigo estas nun ordo.

514
00:20:34,910 --> 00:20:37,370
Bone, do tiuj infanoj havis
la avantaĝo de mia -

515
00:20:37,370 --> 00:20:40,340
kiamaniere ĝi finos ĉiuj la knabinoj sur la
forlasis kaj ĉiuj knaboj sur la dekstra?

516
00:20:40,340 --> 00:20:42,450
>> Bone, do infanoj 'turnu nun.

517
00:20:42,450 --> 00:20:44,680
Do mi ne iros tra vi
tiuj paŝoj.

518
00:20:44,680 --> 00:20:46,550
Ni vidos se ni povas rekandidatiĝi
la sama _pseudocode_.

519
00:20:46,550 --> 00:20:50,050
Se vi volas antaŭeniri kaj levigxu,
kaj vi, knaboj, mi donos al vi la mic.

520
00:20:50,050 --> 00:20:52,990
Vidu se vi ne povas repliki kio
Ni ĵus faris tie sur la

521
00:20:52,990 --> 00:20:53,880
alia fino de la listo.

522
00:20:53,880 --> 00:20:59,530
Kiu bezonas paroli unua,
bazitaj sur la algoritmo?

523
00:20:59,530 --> 00:21:03,210
Do klarigi kion vi faras antaŭe
vi faros neniun piedo movadoj.

524
00:21:03,210 --> 00:21:05,930
>> Parolanto 1: Bone, do ekde
Mi estas la maldekstra duono de la

525
00:21:05,930 --> 00:21:07,790
maldekstra duono, mi revenos.

526
00:21:07,790 --> 00:21:08,730
Ĝuste?

527
00:21:08,730 --> 00:21:09,250
>> DAVID Malan: Bonan.

528
00:21:09,250 --> 00:21:10,350
>> Parolanto 1: Kaj tiam -

529
00:21:10,350 --> 00:21:11,800
>> DAVID Malan: Kiu faras
la mic iri al poste?

530
00:21:11,800 --> 00:21:12,920
>> Parolanto 1: Next nombro.

531
00:21:12,920 --> 00:21:14,720
>> Speaker 2: Do mi estas la dekstra duono
de la maldekstra duono de la

532
00:21:14,720 --> 00:21:17,830
maldekstra duono, kaj mi revenos.

533
00:21:17,830 --> 00:21:18,050
>> DAVID Malan: Bonan.

534
00:21:18,050 --> 00:21:18,550
Vi revenis.

535
00:21:18,550 --> 00:21:21,855
Do nun kio estas la sekva por vi du?

536
00:21:21,855 --> 00:21:23,740
>> Speaker 2: Ni volas vidi kiu estas pli malgranda.

537
00:21:23,740 --> 00:21:24,200
>> DAVID Malan: Ĝuste.

538
00:21:24,200 --> 00:21:24,940
Ni volas kunfandi.

539
00:21:24,940 --> 00:21:27,590
La spaco ni tuj uzi por kunfandi
vin en, kvankam ili estas

540
00:21:27,590 --> 00:21:30,250
evidente ordo jam, ni iras
sekvi la saman algoritmon.

541
00:21:30,250 --> 00:21:31,560
Do, kiu iras en reen unua?

542
00:21:31,560 --> 00:21:35,720
Do 3, kaj tiam 7.

543
00:21:35,720 --> 00:21:38,570
Kaj nun la mic iras
al ĉi tiuj infanoj, okej?

544
00:21:38,570 --> 00:21:43,590
>> Parolanto 3: Do mi estas la dekstra duono de la
maldekstra duono, kaj mia n estas malpli ol

545
00:21:43,590 --> 00:21:45,048
1, do mi simple tuj pasos -

546
00:21:45,048 --> 00:21:46,380
>> DAVID Malan: Bonan.

547
00:21:46,380 --> 00:21:49,450
>> Parolanto 4: Mi estas la dekstra duono de la
dekstra duono de la dekstra duono, kaj mi estas

548
00:21:49,450 --> 00:21:51,740
ankaŭ unu persono, tial mi estas
tuj revenos.

549
00:21:51,740 --> 00:21:52,990
Do nun ni kunfandi.

550
00:21:52,990 --> 00:21:55,140

551
00:21:55,140 --> 00:21:56,150
>> Parolanto 3: Do ni iru reen.

552
00:21:56,150 --> 00:21:57,160
>> DAVID Malan: Do vi iru en la dorso.

553
00:21:57,160 --> 00:21:59,200
Do 5 iras unue, tiam 8.

554
00:21:59,200 --> 00:22:01,240
Kaj nun publiko, kiu estas la
treti ni devas nun malantaŭenigi

555
00:22:01,240 --> 00:22:02,200
apogi al en niaj mensoj?

556
00:22:02,200 --> 00:22:02,940
>> Spektantaro: Merge.

557
00:22:02,940 --> 00:22:07,270
>> DAVID Malan: kunfandi maldekstra duono kaj dekstra
duono de la originala maldekstra duono.

558
00:22:07,270 --> 00:22:08,840
Do nun -

559
00:22:08,840 --> 00:22:10,520
kaj justa por fari ĉi tiu klara,
fari iom da spaco

560
00:22:10,520 --> 00:22:11,690
inter vi du infanoj.

561
00:22:11,690 --> 00:22:13,800
Do nun jen la du listoj,
maldekstra kaj dekstra.

562
00:22:13,800 --> 00:22:18,320
Nu do kiel ni nun kunfandi you guys en
la unua vico de seĝoj denove?

563
00:22:18,320 --> 00:22:19,600
>> 3 iras unue.

564
00:22:19,600 --> 00:22:20,850
Tiam 5, evidente.

565
00:22:20,850 --> 00:22:23,110

566
00:22:23,110 --> 00:22:27,330
Tiam 7, kaj nun 8.

567
00:22:27,330 --> 00:22:28,710
Bone, kaj nun ni estas?

568
00:22:28,710 --> 00:22:29,650
>> Spektantaro: Not done.

569
00:22:29,650 --> 00:22:32,440
>> DAVID Malan: Ne farita, ĉar
evidente, estas unu paŝo restanton.

570
00:22:32,440 --> 00:22:35,720
Sed denove, la kialo Mi uzas tiun
ĵargono kiel "rebobinado en via menso,"

571
00:22:35,720 --> 00:22:37,160
estas ĉar tio estas vere
kio okazis.

572
00:22:37,160 --> 00:22:39,610
Ni iras tra ĉiu el tiuj paŝoj,
sed ni estas speco de paŭzante por

573
00:22:39,610 --> 00:22:42,480
momento, plonĝado pli profunden en la
algoritmo, paŭzante dum momento,

574
00:22:42,480 --> 00:22:45,840
subnaĝado pli profunden en la algoritmo, kaj
nun ni devas ordigi de rebobinado en nia

575
00:22:45,840 --> 00:22:49,430
mensoj kaj malfari ĉiuj de ĉi tiuj tavoloj
ke ni ia en ĉesigita.

576
00:22:49,430 --> 00:22:51,790
>> Do nun ni havas du listoj de grandeco 4.

577
00:22:51,790 --> 00:22:54,790
Se vi infanoj povis ekstari lasta fojo
kaj fari iom da spaco tie por

578
00:22:54,790 --> 00:22:57,230
klarigi ke tiu estas la maldekstra
duono de la originalo, la

579
00:22:57,230 --> 00:22:58,620
dekstra duono de la originalo.

580
00:22:58,620 --> 00:23:01,060
Kiu estas la unua numero, ke ni
bezonas tiri en la malantaŭan?

581
00:23:01,060 --> 00:23:01,870
Michelle, kompreneble.

582
00:23:01,870 --> 00:23:03,230
>> Do ni metas Michelle tie.

583
00:23:03,230 --> 00:23:05,080
Kaj kiu havas numeron 2?

584
00:23:05,080 --> 00:23:06,440
Numero 2 venas sur dorson tiel.

585
00:23:06,440 --> 00:23:07,800
Numero 3?

586
00:23:07,800 --> 00:23:08,510
Bonega.

587
00:23:08,510 --> 00:23:16,570
Numero 4, numero 5, numero 6,
numero 7, kaj la numero 8.

588
00:23:16,570 --> 00:23:18,850
>> Bone, do li sentis kiel multe
de paŝoj, por certa.

589
00:23:18,850 --> 00:23:22,390
Sed nun ni vidu se ni ne povas konfirmi
speco de intuicie ke tiu

590
00:23:22,390 --> 00:23:26,190
algoritmo fundamente, aparte
n ricevas vere granda, kiel ni vidis

591
00:23:26,190 --> 00:23:29,170
kun la kuraĝigoj, estas
fundamente rapida.

592
00:23:29,170 --> 00:23:33,400
Do mi asertas tiu algoritmo, en la plej malbona
kazo kaj eĉ en la plej bona kazo,

593
00:23:33,400 --> 00:23:36,160
estas granda O de n fojoj logo n.

594
00:23:36,160 --> 00:23:39,160
Tio estas, ne estas iu aspekto de tiu
algoritmo kiu prenas n paŝoj, sed

595
00:23:39,160 --> 00:23:43,110
estas alia aspekto ie en
ke ripeta, ke looping, ke

596
00:23:43,110 --> 00:23:44,410
prenas logo n paŝoj.

597
00:23:44,410 --> 00:23:49,154
Ĉu ni povas meti nian fingron sur kio tiuj
du nombroj estas referanta al?

598
00:23:49,154 --> 00:23:51,320
Nu, kie -

599
00:23:51,320 --> 00:23:54,160
where'd la mic iras?

600
00:23:54,160 --> 00:23:58,660
>> Parolanto 1: Ĉu ensaluti n esti
rompi nin en du -

601
00:23:58,660 --> 00:23:59,630
dividanta per du, esence.

602
00:23:59,630 --> 00:24:00,120
>> DAVID Malan: Ĝuste.

603
00:24:00,120 --> 00:24:03,000
Ajna tempo ni vidas en iu ajn algoritmo tiel
nun, tie jam pasis tiun bildon de

604
00:24:03,000 --> 00:24:04,200
dividanta, dividante, dividante.

605
00:24:04,200 --> 00:24:05,700
Kaj ĝi estas tipe reduktita
al iu kiu estas

606
00:24:05,700 --> 00:24:07,100
logaritma, log bazo 2.

607
00:24:07,100 --> 00:24:10,180
Sed povus esti vere nenion,
sed ensaluti bazo 2.

608
00:24:10,180 --> 00:24:11,330
>> Nun kio pri la n?

609
00:24:11,330 --> 00:24:14,550
Mi povas vidi ke ni ia dividita vin
infanoj - dividita vi, dividita vi,

610
00:24:14,550 --> 00:24:15,910
dividita vi, dividita vi.

611
00:24:15,910 --> 00:24:18,760
Kie la fino venis?

612
00:24:18,760 --> 00:24:19,810
>> Do estas la fandado.

613
00:24:19,810 --> 00:24:20,610
Ĉar pensi pri ĝi.

614
00:24:20,610 --> 00:24:25,420
Kiam vi kunfandi ok homojn,
per kiu duono de ili estas aro de kvar

615
00:24:25,420 --> 00:24:27,770
kaj la alia duono estas alia
aro de kvar, how do you go

616
00:24:27,770 --> 00:24:28,820
pri fari la kunfandi?

617
00:24:28,820 --> 00:24:30,830
Nu, vi infanoj faris
sufiĉe intuicie.

618
00:24:30,830 --> 00:24:34,140
>> Sed se mi anstataŭ faris ĝin iom pli
metode, mi povus indik

619
00:24:34,140 --> 00:24:38,090
la plej maldekstra persono unue kun mia maldekstra
manon, indik la plej maldekstra persono

620
00:24:38,090 --> 00:24:42,080
de tiu duono kun mia dekstra mano, kaj
nur poste promenis tra la

621
00:24:42,080 --> 00:24:46,990
listo, fingromontrante la plej malgranda ero
ĉiu tempo, movante mian fingron sur kaj

622
00:24:46,990 --> 00:24:48,970
super drajvo tra la listo.

623
00:24:48,970 --> 00:24:51,890
Sed kio estas pri tiu klavo kunfandi
procezo estas mi komparante tiujn parojn

624
00:24:51,890 --> 00:24:53,460
de elementoj.

625
00:24:53,460 --> 00:24:57,270
De la dekstra duono kaj de maldekstre
duono, mi neniam unufoje backtracking.

626
00:24:57,270 --> 00:25:00,570
>> Do la merge mem prenas
ne pli ol n paŝoj.

627
00:25:00,570 --> 00:25:03,250
Kaj kiom da fojoj faris mi havas
por fari tion kunfandi?

628
00:25:03,250 --> 00:25:07,150
Nu, ne pli ol n, kaj ni simple
vidis, ke kun la fina merge.

629
00:25:07,150 --> 00:25:13,120
Kaj do se vi faras iu kiu prenas
log n paŝoj n fojoj, aŭ inverse,

630
00:25:13,120 --> 00:25:15,210
ĝi tuj donas al ni n fojoj logo n.

631
00:25:15,210 --> 00:25:16,310
>> Kaj kial estas tiu pli bona?

632
00:25:16,310 --> 00:25:19,600
Nu, se ni jam scias ke log
n estas pli bona ol n - ne?

633
00:25:19,600 --> 00:25:22,590
Ni vidis en duuma serĉo, la telefono libro
ekzemple, log n estis definitive

634
00:25:22,590 --> 00:25:23,760
pli bona ol lineara.

635
00:25:23,760 --> 00:25:28,420
Do tio signifas n fojoj log n estas
definitive pli bona ol n fojojn alian

636
00:25:28,420 --> 00:25:30,390
n, AKA n kvadratoj.

637
00:25:30,390 --> 00:25:32,400
Kaj tio kion ni fine sentas.

638
00:25:32,400 --> 00:25:34,928
>> Tiel granda ronda da aplaŭdoj, se
ni povis, por ĉi tiuj infanoj.

639
00:25:34,928 --> 00:25:38,920
>> [Aplaŭdo]

640
00:25:38,920 --> 00:25:41,550
>> DAVID Malan: Kaj via adiaŭa donacoj -
sed observu la numerojn,

641
00:25:41,550 --> 00:25:44,010
se vi ŝatus.

642
00:25:44,010 --> 00:25:45,620
Kaj via adiaŭa donaco, kiel kutime.

643
00:25:45,620 --> 00:25:47,290
Ho, kaj ni sendos al vi
la materialo, Michelle.

644
00:25:47,290 --> 00:25:48,343
Dankon.

645
00:25:48,343 --> 00:25:49,250
Ĉio bone.

646
00:25:49,250 --> 00:25:50,400
Prenu al streso pilko.

647
00:25:50,400 --> 00:25:54,110
>> Kaj lasu min eltiri supren, dume,
nia amiko Rob Bowden proponi

648
00:25:54,110 --> 00:25:59,520
tiel malsama perspektivo pri tio,
ĉar vi povas pensi pri tiuj

649
00:25:59,520 --> 00:26:01,280
paŝoj okazas en iom
malsama maniero.

650
00:26:01,280 --> 00:26:04,750
Fakte, la aro-ĉe kio Rob temas pri
por montri al ni supozas ke ni

651
00:26:04,750 --> 00:26:09,030
jam faris la dividanta supren de la
grandan liston en ok malgrandaj lertaj,

652
00:26:09,030 --> 00:26:10,570
ĉiu de amplekso 1.

653
00:26:10,570 --> 00:26:13,350
>> Do ni ŝanĝas la _pseudocode_ a
iom simple ordigi de atingi la

654
00:26:13,350 --> 00:26:15,320
kerno ideon de kiel la kunfandi verkoj.

655
00:26:15,320 --> 00:26:17,600
Sed la rula tempo de kio
li estas faronta, estas ankoraŭ

656
00:26:17,600 --> 00:26:19,110
tuj estos la sama.

657
00:26:19,110 --> 00:26:23,540
Kaj denove, la starigo de ĉi tie estas ke li estas
komencinta kun ok listoj de amplekso 1.

658
00:26:23,540 --> 00:26:27,730
Do vi maltrafis la parto kie li estas
efektive plenumis sian log n, logo n, log n

659
00:26:27,730 --> 00:26:31,205
dividante de la enigo.

660
00:26:31,205 --> 00:26:32,120
>> [VIDEO reprodukto]

661
00:26:32,120 --> 00:26:33,615
>> -Estas tio por paŝo unu.

662
00:26:33,615 --> 00:26:38,270
Por paŝo du, ree
kunfandi paroj de listoj.

663
00:26:38,270 --> 00:26:39,210
>> DAVID Malan: Hm.

664
00:26:39,210 --> 00:26:41,270
Nur sono venas
el mia komputilo.

665
00:26:41,270 --> 00:26:42,520
Ni provu ĉi denove.

666
00:26:42,520 --> 00:26:45,330

667
00:26:45,330 --> 00:26:48,310
>> -Ĝuste arbitre elekti kio -
nun ni havas kvar listoj.

668
00:26:48,310 --> 00:26:51,590

669
00:26:51,590 --> 00:26:52,120
Lernu antaŭe.

670
00:26:52,120 --> 00:26:53,040
>> DAVID Malan: Tie ni iru.

671
00:26:53,040 --> 00:27:00,510
>> -Kunfandi 108 kaj 15, ni finos
kun la listo 15, 108.

672
00:27:00,510 --> 00:27:07,170
Kunfandi 50 kaj 4, ni
finos kun 4, 50.

673
00:27:07,170 --> 00:27:12,990
Kunfandi 8 kaj 42, ni
finos kun 8, 42.

674
00:27:12,990 --> 00:27:19,970
Kaj kunfandi 23 kaj 16, ni
fini kun 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Nun ĉiuj niaj listoj de amplekso 2.

676
00:27:23,270 --> 00:27:26,690
Rimarku ke ĉiu el la
kvar listoj estas ordigitaj.

677
00:27:26,690 --> 00:27:29,450
Do ni povas starti kunfandi
paroj de lertaj denove.

678
00:27:29,450 --> 00:27:38,420
Kunfandi 15 kaj 108 kaj 4 kaj 50, ni
unue prenu la 4, tiam la 15, tiam

679
00:27:38,420 --> 00:27:41,500
la 50, tiam la 108.

680
00:27:41,500 --> 00:27:50,610
Kunfandi 8, 42 kaj 16, 23, ni unue prenas
la 8, tiam la 16an de tiam la 23,

681
00:27:50,610 --> 00:27:52,700
tiam la 42.

682
00:27:52,700 --> 00:27:57,600
>> Do nun ni havas nur du listoj de grandeco
4, ĉiu el kiuj estas ordo.

683
00:27:57,600 --> 00:28:01,170
Do nun ni kunfandi tiujn du listojn.

684
00:28:01,170 --> 00:28:11,835
Unue, ni prenu la 4, tiam ni prenos la
8, tiam ni prenos la 15, tiam 16, do

685
00:28:11,835 --> 00:28:19,456
23, poste 42, tiam 50, do 108.

686
00:28:19,456 --> 00:28:19,872
>> [FINO reprodukto de vídeo]

687
00:28:19,872 --> 00:28:23,430
>> DAVID Malan: Denove, rimarki, li neniam
tusxis donita taso pli ol unu horo

688
00:28:23,430 --> 00:28:24,860
post antaŭi preter ĝi.

689
00:28:24,860 --> 00:28:26,200
Do li neniam ripetas.

690
00:28:26,200 --> 00:28:29,850
Do li ĉiam movi al la bordo,
kaj tie estas kie ni poste ricevis nian n.

691
00:28:29,850 --> 00:28:33,290
>> Kial ne lasu min eltiri supren unu kuraĝigo
kiun ni vidis antaŭe, sed ĉi tiu tempo

692
00:28:33,290 --> 00:28:35,110
enfokusigante nur sur merge varo.

693
00:28:35,110 --> 00:28:38,030
Lasu min antaŭeniri kaj zomi
en ĉi tiu tie.

694
00:28:38,030 --> 00:28:42,530
Unue, mi elektas hazarda eniro,
altigi tiun, kaj vi povas ordigi de vidos

695
00:28:42,530 --> 00:28:46,600
kion ni prenis koncedis, pli frue,
kunfandi varo estas efektive faras.

696
00:28:46,600 --> 00:28:50,330
>> Do rimarki ke vi ricevas tiujn duonoj aŭ
tiuj kvaraj aŭ tiuj okaj de la

697
00:28:50,330 --> 00:28:53,140
problemo kiu subite
komenci preni bona formo.

698
00:28:53,140 --> 00:28:57,070
Kaj tiam finfine, vi vidos en
la fino ke bam,

699
00:28:57,070 --> 00:28:58,860
ĉiu estas kunfanditaj kune.

700
00:28:58,860 --> 00:29:01,690
>> Do tiuj estas nur tri malsamajn
prenas sur la sama ideo.

701
00:29:01,690 --> 00:29:05,980
Sed la ŝlosilo komprenon, kiel dividi
kaj venkos en la unua klaso,

702
00:29:05,980 --> 00:29:10,640
estis, ke ni decidis iel dividi
la problemo en ion grandan, en

703
00:29:10,640 --> 00:29:14,760
io ia identa en spirito,
sed pli malgranda kaj pli kaj pli malgranda

704
00:29:14,760 --> 00:29:15,660
kaj pli malgrandaj.

705
00:29:15,660 --> 00:29:18,420
>> Nun alia amuza maniero por ordigi de opinias
pri tiuj, kvankam ĝi ne estas

706
00:29:18,420 --> 00:29:20,520
tuj donos al vi la saman intuicia
kompreno, estas

707
00:29:20,520 --> 00:29:21,640
la jena kuraĝigo.

708
00:29:21,640 --> 00:29:25,400
Do tiu estas video iu kunmetita
ke asociita malsamajn

709
00:29:25,400 --> 00:29:29,970
sonoj kun la diversaj operacioj por
inserción varon, por merge varo, kaj

710
00:29:29,970 --> 00:29:31,150
por paro de la aliaj.

711
00:29:31,150 --> 00:29:32,330
Do, momente, mi tuj batis Play.

712
00:29:32,330 --> 00:29:33,600
Temas pri unu minuto longe.

713
00:29:33,600 --> 00:29:37,410
Kaj eĉ se vi ankoraŭ povas vidi la
ŝablonoj okazas, ĉi tiu tempo vi povas

714
00:29:37,410 --> 00:29:41,420
ankaŭ aŭdi kiel tiuj algoritmoj estas
agi malsame kaj kun

715
00:29:41,420 --> 00:29:43,950
tiel malsama ŝablonoj.

716
00:29:43,950 --> 00:29:45,830
>> Ĉi tiu estas inserción varo.

717
00:29:45,830 --> 00:29:50,400
>> [Tonoj ludi]

718
00:29:50,400 --> 00:29:52,400
>> DAVID Malan: ĝi estas denove provas
insertar ĉiu elemento

719
00:29:52,400 --> 00:29:52,900
en kie apartenas.

720
00:29:52,900 --> 00:29:54,628
Ĉi tiu estas bobelo varo.

721
00:29:54,628 --> 00:30:10,097
>> [Tonoj ludi]

722
00:30:10,097 --> 00:30:13,630
>> DAVID Malan: Kaj vi povas ordigi de sento
kiel relative malmulta labori ĝi estas faranta

723
00:30:13,630 --> 00:30:15,834
sur ĉiu paŝo.

724
00:30:15,834 --> 00:30:20,470
Jen kion tediousness sonas.

725
00:30:20,470 --> 00:30:21,472
>> [Tonoj ludi]

726
00:30:21,472 --> 00:30:25,222
>> DAVID Malan: Ĉi tiu estas elekto varon,
kie ni elektu la elemento ni volas per

727
00:30:25,222 --> 00:30:28,845
irante tra denove kaj denove kaj denove
kaj metante ĝin en la komenco.

728
00:30:28,845 --> 00:30:37,674
>> [Tonoj ludi]

729
00:30:37,674 --> 00:30:43,970
>> DAVID Malan: Ĉi tiu estas kunfandi varon, kiun
Vi povas vere komenci senti.

730
00:30:43,970 --> 00:30:51,810
>> [Tonoj ludi]

731
00:30:51,810 --> 00:30:54,770
>> [Ridado]

732
00:30:54,770 --> 00:30:58,395
>> DAVID Malan: Iu nomis gnomo
varon, kiun ni ne rigardis.

733
00:30:58,395 --> 00:31:13,630
>> [Tonoj ludi]

734
00:31:13,630 --> 00:31:17,910
>> DAVID Malan: Do lasu min vidi, nun,
distris kiel vi espereble estas por la

735
00:31:17,910 --> 00:31:21,110
muziko, se mi povas gliti iom
iom da matematiko en ĉi tie.

736
00:31:21,110 --> 00:31:24,850
Do tie estas kvara vojon, kiun ni povas
pensi kion signifas tiuj

737
00:31:24,850 --> 00:31:29,210
funkcioj al esti pli rapida ol aĵoj
ke ni vidis antaŭe.

738
00:31:29,210 --> 00:31:32,470
Kaj se vi venas je la kurso de
de matematiko fono, vi

739
00:31:32,470 --> 00:31:36,030
efektive scias eble jam, ke vi
povas vangofrapon termino en tiu tekniko -

740
00:31:36,030 --> 00:31:40,400
nome rekursio, funkcio
ke iel nomas sin.

741
00:31:40,400 --> 00:31:44,780
>> Kaj denove, memoru ke merge speco
_pseudocode_ estis rekursie en la senco

742
00:31:44,780 --> 00:31:48,460
ke unu el merge speco de paŝoj
estis nomi speco -

743
00:31:48,460 --> 00:31:49,740
tio estas, mem.

744
00:31:49,740 --> 00:31:52,480
Sed feliĉe, ĉar ni daŭre
nomante varon, aŭ kunfandi varon,

745
00:31:52,480 --> 00:31:55,880
specife, en pli kaj pli malgranda
kaj pli malgrandaj listo, ni fine

746
00:31:55,880 --> 00:32:00,005
fundo el danke al kio ni vokos
bazo kazo, la malmola-kodita kazo kiu

747
00:32:00,005 --> 00:32:04,270
diris se la listo estas malgranda, malpli ol 2
en tiu kazo, simple reveni tuj.

748
00:32:04,270 --> 00:32:07,550
Se ni ne havas tiun specialan kazon, la
algoritmo Neniam fundo eksteren,

749
00:32:07,550 --> 00:32:11,010
kaj vi ja eniros en la
senfinan buklon vere ĉiam.

750
00:32:11,010 --> 00:32:14,330
>> Sed supozu ke ni volis jam metis
iuj nombroj sur ĉi, denove, uzante n

751
00:32:14,330 --> 00:32:15,660
kiel la grandeco de la enigo.

752
00:32:15,660 --> 00:32:18,680
Kaj mi volis demandi vin, kio estas
la tuta tempo partoprenas en

753
00:32:18,680 --> 00:32:19,800
kurante merge speco?

754
00:32:19,800 --> 00:32:22,960
Aŭ pli ĝenerale, kio estas
la kosto de ĝi en la tempo?

755
00:32:22,960 --> 00:32:24,730
>> Nu estas sufiĉe facila por mezuri tion.

756
00:32:24,730 --> 00:32:29,010
Se n estas malpli ol 2, la tempo implikita
en ordigi n eroj,

757
00:32:29,010 --> 00:32:30,480
kie n estas 2, estas 0.

758
00:32:30,480 --> 00:32:31,410
Ĉar ni ĵus revenas.

759
00:32:31,410 --> 00:32:32,510
Ne estas laboro farenda.

760
00:32:32,510 --> 00:32:35,660
Nun eble, eble estas unu paŝo aŭ du
paŝoj por kalkuli la kvanton de

761
00:32:35,660 --> 00:32:38,420
funkcii, sed ĝi estas sufiĉe proksime al 0, ke
Mi nur volis diri sen laboro estas

762
00:32:38,420 --> 00:32:40,940
bezonata se la listo estas tiel malgrandaj
esti neinteresa.

763
00:32:40,940 --> 00:32:42,580
>> Sed ĉi tiu kazo estas interesa.

764
00:32:42,580 --> 00:32:47,320
La rekursie kazo estis la branĉo de
la _pseudocode_ kiu diris alie, speco

765
00:32:47,320 --> 00:32:52,000
la maldekstra duono, ordigi la dekstra
duono, kunfandi la du duonoj.

766
00:32:52,000 --> 00:32:55,530
Nun kial faras ĉi esprimo
reprezenti ke elspezo?

767
00:32:55,530 --> 00:32:58,690
Nu, T de n simple signifas la
tempo por ordigi n eroj.

768
00:32:58,690 --> 00:33:03,070
Kaj poste sur la dekstra flanko de la
egala signo tie, la T de n dividita

769
00:33:03,070 --> 00:33:06,600
per 2 estas referenco al la kosto de kio?

770
00:33:06,600 --> 00:33:07,570
Ordigo la maldekstra duono.

771
00:33:07,570 --> 00:33:10,990
La aliaj T de n dividita per 2 estas
supozeble raportante al la kosto

772
00:33:10,990 --> 00:33:12,390
ordigi la dekstra duono.

773
00:33:12,390 --> 00:33:14,590
>> Kaj tiam la alpago n?

774
00:33:14,590 --> 00:33:15,420
Ĉu la fandado.

775
00:33:15,420 --> 00:33:19,120
Ĉar se vi havas du listoj, unu el
amplekso n super 2 kaj alia de amplekso n

776
00:33:19,120 --> 00:33:22,580
super 2, vi devas esence tuŝi
ĉiu el tiuj elementoj, ĝuste kiel Rob

777
00:33:22,580 --> 00:33:24,990
altusxantaj unu el la kalikojn, kaj nur
kiel ni notis al ĉiu el la

778
00:33:24,990 --> 00:33:26,310
volontuloj en la scenejo.

779
00:33:26,310 --> 00:33:28,790
Do n estas la kosto de fandado.

780
00:33:28,790 --> 00:33:31,780
>> Nun bedaŭrinde, ĉi tiu formulo
Estas ankaŭ sin rekursie.

781
00:33:31,780 --> 00:33:36,390
Do se demandis la demando, se n estas, ni diru,
16, se estas 16 personoj en la scenejo

782
00:33:36,390 --> 00:33:40,670
aŭ 16 tasoj en la video, kiom entute
paŝoj faras ĝi preni por ordigi ilin

783
00:33:40,670 --> 00:33:41,550
kun merge speco?

784
00:33:41,550 --> 00:33:45,790
Ĝi fakte ne estas evidenta respondo,
ĉar nun vi devas ordigi de

785
00:33:45,790 --> 00:33:48,500
rekursie respondi tiun formulon.

786
00:33:48,500 --> 00:33:51,190
>> Sed tio estas bone, ĉar mi volas proponi
ke ni faru la sekvajn.

787
00:33:51,190 --> 00:33:56,670
La tempo implikita ordigi 16 personoj aŭ
16 tasoj tuj estos reprezentitaj

788
00:33:56,670 --> 00:33:58,020
ĝenerale kiel T de 16.

789
00:33:58,020 --> 00:34:01,400
Sed kiu egalas, laŭ nia
antaŭa formulo, 2 fojoj la kvanto

790
00:34:01,400 --> 00:34:04,780
el tempo necesa por ordigi
8 tasoj plus 16.

791
00:34:04,780 --> 00:34:08,590
Kaj denove, plus 16 estas la tempo por kunfandi,
kaj la du fojoj T de 8 estas la

792
00:34:08,590 --> 00:34:10,790
tempo por ordigi maldekstra duono kaj dekstra duono.

793
00:34:10,790 --> 00:34:11,989
>> Sed denove, tio ne estas sufiĉa.

794
00:34:11,989 --> 00:34:13,210
Ni devas mergi en pli profunda.

795
00:34:13,210 --> 00:34:16,409
Tiu signifas ke ni devas respondi al la
demando, kio estas T de la 8?

796
00:34:16,409 --> 00:34:19,610
Nu T de 8 estas nur 2
fojoj T de 4 plus 8.

797
00:34:19,610 --> 00:34:20,520
Nu, kio estas T de 4?

798
00:34:20,520 --> 00:34:23,780
T de 4 estas nur 2 fojojn T de 2 plus 4.

799
00:34:23,780 --> 00:34:25,489
Nu, kio estas T de 2?

800
00:34:25,489 --> 00:34:29,030
T de 2 estas nur 2 fojojn T de 1 plus 2.

801
00:34:29,030 --> 00:34:31,940
>> Kaj denove, ni estas speco de prenanta
fiksitaj en ĉi tiu ciklo.

802
00:34:31,940 --> 00:34:34,790
Sed temas pri bati ke
tiel nomata bazon kazo.

803
00:34:34,790 --> 00:34:37,310
Ĉar kio estas T de 1, ni asertas?

804
00:34:37,310 --> 00:34:37,810
0.

805
00:34:37,810 --> 00:34:39,730
Do nun, fine, ni povas laboro malantaŭen.

806
00:34:39,730 --> 00:34:44,290
>> Se T de 1 estas 0, mi povas nun reiru supren unu
vicigas al ĉi tiu ulo ĉi tie, kaj mi povas

807
00:34:44,290 --> 00:34:46,330
konekti 0 por T de 1.

808
00:34:46,330 --> 00:34:51,770
Do tio signifas ke ghi egalas 2 fojoj nulo,
alie sciata kiel 0, plus 2.

809
00:34:51,770 --> 00:34:53,739
Kaj por ke ĉiu esprimo estas 2.

810
00:34:53,739 --> 00:34:58,740
>> Nu, se mi prenus la T de 2, kies respondo
estas 2, ŝtopi ĝin en la mezo linio, T

811
00:34:58,740 --> 00:35:02,740
de 4, kiu donas al mi 2 fojoj
2 plus 4, do 8.

812
00:35:02,740 --> 00:35:07,080
Se do mi konektiĝas en 8 al la antaŭa
linio, kiu donas al mi 2 fojoj 8, 16.

813
00:35:07,080 --> 00:35:12,470
Kaj se ni tiam sekvas ke kun la
24, aldonante en 16, ni fine akiras

814
00:35:12,470 --> 00:35:13,820
valoro de 64.

815
00:35:13,820 --> 00:35:18,480
>> Nun kiam en kaj per si speco de lingvo
nenion por la n skribmaniero, la

816
00:35:18,480 --> 00:35:20,700
granda O, la omega ke ni
estis parolas.

817
00:35:20,700 --> 00:35:24,890
Sed ĝi rezultas ke 64 estas ja
16, la grandeco de la enigo,

818
00:35:24,890 --> 00:35:27,110
ensaluti bazo 2 de 16.

819
00:35:27,110 --> 00:35:30,200
Kaj se tiu estas iom nekonataj, same
pensas dorso, kaj ĝi revenos

820
00:35:30,200 --> 00:35:30,700
al vi fine.

821
00:35:30,700 --> 00:35:33,775
Se ĉi tiu estas log bazo 2, estas kiel 2
altigita al la kio donas al vi 16?

822
00:35:33,775 --> 00:35:36,380
Ho, tio estas 4, do estas 16 fojoj 4.

823
00:35:36,380 --> 00:35:39,380
>> Kaj denove, tio ne estas granda interkonsento se tiu
estas speco de malprecizaj memoro nun.

824
00:35:39,380 --> 00:35:43,720
Sed nuntempe, preni sur fido
ke 16 log 16 estas 64.

825
00:35:43,720 --> 00:35:46,590
Kaj tiel ja, kun tiu simpla prudento
kontroli, ni konfirmis -

826
00:35:46,590 --> 00:35:48,250
sed ne pruvis formale -

827
00:35:48,250 --> 00:35:52,800
ke la rula tempo de merge
varo estas ja n log n.

828
00:35:52,800 --> 00:35:53,790
>> Do ne estas malbona.

829
00:35:53,790 --> 00:35:57,260
Estas definitive pli bona ol la
algoritmoj ni vidis tiel multe, kaj

830
00:35:57,260 --> 00:36:00,710
estas ĉar ni leveraged, oni,
tekniko nomita rekursio.

831
00:36:00,710 --> 00:36:03,880
Sed pli interesa ol tio, ke
nocio de dividanta kaj konkerante.

832
00:36:03,880 --> 00:36:07,460
Denove, vere semajno 0 aĵoj kiuj
eĉ nun estas recurrente en

833
00:36:07,460 --> 00:36:08,740
pli konvinka maniero.

834
00:36:08,740 --> 00:36:11,750
>> Nun amuza iom ekzercon, se vi havas
neniam faris tion - kaj vi probable

835
00:36:11,750 --> 00:36:14,660
ne volis havi, ĉar ia normala
homoj ne pensas por fari tion.

836
00:36:14,660 --> 00:36:20,650
Sed se mi iras al google.com kaj se
Mi volas lerni ion pri

837
00:36:20,650 --> 00:36:22,356
rekursio, Enter.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [Ridado]

840
00:36:29,058 --> 00:36:32,030
[PLI ridado]

841
00:36:32,030 --> 00:36:33,385
DAVID Malan: Malbona ŝerco malrapide etendas.

842
00:36:33,385 --> 00:36:34,450
[Ridado]

843
00:36:34,450 --> 00:36:36,970
DAVID Malan: Ĉiaokaze, estas tie.

844
00:36:36,970 --> 00:36:38,710
Mi ne literumi ĝin erara,
kaj tie estas la ŝerco.

845
00:36:38,710 --> 00:36:40,810
Ĉio bone.

846
00:36:40,810 --> 00:36:42,950
Klarigi ĝin al la popolo apud vi, se
ĝi ne sufiĉe alklakis nur ankoraŭ.

847
00:36:42,950 --> 00:36:47,650
Sed rekursio, pli ĝenerale, referas
al la procezo de funkcio vokas

848
00:36:47,650 --> 00:36:51,430
mem, aŭ pli ĝenerale, dividante al
problemo en iu kiu povas esti

849
00:36:51,430 --> 00:36:56,220
solvita piecemeal per solvanta identa
reprezentanto problemojn.

850
00:36:56,220 --> 00:36:58,400
>> Nu, ni ŝanĝo dentaĵoj
por nur momento.

851
00:36:58,400 --> 00:37:00,840
Ni ŝatas fini sur certa cliffhangers,
do ni komencu meti

852
00:37:00,840 --> 00:37:05,870
la etapo, dum kelkaj minutoj,
sur tre simpla ideo -

853
00:37:05,870 --> 00:37:07,620
tiu de swapping du elementoj, ĉu ne?

854
00:37:07,620 --> 00:37:10,040
Ĉiuj de ĉi tiuj algoritmoj ni vizitis
parolas pri la pasintaj kelkaj

855
00:37:10,040 --> 00:37:12,420
prelegoj engaĝi kelkajn
speco de swapping.

856
00:37:12,420 --> 00:37:14,630
Hodiaŭ ĝi imagis per ili atingi
el iliaj seĝoj kaj

857
00:37:14,630 --> 00:37:18,570
marsxante, sed en kodo, ni volus
nur prenu ero de unu aro

858
00:37:18,570 --> 00:37:20,370
kaj Plop ĝin en alian.

859
00:37:20,370 --> 00:37:21,880
>> Nu do kiel ni irad faras tion?

860
00:37:21,880 --> 00:37:24,850
Nu, lasu min antaŭeniri kaj skribi
rapida programo tie.

861
00:37:24,850 --> 00:37:31,600
Mi tuj iros antaŭen kaj fari
tion kiel la sekvajn.

862
00:37:31,600 --> 00:37:33,910
Ni nomas tion -

863
00:37:33,910 --> 00:37:38,070
kion ni volas nomi ĉi tiu?

864
00:37:38,070 --> 00:37:38,650
>> Efektive, ne.

865
00:37:38,650 --> 00:37:39,420
Lasu min malantaŭenigi.

866
00:37:39,420 --> 00:37:41,220
Mi ne volas fari tion
cliffhanger ankoraŭ.

867
00:37:41,220 --> 00:37:42,270
Ĝi difektas la amuzo.

868
00:37:42,270 --> 00:37:43,600
Ni faras ĉi anstataŭe.

869
00:37:43,600 --> 00:37:47,430
>> Supozu, ke mi volas skribi iomete
programo kaj kiu nun ampleksas ĉi

870
00:37:47,430 --> 00:37:48,700
ideo de rekursio.

871
00:37:48,700 --> 00:37:50,370
Mi specon de atingis antaŭ min tie.

872
00:37:50,370 --> 00:37:51,420
Mi tuj faros la sekvajn.

873
00:37:51,420 --> 00:38:00,220
>> Unue, rapida inkludas de normo io.h,
tiel kiel inkluzivas de cs50.h.

874
00:38:00,220 --> 00:38:03,200
Kaj poste mi iros por antaŭeniri
kaj deklari int main void

875
00:38:03,200 --> 00:38:04,360
en la kutima maniero.

876
00:38:04,360 --> 00:38:07,920
Mi rimarkis mi misnamed la dosieron, do
lasu min nur aldoni. c etendo tie tiel

877
00:38:07,920 --> 00:38:09,510
ke ni povas kompili ĝin ĝuste.

878
00:38:09,510 --> 00:38:10,970
Start tiu funkcio malproksime.

879
00:38:10,970 --> 00:38:13,290
>> Kaj la funkcio mi volas skribi, sufiĉe
simple, unu, kiu petas la

880
00:38:13,290 --> 00:38:16,210
uzanton por nombro kaj poste aldonas supren
ĉiuj numeroj inter tiu

881
00:38:16,210 --> 00:38:19,920
numeron kaj, ni diru, 0.

882
00:38:19,920 --> 00:38:22,510
Do unue mi tuj iros antaŭen
kaj deklari int n.

883
00:38:22,510 --> 00:38:24,760
Tiam mi kopii iujn kodo kiu
ni uzis por tempo.

884
00:38:24,760 --> 00:38:26,660
Dum io estas vera.

885
00:38:26,660 --> 00:38:28,000
Mi revenos al tio en momento.

886
00:38:28,000 --> 00:38:29,010
>> Kion mi volas fari?

887
00:38:29,010 --> 00:38:33,460
Mi volas diri printf pozitiva
entjero bonvolu.

888
00:38:33,460 --> 00:38:36,130
Kaj poste mi iros al
diru n gets akiri int.

889
00:38:36,130 --> 00:38:38,800
Do denove, iuj Boilerplate kodo
ke ni uzis antaŭe.

890
00:38:38,800 --> 00:38:40,810
Kaj mi faros tiun
dum n estas malpli ol 1.

891
00:38:40,810 --> 00:38:44,120
Do tio certigos ke la uzanto
donas al mi pozitiva entjero.

892
00:38:44,120 --> 00:38:45,490
>> Kaj nun mi faros la sekvajn.

893
00:38:45,490 --> 00:38:51,020
Mi volas aldoni la tutan de la nombroj
inter 1 kaj kaj n, aŭ 0 kaj n,

894
00:38:51,020 --> 00:38:52,570
ekvivalente, por akiri la tuta sumo.

895
00:38:52,570 --> 00:38:55,100
Do la granda sigma simbolo
ke vi eble memoras.

896
00:38:55,100 --> 00:38:59,050
Do mi tuj faros tion per la unua voko
funkcio nomita sigma,

897
00:38:59,050 --> 00:39:06,030
pasante ĝin en n, kaj do mi tuj
diru printf, la respondo estas prava.

898
00:39:06,030 --> 00:39:08,180
>> Do, en mallonga, mi alvenas kaj
int de la uzanto.

899
00:39:08,180 --> 00:39:09,280
Mi certigas ĝi estas pozitiva.

900
00:39:09,280 --> 00:39:12,700
Mi deklaras variablon nomata respondon de
tipo int kaj vendejo en tio la reveno

901
00:39:12,700 --> 00:39:15,610
valoro de sigmo, pasante en n kiel enigo.

902
00:39:15,610 --> 00:39:17,060
Kaj tiam mi elprinti tiun respondon.

903
00:39:17,060 --> 00:39:19,550
>> Bedaŭrinde, kvankam sigma sonas
kiel iu kiu povus esti en

904
00:39:19,550 --> 00:39:24,040
la math.h dosieron, ĝia deklaro,
fakte ne estas.

905
00:39:24,040 --> 00:39:24,690
Por ke estas bone.

906
00:39:24,690 --> 00:39:26,170
Mi povas apliki ĉi mi mem.

907
00:39:26,170 --> 00:39:29,160
Mi tuj apliki funkcio nomata
sigma, kaj gxi tuj preni

908
00:39:29,160 --> 00:39:29,900
parametro -

909
00:39:29,900 --> 00:39:32,100
ni simple nomas ĝin m, nur
tial estas malsama.

910
00:39:32,100 --> 00:39:35,910
Kaj tiam ĉi tien, mi tuj diros,
bone, se m estas malpli ol 1 - tio estas

911
00:39:35,910 --> 00:39:38,180
tre seninteresa programo.

912
00:39:38,180 --> 00:39:41,700
Do mi tuj iros antaŭen kaj
tuj revenos 0.

913
00:39:41,700 --> 00:39:45,920
Ĝi simple ne havas sencon por aldoni ĉiujn
la numeroj inter 1 kaj m se m

914
00:39:45,920 --> 00:39:48,470
estas sin 0 aŭ negativa.

915
00:39:48,470 --> 00:39:50,900
>> Kaj poste mi iros por antaŭeniri
kaj faros cxi tre ripete.

916
00:39:50,900 --> 00:39:53,090
Mi tuj faros ĉi speco de malnova lernejo,
kaj mi tuj iros antaŭen

917
00:39:53,090 --> 00:39:57,150
kaj diru, ke mi tuj
deklari sumo al esti 0.

918
00:39:57,150 --> 00:39:59,630
Tiam mi tuj devos
a por buklo de int -

919
00:39:59,630 --> 00:40:02,820
kaj lasu min fari tion por kongrui nia
dissendo kodo, do vi havas kopion

920
00:40:02,820 --> 00:40:07,500
hejme. int i ricevas 1 sur ĝis
i estas malpli ol aŭ egala al m.

921
00:40:07,500 --> 00:40:09,430
i plus plus.

922
00:40:09,430 --> 00:40:11,430
Kaj poste ene de ĉi por buklo -

923
00:40:11,430 --> 00:40:12,440
ni estas preskaŭ tie -

924
00:40:12,440 --> 00:40:15,810
sumo atingas sumon plus 1.

925
00:40:15,810 --> 00:40:17,670
Kaj poste mi iros por reveni la sumon.

926
00:40:17,670 --> 00:40:19,420
>> Do mi faris tion rapide,
sufiĉe Certe.

927
00:40:19,420 --> 00:40:22,775
Sed denove, la ĉefa funkcio estas sufiĉe
simpla, bazita sur kodo Ni

928
00:40:22,775 --> 00:40:23,190
skribita tiel nun.

929
00:40:23,190 --> 00:40:25,610
Uzas la duobla banto akiri pozitivajn
int de la uzanto.

930
00:40:25,610 --> 00:40:29,870
Mi tiam preterpasonta int al nova funkcio
vokis sigma, nomante ĝin, denove, n.

931
00:40:29,870 --> 00:40:33,100
Kaj mi stoki la reveno valoro, la respondo
el la nigra skatolo aktuale

932
00:40:33,100 --> 00:40:35,460
konata kiel sigma, en variablo
vokis respondo.

933
00:40:35,460 --> 00:40:36,580
Tiam mi presi ĝin.

934
00:40:36,580 --> 00:40:39,090
>> Se ni nun sekvos la historio,
kiele sigma implementado?

935
00:40:39,090 --> 00:40:40,840
Mi proponas apliki jene.

936
00:40:40,840 --> 00:40:43,560
Unue, iom de eraro-kontrolanta
por certigi ke la uzanto ne

937
00:40:43,560 --> 00:40:46,480
rompado kun mi kaj pasante en
iuj negativaj aŭ 0 valoro.

938
00:40:46,480 --> 00:40:49,710
Tiam mi deklaras variablon nomata
Resume kaj starigis gxin al 0.

939
00:40:49,710 --> 00:40:55,910
>> Kaj nun mi komencas movi de i egalas
1 la tuta vojo ĝis kaj inkluzive de m,

940
00:40:55,910 --> 00:41:00,130
ĉar mi volas inkludi ĉiujn
nombroj de unu tra m, inkluziva.

941
00:41:00,130 --> 00:41:04,350
Kaj ene de ĉi por ciklo, mi simple fari
sumo atingas ĉion, kio estas nun, plus la

942
00:41:04,350 --> 00:41:08,900
valoro de i.

943
00:41:08,900 --> 00:41:10,370
Plus la valoro de i.

944
00:41:10,370 --> 00:41:14,090
>> Kiel flanken, se vi ne vidis tiun
antaŭe, tie estas kelkaj sintaksaj sukero

945
00:41:14,090 --> 00:41:14,870
por ĉi tiu linio.

946
00:41:14,870 --> 00:41:21,120
Mi povas reverki ĉi tiu kiel pli egalas i,
nur por savi min kelkaj klavoj

947
00:41:21,120 --> 00:41:22,570
kaj serĉi iom pli freŝa.

948
00:41:22,570 --> 00:41:23,140
Sed tio estas ĉio.

949
00:41:23,140 --> 00:41:24,660
Ĝi estas funkcie la sama aĵo.

950
00:41:24,660 --> 00:41:26,710
>> Bedaŭrinde, ĉi tiu kodo estas
ne tuj kompili ankoraŭ.

951
00:41:26,710 --> 00:41:31,600
Se mi kuras fari sigma 0, kiel estas
Mi tuj get kriis al?

952
00:41:31,600 --> 00:41:33,473
Kio ĝi tuj ne plaĉas?

953
00:41:33,473 --> 00:41:35,740
>> Spektantaro: [inaudibles].

954
00:41:35,740 --> 00:41:37,800
>> DAVID Malan: Jes, mi ne deklaris
la funkcio ĝis supro, ĉu ne?

955
00:41:37,800 --> 00:41:40,590
C estas speco de stulta, en kiu nur
faras kion vi diros ĝin fari, kaj vi

956
00:41:40,590 --> 00:41:41,880
devas fari gxin en tiu ordo.

957
00:41:41,880 --> 00:41:45,910
Kaj tial, se mi batis Indiku ĉi tie, mi tuj
ricevas averton pri sigma implicitan

958
00:41:45,910 --> 00:41:46,860
deklaro.

959
00:41:46,860 --> 00:41:48,120
>> Ho, ne estas problemo.

960
00:41:48,120 --> 00:41:50,370
Mi povas iri sur la supron, kaj mi povas
diri, gravas, atendu momenton.

961
00:41:50,370 --> 00:41:54,240
Sigma estas funkcio kiu revenas
an int kaj atendas de

962
00:41:54,240 --> 00:41:56,620
int kiel enigo, punktokomo.

963
00:41:56,620 --> 00:41:59,550
Aux mi povus meti la tuta funkcio
supre ĉefa, sed en ĝenerala, mi dirus

964
00:41:59,550 --> 00:42:02,260
rekomendas kontraŭ tio, ĉar ĝi estas
nice ĉiam havi ĉefan ĉe la supro tiel

965
00:42:02,260 --> 00:42:06,310
vi povas plonĝi juste kaj scias kia
programo estas faranta per legado ĉefa unua.

966
00:42:06,310 --> 00:42:07,930
>> Do nun lasu min liberigi la ekrano.

967
00:42:07,930 --> 00:42:09,330
Refari sigma 0.

968
00:42:09,330 --> 00:42:10,340
Ĉio ŝajnas ekiri.

969
00:42:10,340 --> 00:42:11,970
Permesu al mi kuri sigma 0.

970
00:42:11,970 --> 00:42:12,770
Pozitivaj intermilita.

971
00:42:12,770 --> 00:42:15,580
Mi donos al gxi la nombron
3 teni ĝin simpla.

972
00:42:15,580 --> 00:42:18,710
Por ke oni donu al mi 3
plus 2 plus 1, do 6.

973
00:42:18,710 --> 00:42:20,750
Enter, kaj ja mi ricevas 6.

974
00:42:20,750 --> 00:42:21,820
>> Mi povas fari ion pli granda -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Ĝuste kiel tangento, mi faros
io ridinda kiel vere granda

977
00:42:27,690 --> 00:42:30,375
nombro, Ho, kiu fakte prilaborita -

978
00:42:30,375 --> 00:42:31,600
eh, mi ne kredas ke tio estas prava.

979
00:42:31,600 --> 00:42:32,810
Ni vidu.

980
00:42:32,810 --> 00:42:34,060
Ni vere metas kun ĝi.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> Tio estas problemo.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
Kio okazas?

985
00:42:44,970 --> 00:42:46,050
La kodo ne estas tiel malbona.

986
00:42:46,050 --> 00:42:48,470
Ĝi estas ankoraŭ lineara.

987
00:42:48,470 --> 00:42:50,810
Fajfante estas bona efekto, tamen.

988
00:42:50,810 --> 00:42:52,060
Kio okazas?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> Ne certas se mi aŭdis.

991
00:42:55,620 --> 00:42:57,620
Do rezultas - kaj
ĉi tiu estas kiel flanken.

992
00:42:57,620 --> 00:42:59,400
Ĉi tio ne estas kerna al la
ideo de rekursio.

993
00:42:59,400 --> 00:43:02,480
Rezultas, ĉar mi klopodas
reprezenti tia granda nombro, plej

994
00:43:02,480 --> 00:43:06,980
verŝajne ĝi estos esti misinterpretita
per C kiel ne pozitiva nombro,

995
00:43:06,980 --> 00:43:09,980
sed negativa nombro.

996
00:43:09,980 --> 00:43:12,690
>> Ni ne parolis pri tio, sed
rezultas tie estas negativaj nombroj

997
00:43:12,690 --> 00:43:14,210
en la mondo krom
por pozitivaj nombroj.

998
00:43:14,210 --> 00:43:16,290
Kaj la rimedoj, per kiuj vi povas
reprezentas negativan numeron

999
00:43:16,290 --> 00:43:19,530
esence, vi uzas unu
speciala bito por indiki

1000
00:43:19,530 --> 00:43:20,400
pozitiva ol negativa.

1001
00:43:20,400 --> 00:43:22,950
Ĝi estas iom pli kompleksa ol tio,
sed tio estas la baza ideo.

1002
00:43:22,950 --> 00:43:26,740
>> Do, bedaŭrinde, se C estas malklara oni
de tiuj bitoj kiel fakte signifas,

1003
00:43:26,740 --> 00:43:30,790
oh, tio estas negativa nombro, mia buklo
ĉi tie, ekzemple, estas fakte neniam

1004
00:43:30,790 --> 00:43:31,740
tuj finiĝi.

1005
00:43:31,740 --> 00:43:33,850
Do, se mi efektive presi ion
denove kaj denove, ni volus

1006
00:43:33,850 --> 00:43:34,650
vidi tutan sorton.

1007
00:43:34,650 --> 00:43:36,220
Sed denove, tio estas krom la punkto.

1008
00:43:36,220 --> 00:43:38,590
Tio estas vere nur ia
intelekta scivolo, ke ni venos

1009
00:43:38,590 --> 00:43:39,550
apogi al fine.

1010
00:43:39,550 --> 00:43:43,400
Sed nuntempe, ĉi tiu estas korekta
efektivigo se ni supozas ke la

1011
00:43:43,400 --> 00:43:45,970
uzanto provizos ints
kiu persvadas ene ints.

1012
00:43:45,970 --> 00:43:49,370
>> Sed mi asertas ke tiu kodo, sincere,
povus fari tiel multe pli simple.

1013
00:43:49,370 --> 00:43:54,060
Se la celo en mano estas preni nombro
kiel m kaj adicii ĉiujn

1014
00:43:54,060 --> 00:43:59,510
nombroj inter ĝi kaj 1, aŭ inverse
inter 1 kaj ĝi, mi asertas

1015
00:43:59,510 --> 00:44:03,380
ke mi povas pruntepreni tiun ideon kiu kunfandi
speco havis, kion prenis problemo

1016
00:44:03,380 --> 00:44:05,660
de tiu grandeco kaj dividante ĝin
en iu pli malgranda.

1017
00:44:05,660 --> 00:44:09,875
Eble ne duono, sed pli malgranda, sed
representatively la sama.

1018
00:44:09,875 --> 00:44:12,130
Sama ideo, sed plej malgranda problemo.

1019
00:44:12,130 --> 00:44:15,470
>> Do mi fakte - lasu min konservi tiun dosieron
kun malsama versio numeron.

1020
00:44:15,470 --> 00:44:17,670
Ni nomas tiun versio
1 anstataŭ 0.

1021
00:44:17,670 --> 00:44:20,790
Kaj mi asertas ke mi povas reale
reimplement tion en ĉi tia

1022
00:44:20,790 --> 00:44:22,160
menso-fleksante vojo.

1023
00:44:22,160 --> 00:44:23,710
>> Mi tuj forlasi parton de ĝi nur.

1024
00:44:23,710 --> 00:44:27,710
Mi intencis diri, se m estas malpli
ol aŭ eĉ egala al 0 -

1025
00:44:27,710 --> 00:44:29,280
Mi simple tuj estos iom
pli anal ĉi tiu tempo

1026
00:44:29,280 --> 00:44:30,520
kun mia eraro kontrolanta -

1027
00:44:30,520 --> 00:44:33,190
Mi tuj iros antaŭen kaj reveni 0.

1028
00:44:33,190 --> 00:44:34,490
Ĉi tio estas arbitra.

1029
00:44:34,490 --> 00:44:37,500
Mi nur simple decidi se la uzanto
donas al mi negativa nombro, mi estas

1030
00:44:37,500 --> 00:44:41,490
reveni 0, kaj ili devas esti legita
la dokumentado pli atente.

1031
00:44:41,490 --> 00:44:42,170
>> Else -

1032
00:44:42,170 --> 00:44:44,070
rimarki kion mi faros.

1033
00:44:44,070 --> 00:44:49,260
Alie, mi tuj revenos m pli -

1034
00:44:49,260 --> 00:44:51,010
kio estas sigma de m?

1035
00:44:51,010 --> 00:44:56,710
Nu, sigma de m plus m minus 1,
krom m minus 2, plus m minus 3.

1036
00:44:56,710 --> 00:44:58,030
Mi ne volas skribi ĉiujn kiuj ekstere.

1037
00:44:58,030 --> 00:44:59,120
Kial ne Mi nur liberigas?

1038
00:44:59,120 --> 00:45:05,080
Rekursie voki min kun iomete
plej malgranda problemo, punktokomo,

1039
00:45:05,080 --> 00:45:06,840
kaj voku gxin tago?

1040
00:45:06,840 --> 00:45:07,040
>> Ĝuste?

1041
00:45:07,040 --> 00:45:10,980
Nun ĉi tie ankaŭ vi povus senti aŭ maltrankviligi
ke tio estas malfinia buklo kiun mi

1042
00:45:10,980 --> 00:45:15,450
indukti, per kiu mi estas apliko
sigma per voko sigmo.

1043
00:45:15,450 --> 00:45:20,342
Sed tio estas perfekte OK, ĉar mi
pensis antaŭen aldonita kies linioj?

1044
00:45:20,342 --> 00:45:22,600
>> Spektantaro: [inaudibles].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID Malan: 23 al 26, kio
estas mia se kondiĉo.

1046
00:45:25,430 --> 00:45:28,390
Ĉar kio estas bela pri la
subtraho tie, ĉar mi konservos

1047
00:45:28,390 --> 00:45:31,180
disdonado sigma malgrandaj problemoj, pli malgranda
problemoj, pli malgranda - ĝi ne estas

1048
00:45:31,180 --> 00:45:31,870
duonon de la grandeco.

1049
00:45:31,870 --> 00:45:34,380
Tio estas nur bebo paŝon pli malgranda,
sed tio ne gravas.

1050
00:45:34,380 --> 00:45:38,050
Ĉar fine, ni laboros
nia vojo suben al 1 aŭ 0.

1051
00:45:38,050 --> 00:45:41,630
Kaj unufoje ni batis 0, sigma ne
tuj nomos sin plu.

1052
00:45:41,630 --> 00:45:43,590
Ĝi tuj tuj revenos 0.

1053
00:45:43,590 --> 00:45:47,960
>> Do la efikon, se vi ia vento ĉi
en via menso, estas aldoni m pli

1054
00:45:47,960 --> 00:45:52,740
m minus 1, plus m minus 2, plus m minus
3, plus dot, punkto, ĝi pentras, m minus

1055
00:45:52,740 --> 00:45:57,820
m, fine transdonante vin 0, kaj la
efekto estas finfine aldoni ĉiuj

1056
00:45:57,820 --> 00:45:59,070
tion kune.

1057
00:45:59,070 --> 00:46:02,380
Do ni ne havas, per rekursio,
solvis la problemon, ke ni

1058
00:46:02,380 --> 00:46:03,470
ne povis solvi antaŭe.

1059
00:46:03,470 --> 00:46:06,840
Ja, versio 0 de tiu, kaj ĉiu
problemo ĝis nun, estis solvebla

1060
00:46:06,840 --> 00:46:09,980
kun nur uzante por maŝojn aŭ dum
maŝojn aŭ similaj konstruoj.

1061
00:46:09,980 --> 00:46:13,150
>> Sed rekursio, mi daresay, donas al ni
malsama maniero de pensi

1062
00:46:13,150 --> 00:46:17,010
problemoj, per kiu, se ni povas preni
problemo, dividi ĝin el io

1063
00:46:17,010 --> 00:46:22,340
iom grandaj en iu iomete
malgranda, mi asertas, ke ni povas solvi ĝin

1064
00:46:22,340 --> 00:46:26,040
eble iom pli elegante en terminoj
de la dezajno, kun malpli da kodo,

1065
00:46:26,040 --> 00:46:30,980
kaj eble eĉ solvi problemojn kiuj volus
esti pli forta, kiel ni instruos vin eventuale

1066
00:46:30,980 --> 00:46:33,280
vidu, solvante pure ripete.

1067
00:46:33,280 --> 00:46:35,980
>> Sed la cliffhanger kiun mi faris
volas forlasi nin, estis jena.

1068
00:46:35,980 --> 00:46:40,720
Lasu min antaŭeniri kaj malfermi
supren dosiero de -

1069
00:46:40,720 --> 00:46:44,300
fakte, lasu min iri
fari ĉi reala rapida.

1070
00:46:44,300 --> 00:46:46,875
Lasu min kaj proponi
la jena.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Inter la hodiaŭa kodo estas ĉi dosieron ĉi tie.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Ĉi tiu tie, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Do tiu estas stulta iom programo kiu
Mi ekfrapis ke asertoj fari

1076
00:47:06,260 --> 00:47:06,940
la jena.

1077
00:47:06,940 --> 00:47:10,140
En ĉefa, ĝi unue deklaras
int nomata x kaj asignas ĝin

1078
00:47:10,140 --> 00:47:11,100
la valoron de 1.

1079
00:47:11,100 --> 00:47:13,520
Tiam ĝi deklaras int y kaj
asignas al ĝi la valoro 2.

1080
00:47:13,520 --> 00:47:15,310
Tiam ĝi presas kion x kaj y estas.

1081
00:47:15,310 --> 00:47:17,781
Tiam ĝi diras: swapping, dot dot dot.

1082
00:47:17,781 --> 00:47:21,670
>> Tiam ĝi diras esti nomante funkcio
vokis swap, pasante en x kaj

1083
00:47:21,670 --> 00:47:24,290
y, la ideo de kiu estas kiu espereble
x kaj y revenos

1084
00:47:24,290 --> 00:47:25,620
malsama, la malo.

1085
00:47:25,620 --> 00:47:27,110
Tiam ĝi asertas interŝanĝis!

1086
00:47:27,110 --> 00:47:28,420
kun krio punkto.

1087
00:47:28,420 --> 00:47:30,190
Tiam ĝi presas el x kaj y.

1088
00:47:30,190 --> 00:47:33,480
>> Sed ĝi rezultas ke tiu tre
simpla pruvo malsupren

1089
00:47:33,480 --> 00:47:35,570
ĉi tie estas reale kalesxo.

1090
00:47:35,570 --> 00:47:38,870
Eĉ se mi deklarante portempan
ŝanĝiĝema kaj provizore meti en

1091
00:47:38,870 --> 00:47:42,010
ĝi, tiam mi reassigning
de la valoro de b -

1092
00:47:42,010 --> 00:47:45,080
kiuj sentas racia, ĉar mi havas
savis kopion de en temp.

1093
00:47:45,080 --> 00:47:48,410
Tiam mi ĝisdatigos b al egala
kiom estis en temp.

1094
00:47:48,410 --> 00:47:51,610
Ĉi tiu speco de konko ludo de movi
en b kaj b en uzante tiun

1095
00:47:51,610 --> 00:47:54,360
meza viro nomata temp sentas
perfekte racia.

1096
00:47:54,360 --> 00:47:57,270
>> Sed mi asertas, ke kiam mi kuros ĉi
kodo, kiel mi faros nun -

1097
00:47:57,270 --> 00:47:59,490
lasu min iri antaŭen kaj gluu ĝin en ĉi tie.

1098
00:47:59,490 --> 00:48:01,995
Mi nomas tiun noswap.c.

1099
00:48:01,995 --> 00:48:05,630
Kaj kiel la nomo sugestas, ĉi tio ne estas
tuj estos korekta programo.

1100
00:48:05,630 --> 00:48:09,460
Faru noswap. / Ne interŝanĝa.

1101
00:48:09,460 --> 00:48:12,110
x estas 1, y estas 2, swapping, interŝanĝitaj.

1102
00:48:12,110 --> 00:48:14,220
x estas 1, y estas 2.

1103
00:48:14,220 --> 00:48:16,920
Ĉi tiu estas fundamente malĝusta, eĉ
Kvankam tio ŝajnas perfekte

1104
00:48:16,920 --> 00:48:17,730
racie mi.

1105
00:48:17,730 --> 00:48:21,330
Kaj estas kialo, sed ni ne estas
tuj malkaŝus la kialo ĝuste ankoraŭ.

1106
00:48:21,330 --> 00:48:24,610
>> Ĉar nun la dua cliffhanger Mi volis
lasi vin estas ĉi tiu,

1107
00:48:24,610 --> 00:48:27,120
anonco de varoj en kupono kodoj.

1108
00:48:27,120 --> 00:48:31,590
Nia novigo kun malfrua tagoj ĉi tiu jaro
provokis ne-bagatela nombro

1109
00:48:31,590 --> 00:48:33,830
de demandoj, kiuj estis
ne estas nia intenco.

1110
00:48:33,830 --> 00:48:36,590
La intenco de ĉi tiuj kupono kodoj,
per kio, se vi faras parto de la problemo

1111
00:48:36,590 --> 00:48:39,850
starigis frue, tiel atingante ekstran tagon,
estis vere helpi vin infanoj helpi

1112
00:48:39,850 --> 00:48:42,420
vi komencos frue, speco
de de incentivizing vi.

1113
00:48:42,420 --> 00:48:44,880
Helpas nin disdoni ŝarĝo trans
oficejo horoj pli bone por ke

1114
00:48:44,880 --> 00:48:45,740
ĝi estas speco de gajni-gajni.

1115
00:48:45,740 --> 00:48:48,860
>> Bedaŭrinde, mi kredas miaj instrukcioj
ne restis, ĝis nun, tre klara, tiel

1116
00:48:48,860 --> 00:48:52,230
Mi reiris ĉi semajnfino kaj ĝisdatigita
la spec en pli granda, revenante pli aŭdacaj teksto

1117
00:48:52,230 --> 00:48:53,600
ekspliki kuglojn kiel tiuj.

1118
00:48:53,600 --> 00:48:56,900
Kaj ĝuste diri ĝin pli publike, por
Implicite, problemo aroj estas pro ĵaŭdo

1119
00:48:56,900 --> 00:48:58,400
tagmeze, por la Syllabus.

1120
00:48:58,400 --> 00:49:02,030
Se vi komencas frue, finante parto de
la problemo starigis merkredo je 12:00

1121
00:49:02,030 --> 00:49:05,170
GMT, la parto kiu rilatas al kupono
kodo, la ideo estas ke vi povas etendi

1122
00:49:05,170 --> 00:49:07,710
via limdato por la
P starigis ĝis vendredo.

1123
00:49:07,710 --> 00:49:10,890
Tio estas, iom for eta parto de la P
starigis parenco al kio tipe estas la

1124
00:49:10,890 --> 00:49:13,200
granda problemo, kaj vi aĉetos
mem ekstran tagon.

1125
00:49:13,200 --> 00:49:15,190
Denove, ĝi ricevas vi pensas pri
la problemo aro, prenas vin al

1126
00:49:15,190 --> 00:49:16,380
oficejo horojn pli frue.

1127
00:49:16,380 --> 00:49:20,670
Sed la kupono kodo problemo estas ankoraŭ
bezonata, eĉ se vi ne submeti ĝin.

1128
00:49:20,670 --> 00:49:23,340
>> Sed pli compellingly estas tiu.

1129
00:49:23,340 --> 00:49:26,520
(STADIO flustre) Kaj tiuj uloj lasante
Komence estas gonna bedaŭros.

1130
00:49:26,520 --> 00:49:28,620
Kiel estas la homoj sur la balkono.

1131
00:49:28,620 --> 00:49:32,510
Mi pardonpetas anticipe al la homoj sur
la balkono de kialoj kiuj estos

1132
00:49:32,510 --> 00:49:33,920
certe en nur momento.

1133
00:49:33,920 --> 00:49:37,050
>> Do ni estas feliĉa havi unu el
CS50 la eksĉefo instruado uloj ĉe

1134
00:49:37,050 --> 00:49:39,302
kompanio nomita dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
Ili tre malavare donacis
kupono kodo tie ĉi multe spaco,

1136
00:49:45,500 --> 00:49:48,180
kiu estas el la
kutima 2 gigabajtoj.

1137
00:49:48,180 --> 00:49:51,740
Do kion mi pensis ke ni farus en tiu
fina noto estas fari iom de evidenta sinmalkaŝo,

1138
00:49:51,740 --> 00:49:55,380
per kiu en nur momente, ni malkaŝos
la gajnanto kaj kiu havas kupono

1139
00:49:55,380 --> 00:49:57,980
kodo kiun vi povas tiam iru al sia
TTT-ejo, tajpu ĝin en, kaj voilà, ricevi

1140
00:49:57,980 --> 00:50:01,370
tuta multe pli Dropbox spaco por via
aparato kaj pro viaj personaj dosieroj.

1141
00:50:01,370 --> 00:50:05,690
>> Kaj la unua, kiu ŝatus partopreni
en ĉi desegnon?

1142
00:50:05,690 --> 00:50:09,630
OK, nun ke faras ankoraŭ pli amuza.

1143
00:50:09,630 --> 00:50:14,010
La persono, kiu ricevas tiun 25-gigabajto
kupono kodo - kiu estas malproksime

1144
00:50:14,010 --> 00:50:16,150
pli konvinka ol la malfrua
tagoj nun, eble -

1145
00:50:16,150 --> 00:50:20,620
estas tiu, kiu sidas sur supro de
sidejo kuseno sub kiuj estas

1146
00:50:20,620 --> 00:50:21,620
ke kupono kodo.

1147
00:50:21,620 --> 00:50:23,480
Vi povas nun rigardi sube
Via sidejo kuseno.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [VIDEO reprodukto]

1150
00:50:29,680 --> 00:50:31,620
>> -Unu, du, tri.

1151
00:50:31,620 --> 00:50:35,015
>> [Screaming]

1152
00:50:35,015 --> 00:50:35,985
>> -Vi ricevas aŭton!

1153
00:50:35,985 --> 00:50:36,670
Vi ricevas aŭton!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID Malan: Ni vidos
vi merkredon.

1155
00:50:37,970 --> 00:50:38,904
>> -Vi ricevas aŭton!

1156
00:50:38,904 --> 00:50:39,371
Vi ricevas aŭton!

1157
00:50:39,371 --> 00:50:40,305
Vi ricevas aŭton!

1158
00:50:40,305 --> 00:50:41,706
Vi ricevas aŭton!

1159
00:50:41,706 --> 00:50:43,107
Vi ricevas aŭton!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID Malan: Balkono ulojn, venu
cxi tie ĉe la fronto,

1161
00:50:45,530 --> 00:50:46,866
kie ni havas ekstraj.

1162
00:50:46,866 --> 00:50:50,282
>> -Ĉiuj gets aŭton!

1163
00:50:50,282 --> 00:50:52,234
Ĉiuj gets aŭton!

1164
00:50:52,234 --> 00:50:52,722
>> [FINO reprodukto de vídeo]

1165
00:50:52,722 --> 00:50:54,590
>> Rakontanto: Je la sekvanta CS50 -

1166
00:50:54,590 --> 00:51:00,374
>> Parolanto 5: Ho mia gosh gosh gosh gosh
gosh gosh gosh gosh gosh gosh -

1167
00:51:00,374 --> 00:51:02,106
>> [Ukelele Teatraĵoj]