1
00:00:00,000 --> 00:00:11,270

2
00:00:11,270 --> 00:00:14,910
>> SPEAKER: Bone, tiu estas CS50.

3
00:00:14,910 --> 00:00:19,020
Jen la fino de semajno tri, kaj se
vi ne eluzis jam,

4
00:00:19,020 --> 00:00:21,790
scias ke estos tagmanĝo
tiu vendredo kiel kutime, kie

5
00:00:21,790 --> 00:00:25,430
Vi povas ĝui bonan konversacion
kaj manĝo ĉe Fajro kaj Ice

6
00:00:25,430 --> 00:00:27,980
kun kelkaj el CS50 La
bastonon kaj samklasanoj.

7
00:00:27,980 --> 00:00:30,170
Estrus al tiu URL tie.

8
00:00:30,170 --> 00:00:33,420
>> Nun vi eble memoras, aŭ vi
eble baldaŭ povos kompreni,

9
00:00:33,420 --> 00:00:35,970
tion ĉi tie, kiuj
estas donita fine

10
00:00:35,970 --> 00:00:37,850
de la semestro por multaj klasoj.

11
00:00:37,850 --> 00:00:40,870
Tn ekzameno bluaj libroj, en kiuj
vi skribas viajn respondojn al la ekzamenoj.

12
00:00:40,870 --> 00:00:44,240
Nun mi havas tie 26 tiajn
bluaj libroj, sur ĉiu el ili

13
00:00:44,240 --> 00:00:47,580
Estas skribita nomo, A tra Z. Kaj
ja la nomoj estas ke simpla, A

14
00:00:47,580 --> 00:00:50,490
tra Z. El
la celoj proksimigxis hodiaŭ

15
00:00:50,490 --> 00:00:53,910
tuj estos daŭrigi kion
ni komencis lunde, kiu ne estas

16
00:00:53,910 --> 00:00:57,830
tiel rigardante kodon, sed vere
rigardas ideoj kaj problemo solvita.

17
00:00:57,830 --> 00:01:00,170
Unu el la celoj kaj
promesoj de tiu kurso

18
00:01:00,170 --> 00:01:02,985
estas instrui vin pensi pli
zorge, pli metode,

19
00:01:02,985 --> 00:01:05,400
kaj solvi problemojn pli efike.

20
00:01:05,400 --> 00:01:09,526
Kaj efektive, ni povas fari, ke vere
sen eĉ tuŝi linion de kodo.

21
00:01:09,526 --> 00:01:12,150
Do mi havas kelkaj elefantoj
tien hodiaŭ, oranĝa kaj blua,

22
00:01:12,150 --> 00:01:15,780
se ni povus atingi unu volontulo,
eble el malantaux ol kutime.

23
00:01:15,780 --> 00:01:18,070
Kiom proksimume dekstra tie, venu malsupren.

24
00:01:18,070 --> 00:01:24,180
La celo de kio tuj estos al
helpi plus administri ĉi ekzamenon tie.

25
00:01:24,180 --> 00:01:24,935
Kio estas via nomo?

26
00:01:24,935 --> 00:01:25,768
>> Publiko: Mary Beth.

27
00:01:25,768 --> 00:01:27,560
SPEAKER: Mary Beth, venu supren.

28
00:01:27,560 --> 00:01:29,560
Lasu min eltiri la mikrofono tie por vi.

29
00:01:29,560 --> 00:01:32,172

30
00:01:32,172 --> 00:01:32,880
Agrable renkonti vin.

31
00:01:32,880 --> 00:01:34,005
>> Publiko: Nice to meet you.

32
00:01:34,005 --> 00:01:36,790
SPEAKER: Bone, do mi devas
jen bluaj libroj A tra Z

33
00:01:36,790 --> 00:01:41,680
kaj mi tuj ŝajnigas ke
Mi havas unu el la studentoj,

34
00:01:41,680 --> 00:01:45,770
kaj ili estas eniranta iom hazarde
ĉe la fino de tri horo ekzamenon bloko,

35
00:01:45,770 --> 00:01:49,400
Do oni finas en iu
duon-hazarda ordo kiel ĉi.

36
00:01:49,400 --> 00:01:54,510
Nun via laboro en nur momento tuj
al be-- ĉi estas vere kiel akiri

37
00:01:54,510 --> 00:01:56,820
turnis al la fino de
la klaso, verŝajne.

38
00:01:56,820 --> 00:02:01,120
Via tasko nun tuj estos, tute
simple, ordigi tiujn bluajn librojn por ni

39
00:02:01,120 --> 00:02:05,220
de A tra Z

40
00:02:05,220 --> 00:02:08,400
>> Publiko: Ho, tio estas
tuj prenos ĉiam.

41
00:02:08,400 --> 00:02:13,747
>> SPEAKER: Kaj ni viglu
kiel vi faras tion, sen premo.

42
00:02:13,747 --> 00:02:15,330
Publiko: Ne, ne premon aŭ nenion.

43
00:02:15,330 --> 00:02:19,230

44
00:02:19,230 --> 00:02:23,570
>> SPEAKER: Kaj por amuzo,
ni starigis temporizador.

45
00:02:23,570 --> 00:02:26,680

46
00:02:26,680 --> 00:02:28,700
>> Publiko: Tiom amuza, tiel amuza.

47
00:02:28,700 --> 00:02:36,741

48
00:02:36,741 --> 00:02:38,574
>> SPEAKER: Mi povas teni la mic por vi.

49
00:02:38,574 --> 00:02:40,240
Bone, ni jhus duobliĝis nia rapido.

50
00:02:40,240 --> 00:02:44,190

51
00:02:44,190 --> 00:02:49,060
Do intertempe, lasu min supozi kio estas
tuj estos la demandon por Mary Beth

52
00:02:49,060 --> 00:02:51,540
estas kio ŝi faras, kiel estas
ŝi rondirante solvanta ĉi?

53
00:02:51,540 --> 00:02:54,040
Kaj fakte, vi eble ne havas
iam pensis pri io

54
00:02:54,040 --> 00:02:57,440
tiel simpla kiam vi elektu
ĝis 26 libroj kiel tiu,

55
00:02:57,440 --> 00:02:59,350
kiu do havas naturan
ordigante ilin.

56
00:02:59,350 --> 00:03:01,335
Kio estas la procezo
ke vi vere uzas?

57
00:03:01,335 --> 00:03:03,770
Ĉu sufiĉe hazarda simple
prenante la unua vi vidos

58
00:03:03,770 --> 00:03:05,250
kaj metante ĝin en lia loko?

59
00:03:05,250 --> 00:03:09,680
Ĉu vi unue movi viajn manojn ĉirkaŭ
serĉi A tiam serĉi B?

60
00:03:09,680 --> 00:03:11,722
Ĉu vi rigardu al
paro de ili flankon ĉe flanko

61
00:03:11,722 --> 00:03:14,680
kaj simple diri, atendu minuton, tiu
ne estas rajto, kaj tiam interŝanĝi la ordon?

62
00:03:14,680 --> 00:03:16,960
Ni vidis jam lunde
ke estas pluraj manieroj

63
00:03:16,960 --> 00:03:22,140
en kiu ni povas fari tion, kaj
ja kiel ni apud la fino ĉi tie,

64
00:03:22,140 --> 00:03:26,360
Mi prenus noto eble
kion Mary Beth faras.

65
00:03:26,360 --> 00:03:30,040
Ni havas malmultajn amasoj ĝi similas,
granda unu, tri pli malgrandajn.

66
00:03:30,040 --> 00:03:33,790

67
00:03:33,790 --> 00:03:36,415
>> Publiko: Mi ordigante ilin
kiam mi trovas du leterojn

68
00:03:36,415 --> 00:03:39,540
kiun mi konas estas kune en sekvenco,
Mi metis ilin kune tiel ke mi ne

69
00:03:39,540 --> 00:03:42,915
devi maltrankviligi konservante
aŭtoveturejo de tuta vico da libroj.

70
00:03:42,915 --> 00:03:45,706
Estas nur, ho, A estas la unua,
Mi havas ĉi stako tie.

71
00:03:45,706 --> 00:03:47,580
SPEAKER: Do, preskaŭ kiel
puzlo pecoj kiuj

72
00:03:47,580 --> 00:03:49,860
rajti formon al
parigi kun ĉiu alia.

73
00:03:49,860 --> 00:03:51,026
Publiko: Pli malpli, jes.

74
00:03:51,026 --> 00:03:55,320
SPEAKER: OK, bonega.

75
00:03:55,320 --> 00:03:59,850
Kaj nun ĉiu el tiuj
aretoj estas supozeble ordo?

76
00:03:59,850 --> 00:04:00,990
>> Publiko: Yeah.

77
00:04:00,990 --> 00:04:09,900
>> SPEAKER: Bone, A tra Z Ĉiuj
Bone, gratulon, vi faris gxin.

78
00:04:09,900 --> 00:04:11,461
Vi havas vian preferatan.

79
00:04:11,461 --> 00:04:11,960
Blua?

80
00:04:11,960 --> 00:04:13,530
Bone, dankon por tio.

81
00:04:13,530 --> 00:04:16,679
Do Mary Beth ne proponas
kion ŝi alproksimiĝo estis,

82
00:04:16,679 --> 00:04:19,720
sed kio estas alia alproksimiĝo kiom vi
venu pri ordiga tion?

83
00:04:19,720 --> 00:04:21,130
Kion vi faris?

84
00:04:21,130 --> 00:04:24,060
La rekordo bati estus estinta
unu minuton kaj 50 aŭ tiel sekundoj,

85
00:04:24,060 --> 00:04:26,039
pli la aĵoj mi forgesis rakonti.

86
00:04:26,039 --> 00:04:27,080
Kion vi faris?

87
00:04:27,080 --> 00:04:27,579
Yeah?

88
00:04:27,579 --> 00:04:28,735
Publiko: Prenu la stako.

89
00:04:28,735 --> 00:04:29,776
Komencos de la komenco.

90
00:04:29,776 --> 00:04:32,284
Kontrolu vian paperoj.

91
00:04:32,284 --> 00:04:36,586
Se la supra estas pli altaj
ol, eble, ili estas,

92
00:04:36,586 --> 00:04:38,980
malsupre estas
alta, tiam ŝanĝi ilin.

93
00:04:38,980 --> 00:04:41,300
>> SPEAKER: OK, tiel komencante
ĉe la supro kaj la malsupro,

94
00:04:41,300 --> 00:04:43,716
kaj tiam laboras vian vojon
internen tiel, interŝanĝante ilin?

95
00:04:43,716 --> 00:04:46,580
OK, do iom similan
en spirito bobelo speco,

96
00:04:46,580 --> 00:04:49,160
sed elektante la ekstremoj
Ne la apudaj paroj.

97
00:04:49,160 --> 00:04:52,080
Sed la mallonga de ĝi estas ke ekzistas
certe faskon de malsamaj manieroj

98
00:04:52,080 --> 00:04:54,210
ni povus fari tion, kaj
sincere, mi kredas ke vi ia

99
00:04:54,210 --> 00:04:55,700
adoptita paro alproksimiĝoj, dekstra?

100
00:04:55,700 --> 00:05:00,567
Vi faris specon de kvar ordo amasoj, kaj
tiam efike kunfandis ilin kune.

101
00:05:00,567 --> 00:05:02,650
Kaj tio, daresay, alia
tekniko entute.

102
00:05:02,650 --> 00:05:06,950
Vi ne traktis ĝin kiel unu granda amaso,
Vi dividis la problemon en kvar quads,

103
00:05:06,950 --> 00:05:09,820
se vi volas, kaj tiam iel
kunfandis ilin en la fino.

104
00:05:09,820 --> 00:05:13,410
>> Do ni konsideru, en lasta petskribo,
kiel alie oni povus fari tion.

105
00:05:13,410 --> 00:05:15,860
Ni formaligis la nocio
de bobelo speco lasta fojo,

106
00:05:15,860 --> 00:05:18,780
kaj bobelo speco recall estis
algoritmo kiu ni bildigita

107
00:05:18,780 --> 00:05:22,640
kun ok el viaj samklasanoj tien,
ŝajne hazarde ordo unue.

108
00:05:22,640 --> 00:05:26,110
Kaj ni do decidis paroj, se
du elementoj estas el ordo,

109
00:05:26,110 --> 00:05:26,950
simple interŝanĝu ilin.

110
00:05:26,950 --> 00:05:28,930
Do kvar kaj du estas
evidente misfunkcias,

111
00:05:28,930 --> 00:05:31,080
tial tiuj du samklasanoj
ŝanĝis poziciojn.

112
00:05:31,080 --> 00:05:35,390
Kaj tiam ni ripetis kun kvar kaj ses,
tiam ses kaj ok, sur ĉiu ripeto,

113
00:05:35,390 --> 00:05:36,980
movas dekstren.

114
00:05:36,980 --> 00:05:42,590
>> Do donita ok homoj, kiom da paroj
komparojn ĉu mi faras dum marŝante de

115
00:05:42,590 --> 00:05:45,220
maldekstre dekstren en unu tia ripeto?

116
00:05:45,220 --> 00:05:48,410
Kiom komparojn?

117
00:05:48,410 --> 00:05:49,197
Seven, dekstra?

118
00:05:49,197 --> 00:05:51,405
Ĉar se estas ok
homoj sed vi havas la paro

119
00:05:51,405 --> 00:05:53,880
ilin kaj vi tenas movanta
unu hop dekstren,

120
00:05:53,880 --> 00:05:56,060
vi ne tuj havos ok
komparojn ĉar vi ne povas kompari

121
00:05:56,060 --> 00:05:59,226
elementon kontraŭ si, aŭ ĝi farus
nur estu sencela, do vi havas sep.

122
00:05:59,226 --> 00:06:01,290
Aŭ pli ĝenerale, se
ni havas n homoj, ni

123
00:06:01,290 --> 00:06:04,300
faru n minus 1 komparoj
kun bobelo varo.

124
00:06:04,300 --> 00:06:08,150
>> Do ni konsideras nun kiel bonaj aŭ
malbona bobelo speco efektive estis, kaj provi

125
00:06:08,150 --> 00:06:13,570
doni nin vortprovizon per
kiu kritikon algoritmoj kiel tiu,

126
00:06:13,570 --> 00:06:14,430
kaj baldaŭ nia propra.

127
00:06:14,430 --> 00:06:16,970
Do la unuaj pasas tra
bobelo varo, la unua fojo

128
00:06:16,970 --> 00:06:20,909
Mi promenis de maldekstre al dekstre tra la
stadio, prenis min n minus 1 komparoj.

129
00:06:20,909 --> 00:06:22,950
Kaj ke tuj estos mia
unueco de mezuro, dekstra?

130
00:06:22,950 --> 00:06:26,170
Mi estis afabla de paroli kaj promenado,
iom rapida, iom malrapida,

131
00:06:26,170 --> 00:06:29,300
tiel rakontante mia nombro de sekundoj
ne aparte diri,

132
00:06:29,300 --> 00:06:32,260
sed kalkulante la nombron de
operacioj kiuj mi faris lunde,

133
00:06:32,260 --> 00:06:35,900
komparante du homoj, kiuj sentas
kiel bela unueco de mezuro.

134
00:06:35,900 --> 00:06:40,980
>> Do n minus 1 paŝas la unua fojo,
sed tiam kio okazis post tio?

135
00:06:40,980 --> 00:06:46,610
Kio estas la upside de unu paŝo
tra alie Unsorted listo?

136
00:06:46,610 --> 00:06:49,840
Kion vi povas diri al mi pri la ero
kiu estis la tuta vojo tien?

137
00:06:49,840 --> 00:06:51,300
Yeah?

138
00:06:51,300 --> 00:06:52,870
Tio estis la plej granda elemento, dekstra?

139
00:06:52,870 --> 00:06:55,710
Numero ok, kvankam ŝi
komenciĝis tie, ĉiufoje mi

140
00:06:55,710 --> 00:06:57,860
komparis ŝin kontraŭ
najbaro, ŝi tenis

141
00:06:57,860 --> 00:07:00,480
bobelanta supren dekstren
flanko de la listo.

142
00:07:00,480 --> 00:07:02,710
Kaj efektive, jen kie
la algoritmo prenas lian nomon.

143
00:07:02,710 --> 00:07:07,630
>> Nun ke logiko, kiom komparoj
bezonas mi faras en la dua tempo

144
00:07:07,630 --> 00:07:09,800
Mi faros, ke pasu de maldekstre al dekstre?

145
00:07:09,800 --> 00:07:10,730
n minus 2, dekstra?

146
00:07:10,730 --> 00:07:14,297
Estus simple esti malŝparas mian tempon se mi
konservi komparante ok kontraŭ iu

147
00:07:14,297 --> 00:07:16,630
alie, ĉar ni jam scias
ŝi estis en la ĝusta loko.

148
00:07:16,630 --> 00:07:19,760
Do tio estas iom de
optimumigo, do la venonta paŝo

149
00:07:19,760 --> 00:07:23,899
tuj estos plus n minus du paŝojn,
kie n estas la nombro da homoj.

150
00:07:23,899 --> 00:07:26,940
Nun vi povas ia extrapolar, eĉ
Se vi ne estas komputila sciencisto

151
00:07:26,940 --> 00:07:27,680
kiel tiu finas.

152
00:07:27,680 --> 00:07:31,259
Je la fino de tiu algoritmo, supozeble
Vi havas nur unu komparo lasis.

153
00:07:31,259 --> 00:07:33,800
Vi devas speco de ripari la
komencante de la listo se du

154
00:07:33,800 --> 00:07:36,540
kaj unu estas el ordo
kaj devas esti unu kaj du,

155
00:07:36,540 --> 00:07:40,330
tial ĉi fundoj tra
plus 1 fina komparo.

156
00:07:40,330 --> 00:07:44,500
>> Nun la skalara, dot, punkto speco de ondoj estas
manojn iom el la juicier detaloj

157
00:07:44,500 --> 00:07:46,452
sed ni simple iru antaŭen kaj simpligi.

158
00:07:46,452 --> 00:07:48,660
Se vi memoras el alta
lernejo, sincere, multe de vi

159
00:07:48,660 --> 00:07:50,340
havis math libroj kiuj havis
iom lertaĵoj folio

160
00:07:50,340 --> 00:07:52,550
sur la kovrilo aŭ
ferdeko trasera kiu montris al vi

161
00:07:52,550 --> 00:07:56,400
kion serio sumatorios ŝatas
tio finfine aldonis ĝis.

162
00:07:56,400 --> 00:07:59,600
En la ĝenerala kazo, se vi havas
variablon kiel n, kaj ja ĉi tiu,

163
00:07:59,600 --> 00:08:01,634
Se vi rigardis vian
malnova lernejo math libro,

164
00:08:01,634 --> 00:08:04,050
vi vidus ke tio reale
adicias supren al tiu sumo tie,

165
00:08:04,050 --> 00:08:07,970
n × n minus 1 ĉiu dividita per 2.

166
00:08:07,970 --> 00:08:11,172
Do nun lasu min nur kondiĉas
tio estas vera, do sur salto de fido

167
00:08:11,172 --> 00:08:12,880
ke estas kion ĉi resumas
ĝis, kaj ni povis

168
00:08:12,880 --> 00:08:14,341
pruvi ke en pli ĝenerala kazo.

169
00:08:14,341 --> 00:08:15,590
Sed nun ni ekspansiiĝi ​​ĉi ekstere.

170
00:08:15,590 --> 00:08:19,920
Do ni multiplikas ĉi, do tio
n kvadratoj, minus n, ĉiu dividita per 2.

171
00:08:19,920 --> 00:08:23,200
Tio vere n kvadratoj,
dividita per 2, minus n super 2

172
00:08:23,200 --> 00:08:25,010
tiel ke ĉio bela kaj interesa.

173
00:08:25,010 --> 00:08:27,060
Sed kio okazas se ni
nun ŝtopi-en valoro?

174
00:08:27,060 --> 00:08:29,724
Supozi Mi ne havis ok
homoj, sed diru miliono.

175
00:08:29,724 --> 00:08:31,890
Kaj miliono nur ĉar
ĝi estas iom granda nombro,

176
00:08:31,890 --> 00:08:34,039
ni ŝtopi ke en kaj vidu kio okazas.

177
00:08:34,039 --> 00:08:39,039
Do se mi ŝtopi miliono en tiu formulo
Mi tuj akiri milionon kvadrato,

178
00:08:39,039 --> 00:08:42,868
dividita per 2, minus a
milionoj, dividita per 2.

179
00:08:42,868 --> 00:08:44,159
Nun kio tio tuj egali?

180
00:08:44,159 --> 00:08:47,354
Do 500 miliardoj, minus 500.000.

181
00:08:47,354 --> 00:08:49,270
Kaj se mi efektive fari
ke math ekstere, kiu signifas

182
00:08:49,270 --> 00:08:53,920
ke ordigo miliono
homo kun la bobelo speco

183
00:08:53,920 --> 00:09:01,800
konduku min 499.999.500.000
ŝtupoj aŭ komparojn en la fino,

184
00:09:01,800 --> 00:09:02,900
Ni nur extrapolar.

185
00:09:02,900 --> 00:09:06,860
>> Kiu sentas bela malrapida, sed sincere
mezurante unu aparta enigo

186
00:09:06,860 --> 00:09:09,160
kiel tiu, ne ĉiuj kiuj rakonton.

187
00:09:09,160 --> 00:09:14,050
Sed ja ĝi sugestas ke kiel n
ricevas pli kaj pli grandaj, ĉi tiu algoritmo

188
00:09:14,050 --> 00:09:16,280
ia sentas malbona kaj
malbona, aŭ vi vere

189
00:09:16,280 --> 00:09:20,450
komenci senti la doloron de tiu
potencigo, ke n kvadratoj,

190
00:09:20,450 --> 00:09:21,770
kiu adicias supren sufiĉe rapide.

191
00:09:21,770 --> 00:09:25,340
Kaj tiu detalo ne estas
perdiĝis homoj, fakte

192
00:09:25,340 --> 00:09:29,640
antaŭ kelkaj jaroj iu senatano kiu estis
kampanjado, sidiĝis por intervjuo

193
00:09:29,640 --> 00:09:32,180
kun Google Eric
Schmidt, CEO tiutempe,

194
00:09:32,180 --> 00:09:36,380
kaj estis defiita per demando
multe kiel ni esploras hodiaŭ.

195
00:09:36,380 --> 00:09:38,468
Ni rigardu.

196
00:09:38,468 --> 00:09:45,280
>> [VIDEO Playback]

197
00:09:45,280 --> 00:09:48,560
>> -Senator, Vi estas ĉi tie
ĉe Google, kaj mi ŝatas

198
00:09:48,560 --> 00:09:53,382
pensi pri la prezidanteco
kiel laboron intervjuo.

199
00:09:53,382 --> 00:09:56,434
Nun, estas malfacile akiri
laboron kiel prezidanto,

200
00:09:56,434 --> 00:09:58,100
kaj vi tuj tra la rigorecoj nun.

201
00:09:58,100 --> 00:10:01,860
Ĝi estas ankaŭ malfacile akiri laboron ĉe Google.

202
00:10:01,860 --> 00:10:05,490
Ni havas demandojn, kaj ni
petu nian kandidatoj demandoj

203
00:10:05,490 --> 00:10:09,770
kaj ĉi tiu estas de Larry Schwimmer.

204
00:10:09,770 --> 00:10:14,760
What-- vi uloj pensas min
kidding, estas ĝuste ĉi tie.

205
00:10:14,760 --> 00:10:17,930
Kio estas la plej efika maniero
ordigi miliono 32 bitoj entjeroj?

206
00:10:17,930 --> 00:10:21,800

207
00:10:21,800 --> 00:10:24,350
>> -Well--

208
00:10:24,350 --> 00:10:25,200
>> -I'm Bedaŭras, maybe--

209
00:10:25,200 --> 00:10:27,400
>> -No, Ne, ne.

210
00:10:27,400 --> 00:10:30,700
Mi kredas ke la bobelo speco
estus malĝuste iri.

211
00:10:30,700 --> 00:10:34,165

212
00:10:34,165 --> 00:10:38,180
>> -Come Je, kiu rakontis al li ĉi tiu?

213
00:10:38,180 --> 00:10:40,590
Mi ne vidis komputilo
scienco en via fono.

214
00:10:40,590 --> 00:10:42,130
>> -We've Ricevis nian spionoj tie.

215
00:10:42,130 --> 00:10:44,930

216
00:10:44,930 --> 00:10:48,444
>> -OK, Ni petu malsama
intervjuo demando.

217
00:10:48,444 --> 00:10:49,300
>> [FINO VIDEO Playback]

218
00:10:49,300 --> 00:10:52,290
>> SPEAKER: Tiel parolas
specifaj nombroj kvankam,

219
00:10:52,290 --> 00:10:53,890
ne tuj esti tiom utila.

220
00:10:53,890 --> 00:10:56,810
Ne estas vivo leciono ke bobelo
varon, donis milionon enigoj,

221
00:10:56,810 --> 00:10:58,590
povus preni kiel multaj kiel 500 miliardoj paŝoj.

222
00:10:58,590 --> 00:11:01,120
Vi ne povas vere ĝeneraligi
tro efike de tiu

223
00:11:01,120 --> 00:11:03,560
kaj fari bonan decidoj de dezajno
kiam skribas programojn.

224
00:11:03,560 --> 00:11:07,070
Do ni enfokusigi kvankam sur kiel
Ni povus simpligi tiun rezulton.

225
00:11:07,070 --> 00:11:11,780
>> Do mi reliefigis en flava tie
la rezulto de n kvadrato dividita per 2,

226
00:11:11,780 --> 00:11:14,330
tiel miliono kvadrato
dividita per 2, kaj tiam

227
00:11:14,330 --> 00:11:16,710
Mi reliefigis kio
la finfina respondo estis

228
00:11:16,710 --> 00:11:20,180
iam ni subtrahita ekstere n dividita per 2.

229
00:11:20,180 --> 00:11:24,850
Kaj la aserto Mi iras fari nun,
kiuj la heck zorgas se subtrahi ekstere

230
00:11:24,850 --> 00:11:30,060
iom maljuna n super 2 kiam la unuaj
parto de tiu formulo estas tiel granda?

231
00:11:30,060 --> 00:11:33,910
Ĝi regas la alia
termino, n kvadrato dividita per 2

232
00:11:33,910 --> 00:11:37,510
estas tiel granda, klare, kiel
n ricevas grandaj kiel miliono,

233
00:11:37,510 --> 00:11:41,450
ke estas vere granda diferenco ĉe
la fino de la tago inter 500 miliardoj

234
00:11:41,450 --> 00:11:45,730
kaj 499.999.500.000?

235
00:11:45,730 --> 00:11:46,349
Ne vere.

236
00:11:46,349 --> 00:11:48,640
Kaj tiel kion ni tuj
faru kiel komputilo sciencistoj estas

237
00:11:48,640 --> 00:11:53,270
ignori tiujn malsupera ordo terminoj kaj
preni iun kiel ĉi tio kaj vere

238
00:11:53,270 --> 00:11:56,050
nur simpligi ĝin al la
termino kiu tuj gravas.

239
00:11:56,050 --> 00:12:00,315
La pli granda nia datenaroj akiri, des pli
niajn datumbazojn akiri, des pli da retpaĝoj

240
00:12:00,315 --> 00:12:02,690
ni devas esplori, la pli
amikojn vi havas sur Facebook.

241
00:12:02,690 --> 00:12:07,340
>> Kiel n prenas pli granda, ni vere
tuj zorgas pri la plej granda

242
00:12:07,340 --> 00:12:11,560
termino en ajna tia analizo de
nia algoritmoj agado.

243
00:12:11,560 --> 00:12:16,230
Kaj mi tuj diros, vi scias kion,
bobelo varo estas sur la ordo de granda O,

244
00:12:16,230 --> 00:12:18,060
sur la ordo de n kvadratoj.

245
00:12:18,060 --> 00:12:20,090
Ne ĝuste n
kvadrato kiel ni vidis,

246
00:12:20,090 --> 00:12:22,060
sed kiuj vere zorgas
pri tiuj malgrandaj terminoj

247
00:12:22,060 --> 00:12:24,390
kaj sincere, kiu vere
zorgas se ni dividos 2?

248
00:12:24,390 --> 00:12:25,870
Tio estas nur konstanta faktoro.

249
00:12:25,870 --> 00:12:29,480
Kaj estas 500 miliardoj kontre 250
miliardo vere ke granda de traktadon?

250
00:12:29,480 --> 00:12:32,190
Mi povis nur atendi unu jaron,
tiam mia tekkomputilo laŭvorte

251
00:12:32,190 --> 00:12:34,810
ricevi duoble rapida en aparataro,
kaj tiu speco de diferenco

252
00:12:34,810 --> 00:12:36,650
nur foriras nature super tempo.

253
00:12:36,650 --> 00:12:39,300
>> Kion ni zorgas proksimume estas
la esprimo, la parto

254
00:12:39,300 --> 00:12:42,489
de la esprimo ke tuj varios
kiel nia eniro ricevas pli kaj pli granda.

255
00:12:42,489 --> 00:12:45,280
Kaj efektive, en la reala mondo,
tio estas kio okazas ĉiufoje

256
00:12:45,280 --> 00:12:48,330
estas la eniroj al niaj problemoj kaj
algoritmoj estas akirantaj pli granda.

257
00:12:48,330 --> 00:12:53,470
Tiel granda O tuj estos la skribmaniero,
la asimptota skribmaniero, ke ni simple

258
00:12:53,470 --> 00:12:57,160
uzi kiel komputilo sciencistoj por priskribi
la prezento, aŭ la rultempo,

259
00:12:57,160 --> 00:12:58,130
de algoritmo.

260
00:12:58,130 --> 00:13:00,800
Tiel ke ni povas kompari algoritmoj
sur malsamaj komputiloj skribita

261
00:13:00,800 --> 00:13:04,170
de malsamaj personoj, uzante
iu fundamente simila metriko

262
00:13:04,170 --> 00:13:07,557
kiel la numero de komparoj vi
fari, aŭ eble la nombro de svopoj

263
00:13:07,557 --> 00:13:08,140
vi faras.

264
00:13:08,140 --> 00:13:11,910
>> Kion ni ne tuj
grafo estas la kvanto de tempo

265
00:13:11,910 --> 00:13:13,981
kiu trasmite la horloĝo
sur la muro tipe.

266
00:13:13,981 --> 00:13:16,230
Kion ni ne tuj maltrankviligos
proksimume estas kiom memoro

267
00:13:16,230 --> 00:13:17,820
vi uzas nuntempe en
Almenaŭ, kvankam tio

268
00:13:17,820 --> 00:13:19,370
alia rimedo ni povus mezuri.

269
00:13:19,370 --> 00:13:23,610
Ni provos bazi nian analizo
sur nur la bazajn operaciojn, la aĵoj,

270
00:13:23,610 --> 00:13:25,930
sincere, ke vi povas vidi la plej vide.

271
00:13:25,930 --> 00:13:30,700
Do kun iu kiel granda O de n
kvadrata, mi asertas ke O de n kvadratoj

272
00:13:30,700 --> 00:13:35,820
estas supra ligis sur la tn
rultempo de bobelo varo.

273
00:13:35,820 --> 00:13:38,820
En aliaj vortoj, se vi
volis aserti ke ekzistas

274
00:13:38,820 --> 00:13:41,370
tiu supra limo sur kiom
paŝas algoritmo povus preni,

275
00:13:41,370 --> 00:13:46,240
ĝi tuj estos en la granda O de n
akorditaj en tiu kazo, supera baro.

276
00:13:46,240 --> 00:13:49,710
>> Kio se mi anstataŭ ŝanĝi la
rakonto esti ne pri bobelo speco,

277
00:13:49,710 --> 00:13:50,910
sed pri tiu supera baro.

278
00:13:50,910 --> 00:13:54,030
Ĉu vi pensas de algoritmo
ke ni rigardis jam

279
00:13:54,030 --> 00:13:59,530
kies supera baro, maksimumo
mezuri tempon aŭ operacioj,

280
00:13:59,530 --> 00:14:04,300
estus dirita esti barita
per n, lineara funkcio,

281
00:14:04,300 --> 00:14:07,260
ne kvadrata kiu estas kurba?

282
00:14:07,260 --> 00:14:10,780
Kio estas algoritmo kiu
ĉiam prenas neniun pli

283
00:14:10,780 --> 00:14:12,860
ol kiel n paŝoj, aŭ
2n paŝoj, aŭ 3n pasxojn?

284
00:14:12,860 --> 00:14:13,360
Yeah?

285
00:14:13,360 --> 00:14:15,030
>> Publiko: Trovanta la
granda nombro en la listo?

286
00:14:15,030 --> 00:14:16,930
>> SPEAKER: Perfekta, trovante
la plej granda nombro en lerta.

287
00:14:16,930 --> 00:14:18,940
Se mi donita listo
homoj ekzemple,

288
00:14:18,940 --> 00:14:21,440
ĉiu de kiuj tenas numeron,
kio estas la maksimuma nombro

289
00:14:21,440 --> 00:14:23,770
de ŝtupoj devus konduki min,
prudente inteligenta persono,

290
00:14:23,770 --> 00:14:27,530
trovi la plej granda persono en tiu listo?

291
00:14:27,530 --> 00:14:28,100
n, ĉu ne?

292
00:14:28,100 --> 00:14:31,320
Ĉar en la plej malbona kazo, kie
eble la plej granda valoro estos?

293
00:14:31,320 --> 00:14:32,700
Ĝuste, la tutan vojon al la fino.

294
00:14:32,700 --> 00:14:34,575
Do, en la plej malbona kazo
superulo, mi povus

295
00:14:34,575 --> 00:14:36,450
devos iri la tutan vojon
tien kaj estu kiel,

296
00:14:36,450 --> 00:14:39,170
ho, jen la numero ok,
aŭ kion ajn tiu valoro estas.

297
00:14:39,170 --> 00:14:41,330
Nun estus nur stulta
se mi faris, ne?

298
00:14:41,330 --> 00:14:43,840
Serĉante pli kaj pli elementoj
se la lasta el ili estas tie?

299
00:14:43,840 --> 00:14:45,340
Tiel certe, n estas supera baro.

300
00:14:45,340 --> 00:14:47,420
Mi ne bezonas preni
pli paŝoj ol tio.

301
00:14:47,420 --> 00:14:51,580
>> Do kio se anstataŭ mi proponis ke
ekzistas algoritmoj en tiu mondo kiu

302
00:14:51,580 --> 00:14:57,750
havi rultempo tio
barita per granda O de log n log n?

303
00:14:57,750 --> 00:15:00,390
Kie ni vidis tiun antaŭ?

304
00:15:00,390 --> 00:15:00,890
Yeah?

305
00:15:00,890 --> 00:15:03,309
>> Publiko: En la telefono libro problemo?

306
00:15:03,309 --> 00:15:04,850
SPEAKER: Kiel la telefono libro problemon.

307
00:15:04,850 --> 00:15:07,754
Kio estis la mezuro de kiel
da tempo aŭ kiom da larmoj

308
00:15:07,754 --> 00:15:10,170
prenis mi trovi iun kiel
Mike Smith en la telefono libro?

309
00:15:10,170 --> 00:15:13,212
Ni asertis estis log n kaj
eĉ se nekonataj aŭ ĝi estas

310
00:15:13,212 --> 00:15:15,170
iom malprecizaj kia
logaritma aŭ eksponento estis,

311
00:15:15,170 --> 00:15:17,650
nur memoras ke log n
ĝenerale aludas al la procezo,

312
00:15:17,650 --> 00:15:20,790
en tiu kazo, la dividadon
io en duono denove, kaj denove,

313
00:15:20,790 --> 00:15:25,790
kaj denove, kaj denove, tiaj ke
ricevas pli malgranda kiel vi faras tion.

314
00:15:25,790 --> 00:15:28,470
>> Do log n aludas, certe,
al la telefono libro ekzemple,

315
00:15:28,470 --> 00:15:32,662
al duuma serĉo teorie, kiam ni
havis la virtualajn pordojn sur la tabulo,

316
00:15:32,662 --> 00:15:34,370
aŭ kiam Sean estis
serĉante ion.

317
00:15:34,370 --> 00:15:37,374
Se li uzis duuma serĉo, log n
estus la supera baro sur kiom

318
00:15:37,374 --> 00:15:38,040
tempo kiu postrestas.

319
00:15:38,040 --> 00:15:44,027
Sed tiuj algoritmoj kiuj kuris en
log n supozis kio ŝlosilo detale?

320
00:15:44,027 --> 00:15:45,360
Ke la listo estis ordigitaj, dekstra?

321
00:15:45,360 --> 00:15:47,789
Via algoritmo estas erara se
via enigo ne ordo,

322
00:15:47,789 --> 00:15:49,830
kaj tamen vi uzas
iu kiel duuma serĉo

323
00:15:49,830 --> 00:15:51,704
ĉar vi povus salti
rajton super la elemento

324
00:15:51,704 --> 00:15:53,600
sen rimarki estas ja tie.

325
00:15:53,600 --> 00:15:55,600
>> Nun kio povus ĉi signifas, granda O de unu?

326
00:15:55,600 --> 00:15:59,117
Tiu ne signifas, ke via algoritmo
prenas unu kaj nur unu paŝo,

327
00:15:59,117 --> 00:16:01,200
Ĝi simple signifas ĝin prenas
konstanta nombro de paŝoj.

328
00:16:01,200 --> 00:16:04,060
Eble estas 1, eble estas
10 eble estas 1.000,

329
00:16:04,060 --> 00:16:07,750
sed estas sendependa de
la amplekso de la problemo.

330
00:16:07,750 --> 00:16:10,850
Neniu afero kiom granda n,
konstanta tempa algoritmo

331
00:16:10,850 --> 00:16:12,747
ĉiam prenas la saman nombron de paŝoj.

332
00:16:12,747 --> 00:16:15,080
Do kio povus esti algoritmo
Ni parolis pri aŭ simple

333
00:16:15,080 --> 00:16:20,418
intuicie, ke venas al vi ke
ĉiam kuras en tn konstanta tempo?

334
00:16:20,418 --> 00:16:20,918
Yeah?

335
00:16:20,918 --> 00:16:22,001
>> Publiko: du nombroj.

336
00:16:22,001 --> 00:16:25,320
SPEAKER: du nombroj,
2 plus 2 estas 4, faritaj.

337
00:16:25,320 --> 00:16:27,227
Por ke povu labori, kion alian?

338
00:16:27,227 --> 00:16:28,560
Kion pri pli reala mondo, jes?

339
00:16:28,560 --> 00:16:30,686
>> Publiko: Trovanta la
unua aĵo en listo.

340
00:16:30,686 --> 00:16:32,810
SPEAKER: Trovanta la unua
ero en listo, sekura.

341
00:16:32,810 --> 00:16:34,540
Ni fakte parolis
pri arrays jam,

342
00:16:34,540 --> 00:16:36,540
kiel vi atingi la
unua ero en tabelo,

343
00:16:36,540 --> 00:16:40,465
negrave kiom longe la
tabelo estas en C kodo?

344
00:16:40,465 --> 00:16:43,090
Vi nur uzos kiel la krampo
nulo skribmaniero, bam, vi estas tie.

345
00:16:43,090 --> 00:16:46,120
Kaj efektive arrays, kiel flanken,
subteno io ĝenerale konata

346
00:16:46,120 --> 00:16:49,240
kiel aliro aleatorio, hazarda aliro
memoro, ĉar vi povas laŭvorte

347
00:16:49,240 --> 00:16:50,284
salti al iu loko.

348
00:16:50,284 --> 00:16:52,700
Ni povas fari ĉi tion eĉ pli simple
ni povas malantaŭenigi al semajno nulo

349
00:16:52,700 --> 00:16:53,900
Kiam ni faris Scratch.

350
00:16:53,900 --> 00:16:59,707
Kiom tempo ĝi prenas por la
diru bloko en Scratch ekzekuti?

351
00:16:59,707 --> 00:17:00,790
Nur konstanta tempo, ĉu ne?

352
00:17:00,790 --> 00:17:03,960
Diru ion, diri
ion, tio ne gravas

353
00:17:03,960 --> 00:17:07,359
kiom granda Grat mondo estas, ĉiam
tuj prenos la sama kvanto de tempo

354
00:17:07,359 --> 00:17:08,490
simple diri ion.

355
00:17:08,490 --> 00:17:11,089
>> Do tio estas konstanta tempo,
sed kio estas la flip flanko?

356
00:17:11,089 --> 00:17:13,030
Se tiu estis supra
baroj, kio se ni volas

357
00:17:13,030 --> 00:17:17,089
priskribi la subaj baroj
de nia algoritmoj rultempo?

358
00:17:17,089 --> 00:17:19,852
Preskaŭ bona kazo
potenciale, se vi volas,

359
00:17:19,852 --> 00:17:23,060
kvankam tiuj terminoj aplikeblas best
kazoj, plej kazoj, mezumo kazoj pli

360
00:17:23,060 --> 00:17:26,359
ĝenerale, sed ni simple enfokusigi
sur subaj baroj pli ĝenerale.

361
00:17:26,359 --> 00:17:31,920
Kio estas algoritmo kiu havas
suba baro de n paŝoj,

362
00:17:31,920 --> 00:17:33,350
aŭ 2n paŝoj, aŭ 3n pasxojn?

363
00:17:33,350 --> 00:17:36,241
Iu faktoro de n paŝoj,
tio estas lia malsupera.

364
00:17:36,241 --> 00:17:36,740
Yeah?

365
00:17:36,740 --> 00:17:37,910
>> Publiko: Bubble speco?

366
00:17:37,910 --> 00:17:41,610
>> SPEAKER: Bubble speco prenas
vi minimume n paŝojn, kial?

367
00:17:41,610 --> 00:17:42,279
Kial estas tio?

368
00:17:42,279 --> 00:17:45,320
Kial tiu komenco veni al vi
intuicie, eĉ se ĝi ne nur

369
00:17:45,320 --> 00:17:46,530
ankoraŭ?

370
00:17:46,530 --> 00:17:47,030
Yeah?

371
00:17:47,030 --> 00:17:47,990
>> Publiko: [inaudible].

372
00:17:47,990 --> 00:17:51,652

373
00:17:51,652 --> 00:17:52,360
SPEAKER: Ekzakte.

374
00:17:52,360 --> 00:17:55,810
En la plej bona ebla scenaro de
bobelo speco, kaj amaso de algoritmoj,

375
00:17:55,810 --> 00:17:58,769
se mi transdonu al vi ok personoj
kiuj jam ordo,

376
00:17:58,769 --> 00:18:00,560
estus malsaĝa
Pri vi, la algoritmo,

377
00:18:00,560 --> 00:18:02,202
iri reen
pli ol iam, ĉu ne?

378
00:18:02,202 --> 00:18:04,285
Ĉar kiam vi
trairu la liston unufoje

379
00:18:04,285 --> 00:18:08,090
vi devus rimarki, ho, mi faris nenian
svopoj, tiu listo estas ordigita, elirejo.

380
00:18:08,090 --> 00:18:09,700
Sed ke tuj prenos vin n paŝoj.

381
00:18:09,700 --> 00:18:12,033
>> Kaj inverse, kio estas alia
pensmanierojn pri ĝi?

382
00:18:12,033 --> 00:18:15,240
Bobelo speco estas omega,
tiel diri, de n,

383
00:18:15,240 --> 00:18:19,050
ĉar se vi rigardas
malpli ol n elementoj, kio

384
00:18:19,050 --> 00:18:23,009
estas la fundamenta demando tie?

385
00:18:23,009 --> 00:18:24,550
Vi ne scias, ĉu ĝi estas ordo, dekstre.

386
00:18:24,550 --> 00:18:26,800
Ni homoj heroajxoj ekrigardi ok
personoj kaj estu kiel, Ho, estas ordigitaj,

387
00:18:26,800 --> 00:18:28,430
kiu ne prenas min n paŝojn, sed faris.

388
00:18:28,430 --> 00:18:30,810
Viaj okuloj, kvankam vi speco
de havas grandan kampon de vidado,

389
00:18:30,810 --> 00:18:33,184
vi rigardis ok elementojn,
vi rigardis ok personoj,

390
00:18:33,184 --> 00:18:34,610
tio estas ok ŝtupoj efike.

391
00:18:34,610 --> 00:18:38,612
Kaj nur se mi iros tra la tuta
Listo mi rimarkas, jes, ordigitaj.

392
00:18:38,612 --> 00:18:41,320
Se mi haltas duonvoje pensante, ĉiuj
Bone, ĝi estas bela ordo ĝis nun,

393
00:18:41,320 --> 00:18:42,520
kio estas prognozo ĝi ne estas ordo?

394
00:18:42,520 --> 00:18:44,186
Tio algoritmoj ne tuj estos ĝusta.

395
00:18:44,186 --> 00:18:46,250
Povus esti pli rapida, sed malĝusta.

396
00:18:46,250 --> 00:18:48,500
>> Do nun ni havas manieron de
priskribantaj subaj baroj,

397
00:18:48,500 --> 00:18:49,710
kaj kio pri konstanta tempo?

398
00:18:49,710 --> 00:18:54,565
Kio estas algoritmo kiu havas pli malaltan
ligis sur ĝia rultempo de unu?

399
00:18:54,565 --> 00:18:58,350
1 paŝo, 2 paŝoj, 10 paŝojn, sed
konstanto sendependa de n,

400
00:18:58,350 --> 00:18:59,310
la amplekso de la enigo?

401
00:18:59,310 --> 00:19:03,930

402
00:19:03,930 --> 00:19:04,600
Jes, en dorso.

403
00:19:04,600 --> 00:19:05,309
>> Publiko: printf?

404
00:19:05,309 --> 00:19:06,183
SPEAKER: Kio estas tio?

405
00:19:06,183 --> 00:19:07,184
Publiko: printf?

406
00:19:07,184 --> 00:19:07,850
SPEAKER: printf.

407
00:19:07,850 --> 00:19:08,400
OK, sekura.

408
00:19:08,400 --> 00:19:10,720
Do necesas fiksa kvanto de paŝoj.

409
00:19:10,720 --> 00:19:13,170
Mi devus now-- nun
ni parolas pri C kodo

410
00:19:13,170 --> 00:19:16,040
kaj ne Scratch, iu
kiel diri, kun printf,

411
00:19:16,040 --> 00:19:17,710
ni devas komenci akiri zorgema.

412
00:19:17,710 --> 00:19:21,090
Ĉar printf ne prenu
enigo, estas cxeno,

413
00:19:21,090 --> 00:19:23,220
kaj kordoj do teknike havas longa.

414
00:19:23,220 --> 00:19:25,530
Do se ni nun volas kapti
sur vi, se vi ne gravas,

415
00:19:25,530 --> 00:19:29,430
teknike ni povus argumenti ke printf
ne prenu ŝanĝiĝema longitudo enigo,

416
00:19:29,430 --> 00:19:32,270
kaj certe ĝi povus preni pli
tempon por presi kordo tiu longa,

417
00:19:32,270 --> 00:19:33,560
ol tiu longa.

418
00:19:33,560 --> 00:19:36,570
>> Do kio se ni konsideras nur la
ordig kaj serĉanta ekzemplojn?

419
00:19:36,570 --> 00:19:40,450
Kio pri Mike Smith en la telefono
libro aŭ duuma serĉo pli ĝenerale?

420
00:19:40,450 --> 00:19:42,220
En la plej bona kazo, kio povus okazi?

421
00:19:42,220 --> 00:19:45,577
Mi malfermas la telefono libro kaj, bam,
ekzistas Mike Smith nombro.

422
00:19:45,577 --> 00:19:46,660
Mi povas voki lin tuj.

423
00:19:46,660 --> 00:19:49,390
>> Prenis unu paŝo, eble du paŝojn,
sed konstanta nombro de paŝoj

424
00:19:49,390 --> 00:19:50,230
se mi akiris bonŝanca.

425
00:19:50,230 --> 00:19:52,570
Kaj sincere, ni vidis sur
Lundo via samklasano

426
00:19:52,570 --> 00:19:54,710
akiri tute bonŝanca dufoje en vico.

427
00:19:54,710 --> 00:19:57,050
Kaj tio ja estis konstanta
tempo en subaj baroj

428
00:19:57,050 --> 00:20:01,280
sur la algoritmo en demando por trovi
la numero 50 malantaŭ tiuj fermitaj

429
00:20:01,280 --> 00:20:01,830
pordoj.

430
00:20:01,830 --> 00:20:06,400
>> Nun, kiel flanken, se vi malkovros
ke tiel granda O, la supera baro,

431
00:20:06,400 --> 00:20:09,310
kaj omega, la suba baro,
Estas unu en la sama, kiu

432
00:20:09,310 --> 00:20:11,830
Estas la sama formulo
krampoj, vi povas ankaŭ

433
00:20:11,830 --> 00:20:15,170
diri, nur por esti fantazio,
ke io estas theta

434
00:20:15,170 --> 00:20:18,270
de n aŭ theta de iu alia valoro.

435
00:20:18,270 --> 00:20:20,661
Tio simple signifas kiam grandaj
O kaj omega estas samaj.

436
00:20:20,661 --> 00:20:21,910
Nun kio pri selektado speco?

437
00:20:21,910 --> 00:20:23,400
Ni uzu tiun novan vortprovizon.

438
00:20:23,400 --> 00:20:27,407
En selektado speco, kion ni neniam
farante denove kaj denove, kaj denove?

439
00:20:27,407 --> 00:20:29,990
Mi tuj reen tra
la listo, serĉante, kiun?

440
00:20:29,990 --> 00:20:33,260

441
00:20:33,260 --> 00:20:34,730
La plej malgranda nombro.

442
00:20:34,730 --> 00:20:37,560
>> Do kiom da ŝtupoj, kiom
multaj komparoj faris mi

443
00:20:37,560 --> 00:20:43,250
devas fari por eltrovi kiu
la plej eta ero en la listo estis?

444
00:20:43,250 --> 00:20:44,437
n minus 1, dekstra?

445
00:20:44,437 --> 00:20:47,770
Ĉar se mi simple komencu per la unu mi
donita kaj mi komencas kompari lin aŭ ŝin,

446
00:20:47,770 --> 00:20:49,519
tiam li aŭ ŝi, li
aŭ ŝi, li aŭ ŝi, mi

447
00:20:49,519 --> 00:20:52,010
nur duo elementoj
kune n minus 1 fojoj.

448
00:20:52,010 --> 00:20:55,630
Do selektado speco simile prenas
n minus 1 paŝas unuafoje.

449
00:20:55,630 --> 00:20:59,540
>> Kiom da paŝoj preni min al
trovi la dua plej malgranda ero?

450
00:20:59,540 --> 00:21:02,920
n minus 2, ĉar mi estas stulta
se mi dauxre rigardante la samaj homoj

451
00:21:02,920 --> 00:21:06,280
denove se mi jam selektis lin
aŭ ŝi kaj metis ilin en sian lokon.

452
00:21:06,280 --> 00:21:09,270
Kaj la tria paŝo, n
minus 3, tiam n minus 4.

453
00:21:09,270 --> 00:21:11,020
Ni vidis ĉi ŝablono
antaŭe, kaj ja

454
00:21:11,020 --> 00:21:13,460
selektado speco simile
havas supera baro

455
00:21:13,460 --> 00:21:16,210
de n kvadratoj se ni faros tion sumado.

456
00:21:16,210 --> 00:21:19,790
Kio estas ĝia suba baro, selektado speco?

457
00:21:19,790 --> 00:21:25,350
Minimume, kiom da tempo devas selektado
speco prenu, kiel ni difinis en lundo?

458
00:21:25,350 --> 00:21:29,370

459
00:21:29,370 --> 00:21:30,490
Propono du ebloj.

460
00:21:30,490 --> 00:21:32,360
Eble estas n, kiel antaŭe.

461
00:21:32,360 --> 00:21:35,040
Eble ĝi estas n kvadratoj, kiel
nun estas kiel la supera baro.

462
00:21:35,040 --> 00:21:35,874
>> Publiko: n kvadratoj.

463
00:21:35,874 --> 00:21:36,664
SPEAKER: n kvadratoj.

464
00:21:36,664 --> 00:21:37,368
Kial?

465
00:21:37,368 --> 00:21:40,060
>> Publiko: Ĉar vi havas
difini [inaudible].

466
00:21:40,060 --> 00:21:41,510
>> SPEAKER: Ekzakte.

467
00:21:41,510 --> 00:21:45,077
Almenaŭ tiel mi difinis selektado speco
ĝi estis sufiĉe naiva, observu tuj,

468
00:21:45,077 --> 00:21:46,160
trovi la plej malgrandan elementon.

469
00:21:46,160 --> 00:21:47,770
Iru denove, trovi la plej malgrandan elementon.

470
00:21:47,770 --> 00:21:49,490
Iru denove, trovi la plej malgrandan elementon.

471
00:21:49,490 --> 00:21:51,700
Ne estas ia
optimumigo en tie

472
00:21:51,700 --> 00:21:54,350
povus lasi min aborti post
nur n aŭ tia paŝoj.

473
00:21:54,350 --> 00:21:57,080
Do ja, selektado
varon, omega de n kvadratoj.

474
00:21:57,080 --> 00:22:00,667
>> Kio pri inserción varo, ĝi kie mi prenis
kiuj mi donis, kaj tiam mi plopped li

475
00:22:00,667 --> 00:22:01,750
aŭ ŝin en la ĝusta loko?

476
00:22:01,750 --> 00:22:04,958
Poste mi iris al la dua persono,
plopped lin aŭ ŝin en la ĝusta loko.

477
00:22:04,958 --> 00:22:07,910
Tiam la sekvanta persono, plopped
li aŭ ŝi en la ĝusta loko.

478
00:22:07,910 --> 00:22:10,537
Rimarku ke tio estas tre
lineara, por tiel diri.

479
00:22:10,537 --> 00:22:12,620
Mi rekto, mi
ne iras tien kaj reen

480
00:22:12,620 --> 00:22:16,080
Mi neniam rigardis reen vere, sed
kio okazas kiam mi enŝovu li

481
00:22:16,080 --> 00:22:20,302
aŭ ŝin en la komenco de
la listo kiel ni faris en lundo?

482
00:22:20,302 --> 00:22:21,010
Kio okazas?

483
00:22:21,010 --> 00:22:21,510
Yeah?

484
00:22:21,510 --> 00:22:23,122
Publiko: [inaudible].

485
00:22:23,122 --> 00:22:24,830
SPEAKER: Yeah, ke
Estis la kaptisto, dekstra?

486
00:22:24,830 --> 00:22:26,746
Vi eble memoras de
via samklasanoj, se ili

487
00:22:26,746 --> 00:22:29,670
estis farante ajnan movadon
iliaj piedoj, kiuj estis operacio.

488
00:22:29,670 --> 00:22:33,610
Do se tri homoj ĉi tie kaj
la nova persono apartenis vojon tien,

489
00:22:33,610 --> 00:22:37,360
sur longa etapo kiel tiu, kompreneble li
aŭ ŝi povus nur iri al la fino mem.

490
00:22:37,360 --> 00:22:40,074
Sed se ni pensas pri
komputilo kaj tabelo de memoro,

491
00:22:40,074 --> 00:22:41,990
tiuj homoj iras
havi barajar super

492
00:22:41,990 --> 00:22:43,260
por fari lokon al tiu persono.

493
00:22:43,260 --> 00:22:46,930
Kaj tial n minus 1 shufflings,
n minus 2 shufflings, n

494
00:22:46,930 --> 00:22:50,660
minus 3 shufflings estas ĝuste speco de
okazas malantaŭ min, ne antaŭ mi

495
00:22:50,660 --> 00:22:52,710
kiel antaŭe, en iu senso.

499
00:22:52,557 --> 00:22:54,640
Nun kiel flanken, kaj kiel
vi eble vidis en linio

500
00:22:54,640 --> 00:22:57,699
Se vi komencas ŝovas ĉirkaŭ ĉirkaŭ
varoj, ekzistas multaj malsamaj aĵoj

501
00:22:57,699 --> 00:22:59,490
tie ekstere, kelkaj el ili
bona ol aliaj.

502
00:22:59,490 --> 00:23:02,200
Ja, bogosort estas
tio estas ia amuza rigardi supren.

503
00:23:02,200 --> 00:23:06,650
Bogosort prenas aron de
nek nombroj diros ludkartaro de kartoj

504
00:23:06,650 --> 00:23:09,870
hazarde ludkartaro ilin kaj
ĉekojn se ili estas ordigitaj.

505
00:23:09,870 --> 00:23:12,130
Kaj se ne, ĉu denove.

506
00:23:12,130 --> 00:23:14,140
Kaj se ne, ĉu denove.

507
00:23:14,140 --> 00:23:15,440
Se ne, ĉu denove.

508
00:23:15,440 --> 00:23:17,060
Nekredeble stulta.

509
00:23:17,060 --> 00:23:19,520
>> Kaj efektive, se vi legis
kiel la Vikipedia artikolo,

510
00:23:19,520 --> 00:23:21,200
lia alnomo estas stulta varo.

511
00:23:21,200 --> 00:23:25,180
Ĝi eventuale labori,
espereble, donita sufiĉa tempo,

512
00:23:25,180 --> 00:23:28,240
sed tiu kvanto de tempo
povus preni sufiĉe tempo.

513
00:23:28,240 --> 00:23:31,650
Do, se mi povus, ni rapido aferoj
el Mary Beth ekzemplon antaŭe,

514
00:23:31,650 --> 00:23:35,150
por havi kelkaj pli elementoj,
sed du pli procesoroj.

515
00:23:35,150 --> 00:23:37,100
Du homoj, se vi
ne gravas kunigi min.

516
00:23:37,100 --> 00:23:40,972
Kiom proksimume 1 pli tie, kaj
ni go-- neniu tie?

517
00:23:40,972 --> 00:23:41,722
Neniu tie?

518
00:23:41,722 --> 00:23:42,221
OK.

519
00:23:42,221 --> 00:23:44,190
Vi kun la nigraj
ĉemizo, jes, venu malsupren.

520
00:23:44,190 --> 00:23:45,000
Bone, kio estas via nomo?

521
00:23:45,000 --> 00:23:45,720
>> Publiko: Peter.

522
00:23:45,720 --> 00:23:46,100
>> SPEAKER: Kio estas tio?

523
00:23:46,100 --> 00:23:46,766
>> Publiko: Peter.

524
00:23:46,766 --> 00:23:49,450
SPEAKER: Peter David, agrable renkonti vin.

525
00:23:49,450 --> 00:23:53,670
Bone, ni havas Peter tie, se vi
volas veni sur la tablo super tie.

526
00:23:53,670 --> 00:23:54,550
Kaj kio estas via nomo?

527
00:23:54,550 --> 00:23:55,216
>> Publiko: Helena.

528
00:23:55,216 --> 00:23:55,970
SPEAKER: Helena.

529
00:23:55,970 --> 00:23:57,030
OK, agrable renkonti vin.

530
00:23:57,030 --> 00:23:58,060
Elena renkonti Petron.

531
00:23:58,060 --> 00:23:59,170
Petro, Helena.

532
00:23:59,170 --> 00:24:02,290
Kaj ni bezonos Andrew
tien tiel, bonvolu.

533
00:24:02,290 --> 00:24:06,107
Kaj via defio tuj
esti ordigi ludkartaro de kartoj.

534
00:24:06,107 --> 00:24:08,190
Kaj se ne estas familiarizados, ferdeko
de kartoj devus finfine

535
00:24:08,190 --> 00:24:11,064
ordigataj etaĵon ŝatas
tiu kie ni faros la kluboj, tiam

536
00:24:11,064 --> 00:24:13,660
la sxovelilojn, la koroj kaj
diamantoj, el as kiel unu,

537
00:24:13,660 --> 00:24:15,570
tuta vojo supren al reĝo.

538
00:24:15,570 --> 00:24:20,890
>> La kartoj Mi tuj donos al vi
tuj estos 52 en kvanto.

539
00:24:20,890 --> 00:24:23,160
Ni tuj simile
tempo vi, en nur momento.

540
00:24:23,160 --> 00:24:26,410
Ni tuj ĵetos Andrew
supren sur la ekrano tie,

541
00:24:26,410 --> 00:24:28,170
tiel kiel por vidi kiel vi faras tion.

542
00:24:28,170 --> 00:24:31,070
Kaj por ke ĉiuj ĉi
Estas des pli videbla,

543
00:24:31,070 --> 00:24:33,490
Jen estas la kartojn mi havas en Amazon.

544
00:24:33,490 --> 00:24:42,861
Do ili estas jam hazarde
ordo, kaj ni iras al tempo vi.

545
00:24:42,861 --> 00:24:44,610
Kaj ni tuj
teni ĝin reala tiu fojo,

546
00:24:44,610 --> 00:24:47,820
do ni provos premi vin
ĉar alie tiu ricevos teda

547
00:24:47,820 --> 00:24:48,460
rapide.

548
00:24:48,460 --> 00:24:53,860
Se vi povus procedi ordigi 52
elementoj kune tra iuj rimedoj, nun.

549
00:24:53,860 --> 00:25:04,710

550
00:25:04,710 --> 00:25:07,180
>> Kaj denove, kiel ni rigardas tiujn
infanoj faras kion, en la fino

551
00:25:07,180 --> 00:25:10,200
tuj produktos evidentan
Rezulte, pensi vere

552
00:25:10,200 --> 00:25:12,962
kiel ili estas ĉiu faras ĝin,
kiel vi povus priskribi ĝin.

553
00:25:12,962 --> 00:25:15,045
Ĉar denove, ĉi tiuj estas
ĉiuj procezoj, algoritmoj

554
00:25:15,045 --> 00:25:17,090
ke ni prenas por donita kiel homo.

555
00:25:17,090 --> 00:25:22,349
Sed vi verŝajne longe havis
intuicio, longe antaŭ vi eĉ

556
00:25:22,349 --> 00:25:24,390
pripensis preni
komputiko klaso vin

557
00:25:24,390 --> 00:25:27,223
eble havis la intuicion kun
kiu solvi problemojn kiel ĉi.

558
00:25:27,223 --> 00:25:29,560
Sed unufoje vi rekonas
la mastroj kaj komenci

559
00:25:29,560 --> 00:25:32,407
formaligi la paŝojn, per kiu
vi solvi tiujn problemojn,

560
00:25:32,407 --> 00:25:35,490
Vi trovos ke vi povas solvi multe
pli interesaj kaj multe pli kompleksa

561
00:25:35,490 --> 00:25:39,190
problemoj rapide.

562
00:25:39,190 --> 00:25:42,351
Do iu el la publiko, kio estas
almenaŭ unu elemento de la algoritmo

563
00:25:42,351 --> 00:25:43,350
ke oni uzas tie?

564
00:25:43,350 --> 00:25:44,275
>> Publiko: [inaudible]

565
00:25:44,275 --> 00:25:45,150
SPEAKER: Kio estas tio?

566
00:25:45,150 --> 00:25:47,062
Publiko: Per kostumo.

567
00:25:47,062 --> 00:25:47,770
SPEAKER: Per kostumo.

568
00:25:47,770 --> 00:25:50,630
Do unue oni clustering
ĉiuj diamantoj kune

569
00:25:50,630 --> 00:25:52,560
ĝi similas, ĉiuj
koroj kune ŝajnas,

570
00:25:52,560 --> 00:25:56,520
ks, sen respekto
por la nombroj sur la kartoj.

571
00:25:56,520 --> 00:26:00,900
Kaj nun aperas, ekzemple,
esti ordiga ilin per nombro.

572
00:26:00,900 --> 00:26:06,870

573
00:26:06,870 --> 00:26:08,910
Tre bona.

574
00:26:08,910 --> 00:26:12,370
>> Bone, do kion tuj
esti la fina paŝo do tien?

575
00:26:12,370 --> 00:26:16,950
Iam ni havi kvar ordo kostumoj, kio
ĉu ni bezonas fari por la kvar aretoj

576
00:26:16,950 --> 00:26:20,059
por atingi unu
ordo ferdeko, tute simple?

577
00:26:20,059 --> 00:26:21,350
Do ni bezonas kunfandi ilin denove.

578
00:26:21,350 --> 00:26:25,160
>> Do tie estas interesa ideo, ke
denove, daresay, estas tre intuicia eĉ

579
00:26:25,160 --> 00:26:28,140
se vi povus neniam manfrapis
tian etikedon sur ĝi.

580
00:26:28,140 --> 00:26:31,900
Ĉi tiu fundamenta nocio de dividadon
la problemo ne estas en la duono ĉi tempo,

581
00:26:31,900 --> 00:26:33,410
sed almenaŭ en kvar pecojn.

582
00:26:33,410 --> 00:26:36,810
Solvanta preskaux
fundamente identa problemoj

583
00:26:36,810 --> 00:26:40,480
izolite unuj de la aliaj,
kaj tiam kunfandas la rezultojn.

584
00:26:40,480 --> 00:26:46,940

585
00:26:46,940 --> 00:26:50,140
Kaj, bonega, farita.

586
00:26:50,140 --> 00:26:52,140
Bone, granda ronda
de aplaŭdoj, se ni povus.

587
00:26:52,140 --> 00:26:56,480
>> [Aplaŭdo]

588
00:26:56,480 --> 00:26:59,740
>> SPEAKER: Mi havas neniun ideon kion vi
faru kun ili, sed ĉi tie vi iras.

589
00:26:59,740 --> 00:27:01,690
Dankon tiom.

590
00:27:01,690 --> 00:27:04,660
Do ni vidu, du minutoj
ok sekundoj,

591
00:27:04,660 --> 00:27:07,490
Se vi ŝatus defii viajn amikojn.

592
00:27:07,490 --> 00:27:12,160
Kio do tuj
esti forpreni el tiu

593
00:27:12,160 --> 00:27:13,830
ke ni povas utiligi pli ĝenerale?

594
00:27:13,830 --> 00:27:16,080
Nu, pensu reen al
tiu tabelo de nombroj,

595
00:27:16,080 --> 00:27:19,060
kaj pensi reen nun iuj de la
_pseudocode_ ni skribis en la pasinteco,

596
00:27:19,060 --> 00:27:22,080
kaj tio estis por la _pseudocode_ por
solvanta la telefono libro problemon.

597
00:27:22,080 --> 00:27:25,150
Per en _pseudocode_ mi
numeritaj pli metoda vojo

598
00:27:25,150 --> 00:27:28,400
priskribi kiel mi agis tre intuicia
homa algoritmo la dividadon de la telefono

599
00:27:28,400 --> 00:27:31,650
libro en duono, ripeto, ripeti, ripeti,
ĝis mi trovos iun kiel Mike Smith,

600
00:27:31,650 --> 00:27:33,790
se li estas ja en la telefono libro.

601
00:27:33,790 --> 00:27:37,610
>> Sed mi specon de uzataj kion mi vokos
tre ripeta alproksimiĝo tie,

602
00:27:37,610 --> 00:27:42,160
en apartaj avizo linio 8 kaj linio 11.

603
00:27:42,160 --> 00:27:46,750
Tiuj estas evidenteco de ripeta
proksimigo, a looping alproksimiĝo,

604
00:27:46,750 --> 00:27:49,040
ĉar tio estas ĝuste
la konduto induktas.

605
00:27:49,040 --> 00:27:52,910
Tiuj linioj tiel diri iri
linio tri, kaj vi povas ia

606
00:27:52,910 --> 00:27:55,140
pensi, ke en via
Anime kiel estante buklo.

607
00:27:55,140 --> 00:27:59,080
Ĝi diras al vi reiri al paŝo
tri kaj ripetas, denove kaj denove,

608
00:27:59,080 --> 00:28:00,010
kaj denove.

609
00:28:00,010 --> 00:28:04,410
>> Sed kio se ni utiligas ŝlosila ideo
tie ni faris ne la lasta fojo,

610
00:28:04,410 --> 00:28:10,280
kaj simpligi linio 8 kaj
linio 11 kaj iliaj najbaroj

611
00:28:10,280 --> 00:28:12,840
kiel ĝuste tiu, en flava.

612
00:28:12,840 --> 00:28:16,480
Ĝi ne estas fundamente mallongigi
la _pseudocode_ tre multe,

613
00:28:16,480 --> 00:28:20,530
sed ĝi fundamente ŝanĝi
la naturo de mia algoritmo.

614
00:28:20,530 --> 00:28:24,220
Kion mi nun diras
en ŝtupo 7, en ŝtupo 10,

615
00:28:24,220 --> 00:28:29,140
estas serĉi Mike
en la ĝusta sama maniero,

616
00:28:29,140 --> 00:28:31,580
sed nur en la maldekstra
duono aŭ la dekstra duono.

617
00:28:31,580 --> 00:28:33,420
>> Do alivorte, se
Mi komencos de ŝtupo unu,

618
00:28:33,420 --> 00:28:36,150
repreni telefono libro, malfermita al meza
el telefono libro, rigardu nomoj

619
00:28:36,150 --> 00:28:39,010
se Smith estas inter
nomo, nomita Mike, alia

620
00:28:39,010 --> 00:28:44,340
se Smith estas antaŭe en libro, treti sep
serĉi Mike en maldekstran duonon de libro.

621
00:28:44,340 --> 00:28:47,130
Sed tian sentas
ĝi estas lasi min pendantan, dekstra?

622
00:28:47,130 --> 00:28:49,240
En flava, estas
instrukcion, sed kiom mi

623
00:28:49,240 --> 00:28:51,870
serĉi Mike en la maldekstra
duono de la telefono libro?

624
00:28:51,870 --> 00:28:54,210
Kie mi havas
algoritmo per kiu mi

625
00:28:54,210 --> 00:28:57,100
povas serĉi iu kiel Mike Smith?

626
00:28:57,100 --> 00:28:58,980
Nu, ĝi estas fiksrigardanta ni en la vizaĝo.

627
00:28:58,980 --> 00:29:03,090
Mi povas laŭvorte uzi la ĝustajn samajn
programo efike suprenirantaj al la supro

628
00:29:03,090 --> 00:29:06,490
denove kaj re-funkciado
la samaj linioj de kodo.

629
00:29:06,490 --> 00:29:10,610
>> Do kvankam tiu devus senti
kiel iom de cikla difino

630
00:29:10,610 --> 00:29:13,480
kie vi respondi ies
demando por nur ia demandante

631
00:29:13,480 --> 00:29:15,990
La sama demando denove,
kiel kial, kial, kial?

632
00:29:15,990 --> 00:29:21,580
La realaĵo estas ĉar ni malfacile kodita
kelkaj specialaj linioj, ŝtupo 4,

633
00:29:21,580 --> 00:29:25,320
kio estas se kaj ŝtupo 12, kiu
estas efektive alia branĉo,

634
00:29:25,320 --> 00:29:30,120
ĉar ni havas tiujn stopgap mezuroj,
tiu algoritmo finiĝi se ni

635
00:29:30,120 --> 00:29:32,050
trovi Mike, aŭ se ni ne faras.

636
00:29:32,050 --> 00:29:36,810
Sed en ŝtupo 7 kaj 10 nun ni havas
kion ni nomas rekursia algoritmo.

637
00:29:36,810 --> 00:29:40,420
Kaj rekursio estas ja potenca ideo
ke estas iom menso kliniĝante al la komenco,

638
00:29:40,420 --> 00:29:42,500
ke ni povas nun apliki jene.

639
00:29:42,500 --> 00:29:46,600
>> Kunfandi speco estos la lasta varo ke
Ni rigardu, almenaŭ en klaso formale.

640
00:29:46,600 --> 00:29:50,040
Kaj estas fundamente malsama
el tiuj lastaj tri, kaj certe

641
00:29:50,040 --> 00:29:52,140
lasta kvar se ni inkludas bogosort.

642
00:29:52,140 --> 00:29:54,810
Jen la _pseudocode_ por merge varo.

643
00:29:54,810 --> 00:30:00,170
Kiam la enigo de n elementoj, tiel donita
tabelo de amplekso n, se n estas malpli ol 2,

644
00:30:00,170 --> 00:30:01,040
reveni.

645
00:30:01,040 --> 00:30:03,610
Do kial mi havas tiun
prudento kontroli unuan?

646
00:30:03,610 --> 00:30:09,477
Kio implico se mi transdonos vin
tabelo kies longo n estas malpli ol 2?

647
00:30:09,477 --> 00:30:11,060
Ĝi estas jam ordo, evidente, dekstra?

648
00:30:11,060 --> 00:30:13,640
Ĉar la listo aŭ havas
unu elemento, kiu estas bagatele

649
00:30:13,640 --> 00:30:15,180
ordo ĉar estas
la sola afero tie.

650
00:30:15,180 --> 00:30:18,138
Aŭ, ĝi estas de grandeco nulo kiu signifas
nenio estas ordigi, do nature

651
00:30:18,138 --> 00:30:18,720
estas ordigitaj.

652
00:30:18,720 --> 00:30:20,410
Ekzistas nur nenio malĝusta tie.

653
00:30:20,410 --> 00:30:22,310
Do jen nia tn baza kazo.

654
00:30:22,310 --> 00:30:24,440
>> Tio estas simila en spirito
kion ni faris kun Mike.

655
00:30:24,440 --> 00:30:26,023
Se Mike en la telefono libro, nomi lin.

656
00:30:26,023 --> 00:30:27,740
Se li ne estas tie, rezigni.

657
00:30:27,740 --> 00:30:31,240
Ĝi estas tiel nomata baza kazo, certigi
tiu algoritmo al la fino de la tago

658
00:30:31,240 --> 00:30:33,540
ĉesos en certaj cirkonstancoj.

659
00:30:33,540 --> 00:30:37,890
>> Sed jen la salto de fido nun alia,
ordigi la maldekstra duono de la elementoj,

660
00:30:37,890 --> 00:30:39,740
tiam ordigi dekstre
duonon de la elementoj,

661
00:30:39,740 --> 00:30:41,189
kaj tiam kunfandi la ordo duonoj.

662
00:30:41,189 --> 00:30:43,230
Kaj tie estas kie sentas
kiel ni copping ekstere.

663
00:30:43,230 --> 00:30:46,900
Mi petis vin ordigi
n elementoj, kaj mi

664
00:30:46,900 --> 00:30:50,712
dirante, OK, ĉu ĝin ordiga
maldekstren kaj ordigo dekstre.

665
00:30:50,712 --> 00:30:52,420
Sed mi diras unu
alia afero, kaj tiu

666
00:30:52,420 --> 00:30:55,530
estas la ŝlosilo temo ŝajnas
en la intuicio tiel multe,

667
00:30:55,530 --> 00:30:57,380
tie estas tio tria ŝtupo de kunfando.

668
00:30:57,380 --> 00:31:00,430
Kiun kvankam
Ŝajnas tiel muta en spirito,

669
00:31:00,430 --> 00:31:02,320
kiel nur kunfandi aferoj
kune, ŝajnas

670
00:31:02,320 --> 00:31:05,380
esti ŝlosila paŝo al la
reassembly de du problemoj

671
00:31:05,380 --> 00:31:07,330
dividigxis finfine duono.

672
00:31:07,330 --> 00:31:12,090
>> Do kunfandi speco, ni faru tion, se vi
humuron mi, kun pli pruvo,

673
00:31:12,090 --> 00:31:14,730
nur por ke ni havas iun
nombroj labori kun.

674
00:31:14,730 --> 00:31:19,470
Ĉu mi povas interŝanĝi ok streso
buloj por ok personoj?

675
00:31:19,470 --> 00:31:29,320
Bone, kio pri vi tri, vi kvar
en ĉi tiu sekcio, kvin, ses, kaj ni

676
00:31:29,320 --> 00:31:30,720
cxu 7, 8, venu supren.

677
00:31:30,720 --> 00:31:35,120

678
00:31:35,120 --> 00:31:36,520
OK, yeah OK.

679
00:31:36,520 --> 00:31:38,640
Minus 8, tie ni iru, plus 1.

680
00:31:38,640 --> 00:31:39,150
Bonega.

681
00:31:39,150 --> 00:31:42,000
Ĉiuj rajtas veni supren, ni
rapide doni vin nombroj.

682
00:31:42,000 --> 00:31:50,800
Numeron du, numero tri, numero kvar,
numero kvin, ses, sep, ok.

683
00:31:50,800 --> 00:31:52,140
Mi faris ok ĝuste tiu tempo.

684
00:31:52,140 --> 00:31:56,390
>> OK, do iru antaŭen se vi povis, kaj
ni ordigi en la originalan ordon

685
00:31:56,390 --> 00:31:59,810
ke ni havis hieraŭ kiuj aspektis
kiel tiu, se vi ne ĝenas.

686
00:31:59,810 --> 00:32:03,620
Kaj ni faros antaŭ la tablo.

687
00:32:03,620 --> 00:32:06,510
Bone, do kunfandi varo.

688
00:32:06,510 --> 00:32:08,820
Jen kie okazas
akiri ia interesa,

689
00:32:08,820 --> 00:32:12,800
ĉar mi ŝajnas esti donante mem
tiom malpli informo hodiaŭ.

690
00:32:12,800 --> 00:32:15,149
>> Do kunfandi speco unue
sur eniro de n elementoj,

691
00:32:15,149 --> 00:32:18,440
kaj evidente ne malpli ol du, ĝi estas
ok, do mi havas iom pli da laboro por fari.

692
00:32:18,440 --> 00:32:21,140
Do nun mense ni kiel klaso
nun estas en la alia branĉo,

693
00:32:21,140 --> 00:32:22,540
kio signifas tri paŝoj.

694
00:32:22,540 --> 00:32:25,017
Unue, mi devas ordigi la
maldekstra duono de la eroj.

695
00:32:25,017 --> 00:32:26,350
Do kiel mi iros en fari ĉi tion?

696
00:32:26,350 --> 00:32:28,950
Nu, mi tuj speco de
mense dividi la liston ĉi tie,

697
00:32:28,950 --> 00:32:30,700
vi ne devas
fizike movi kaj mi

698
00:32:30,700 --> 00:32:33,180
tuj enfokusigi nur en la
maldekstra duono de la elementoj tie.

699
00:32:33,180 --> 00:32:36,770
Do kiel mi iros sur ordiga
listo nun de grandeco kvar?

700
00:32:36,770 --> 00:32:38,730
Kio estas mia algoritmo?

701
00:32:38,730 --> 00:32:42,580
Unue mi kontrolu estas n malpli ol du ne,
do mi povas daŭri al la alia bloko denove.

702
00:32:42,580 --> 00:32:43,900
Ordigi maldekstra duono de elementoj.

703
00:32:43,900 --> 00:32:45,608
>> Do nun denove, mense,
kaj ĉi tiu estas kie

704
00:32:45,608 --> 00:32:49,550
Vi devas accrue multan
mensa historio, se vi volas.

705
00:32:49,550 --> 00:32:51,940
Nun mi ordiga maldekstre
duonon de la maldekstra duono.

706
00:32:51,940 --> 00:32:57,000
Bone, do nun mi vokas mian saman merge
ordiga algoritmo, estas N malpli ol du?

707
00:32:57,000 --> 00:33:00,590
Ne, tio estas du, do mi devas ordigi
maldekstre duono, kaj la dekstran duonon.

708
00:33:00,590 --> 00:33:02,042
Do tie ni iru, ordigi la maldekstra duono.

709
00:33:02,042 --> 00:33:03,750
Kial vi ne simple
preni unu paŝon antaŭen.

710
00:33:03,750 --> 00:33:04,415
Kio estas via nomo?

711
00:33:04,415 --> 00:33:04,860
>> Publiko: Darren.

712
00:33:04,860 --> 00:33:05,260
>> SPEAKER: Dan.

713
00:33:05,260 --> 00:33:06,040
Dan tretis antaŭen.

714
00:33:06,040 --> 00:33:06,748
>> Publiko: Darren.

715
00:33:06,748 --> 00:33:09,000
SPEAKER: Darren, farita.

716
00:33:09,000 --> 00:33:10,090
Ĉu vi diras Darren aŭ Dan?

717
00:33:10,090 --> 00:33:10,550
>> Publiko: Darren.

718
00:33:10,550 --> 00:33:11,216
>> SPEAKER: Darren.

719
00:33:11,216 --> 00:33:14,422
OK, Darren tretis
antaŭen kaj li estas nun ordo.

720
00:33:14,422 --> 00:33:16,130
Kaj tio estas preskaŭ
inane aserton, dekstra?

721
00:33:16,130 --> 00:33:18,862
Mi ne vere ŝajnas esti atingante
nenio, sed ni procedi.

722
00:33:18,862 --> 00:33:20,820
Nun lasu min ordigi dekstre
duono de la eroj.

723
00:33:20,820 --> 00:33:21,200
Kio estas via nomo?

724
00:33:21,200 --> 00:33:21,690
>> Publiko: Luko.

725
00:33:21,690 --> 00:33:22,273
>> SPEAKER: Luko.

726
00:33:22,273 --> 00:33:23,400
Venu, paŝon antaŭen.

727
00:33:23,400 --> 00:33:25,640
Done mi ordigitaj Luko.

728
00:33:25,640 --> 00:33:28,570
La maldekstra duono estas nun ordo kaj
la dekstran duonon nun ordo,

729
00:33:28,570 --> 00:33:30,770
sed denove, estas ŝlosila paŝo tie.

730
00:33:30,770 --> 00:33:32,940
Kion mi apud bezonas fari?

731
00:33:32,940 --> 00:33:33,941
Kunfandi la ordo duonoj.

732
00:33:33,941 --> 00:33:36,648
Nun ni iras al nur devas
ĉiuj reen tiamaniere,

733
00:33:36,648 --> 00:33:38,620
ĉar mi specon de bezoni
iu nulo spaco.

734
00:33:38,620 --> 00:33:40,411
Estas preskaŭ kiel tiuj
knaboj sur tablo,

735
00:33:40,411 --> 00:33:42,460
Mi bezonas ĉambron
movi ilin cxirkauxe.

736
00:33:42,460 --> 00:33:44,170
Do mi tuj kunfandi
vi uloj rigardante

737
00:33:44,170 --> 00:33:45,960
ĉe la maldekstra duono kaj la dekstran duonon.

738
00:33:45,960 --> 00:33:48,740
Kaj kiu evidente venas unue,
maldekstra duono aŭ dekstra duono?

739
00:33:48,740 --> 00:33:52,710
Do dekstran duonon, do ni movi Luko super
tien por Darren originala pozicio.

740
00:33:52,710 --> 00:33:57,640
Kaj nun kunfandi sian maldekstran duonon en,
Darren tuj iru dekstren tie.

741
00:33:57,640 --> 00:33:59,750
>> Do sentas preskaŭ
bobelo speco efekto,

742
00:33:59,750 --> 00:34:02,482
sed mia fundamenta algoritmo,
tre malsama tiu tempo.

743
00:34:02,482 --> 00:34:04,815
Sed nun estas kie aĵoj oni
iom ĝena ĉar vi

744
00:34:04,815 --> 00:34:06,810
devas malantaŭenigi mense
kien mi chesos.

745
00:34:06,810 --> 00:34:09,893
Mi ĵus kunfandis la ordo duonoj,
kio signifas mi kie en mia algoritmo?

746
00:34:09,893 --> 00:34:12,229

747
00:34:12,229 --> 00:34:13,770
Mi devas ordigi la dekstran duonon, ĉu ne?

748
00:34:13,770 --> 00:34:15,910
>> Se vi malantaŭenigi, laŭvorte
sur la video, vi

749
00:34:15,910 --> 00:34:18,339
vidu ke ni alvenis al tiu
punkto de Luko kaj Darren

750
00:34:18,339 --> 00:34:21,370
per ordiga maldekstre
duonon de la maldekstra duono.

751
00:34:21,370 --> 00:34:23,430
Tiam ni kunfandis tiujn
ordo duonoj, kiuj

752
00:34:23,430 --> 00:34:27,941
signifas la sekva paŝo estas speco la
dekstran duonon de la maldekstra duono.

753
00:34:27,941 --> 00:34:29,649
Bone, do ni
fari tion pli rapide.

754
00:34:29,649 --> 00:34:33,282
Bone, ses, mi tuj pretendi
vi estas nun ordo, venu pluen.

755
00:34:33,282 --> 00:34:33,990
Kio estas via nomo?

756
00:34:33,990 --> 00:34:34,589
>> Publiko: Adriano.

757
00:34:34,589 --> 00:34:35,200
>> SPEAKER: Adriano.

758
00:34:35,200 --> 00:34:36,010
Adriano nun ordo.

759
00:34:36,010 --> 00:34:36,450
Kaj kio estas via nomo?

760
00:34:36,450 --> 00:34:37,080
>> Publiko: Alex.

761
00:34:37,080 --> 00:34:38,379
>> SPEAKER: Alex estas nun ordo.

762
00:34:38,379 --> 00:34:40,750
Maldekstra duono, dekstran duonon,
kio estas la fina paŝo?

763
00:34:40,750 --> 00:34:41,250
Kunfandi.

764
00:34:41,250 --> 00:34:44,310
Bela bagatela, do mi estas
tuj kunfandos en ses,

765
00:34:44,310 --> 00:34:46,930
preni retropaŝo,
ok, preni retropaŝo.

766
00:34:46,930 --> 00:34:49,530
Kaj nun rimarki ĉi estas
utila takeaway, kio

767
00:34:49,530 --> 00:34:53,930
nun estas vera pri la maldekstran duonon de la
lerta, sendepende de kiel ni komencis?

768
00:34:53,930 --> 00:34:55,090
Ĝi estas ordigitaj.

769
00:34:55,090 --> 00:34:57,750
>> Nun ĝi ne estas ordo en
la granda skemo de aferoj,

770
00:34:57,750 --> 00:35:00,250
sed estas ordo sendepende
de la alia duono.

771
00:35:00,250 --> 00:35:04,100
Nun kio paŝo mi sur se mi konservos
rewinding kiel la historio komencis?

772
00:35:04,100 --> 00:35:05,680
Nun mi devas ordigi la dekstran duonon.

773
00:35:05,680 --> 00:35:07,630
Do nun ni estas vojo reen ĉe
la komenco de la rakonto,

774
00:35:07,630 --> 00:35:08,921
kaj ni faru tion pli rapide.

775
00:35:08,921 --> 00:35:11,320
Do mi tuj ordigi la
dekstran duonon de la tuta listo.

776
00:35:11,320 --> 00:35:13,060
Kio estas la sekva paŝo?

777
00:35:13,060 --> 00:35:15,840
Ordigi la maldekstra duono de la dekstra duono.

778
00:35:15,840 --> 00:35:18,715
Ordigi la maldekstra duono de la
maldekstra duono de la dekstra duono.

779
00:35:18,715 --> 00:35:19,590
Kaj kio estas via nomo?

780
00:35:19,590 --> 00:35:20,230
>> Publiko: Omar.

781
00:35:20,230 --> 00:35:21,970
>> SPEAKER: Omar, paŝas antaŭen farita.

782
00:35:21,970 --> 00:35:22,860
Maldekstra duono estas ordigitaj.

783
00:35:22,860 --> 00:35:23,330
Kaj kio estas via nomo?

784
00:35:23,330 --> 00:35:23,820
>> Publiko: Chris.

785
00:35:23,820 --> 00:35:25,620
>> SPEAKER: Chris, paŝon
antaŭen, vi nun ordo.

786
00:35:25,620 --> 00:35:27,010
Kio estas la klavo paŝo nun?

787
00:35:27,010 --> 00:35:27,510
Kunfandi.

788
00:35:27,510 --> 00:35:30,509
Do oni tuj eniru loko
ĉi tie, se vi povus preni retropaŝo,

789
00:35:30,509 --> 00:35:32,930
kaj tri tuj
preni retropaŝon, kunfandi.

790
00:35:32,930 --> 00:35:38,080
Tiel la maldekstra duono de la
dekstra duono, estas nun ordo.

791
00:35:38,080 --> 00:35:41,747
Sincere, ĉi tiu algoritmo sentas nin
malŝparas vojon pli tempo ol antaŭe,

792
00:35:41,747 --> 00:35:44,830
sed se ni faris tion en reala tempo, ni
vidu kion takeaways tuj estos.

793
00:35:44,830 --> 00:35:47,970
Nun mi estas preta, dekstra
duono de la dekstra duono,

794
00:35:47,970 --> 00:35:50,170
lasu min antaŭeniri kaj ordigi la maldekstra duono.

795
00:35:50,170 --> 00:35:51,482
Paŝu antaŭen, kio estas via nomo?

796
00:35:51,482 --> 00:35:52,190
Publiko: Ramsey.

797
00:35:52,190 --> 00:35:53,210
SPEAKER: Ramsey estas nun ordo.

798
00:35:53,210 --> 00:35:53,570
Kio estas via nomo?

799
00:35:53,570 --> 00:35:54,200
>> Publiko: Marina.

800
00:35:54,200 --> 00:35:57,033
>> SPEAKER: Marina estas nun ordo kiel
bone, se vi preni unu paŝon antaŭen.

801
00:35:57,033 --> 00:36:00,690
Ŝlosilo paŝo tie nun kunfandi, mi
tuj deŝiri de miaj du listojn,

802
00:36:00,690 --> 00:36:01,720
maldekstra kaj dekstra.

803
00:36:01,720 --> 00:36:05,150
Kvin tuj veni unue
kaj sep venos baldaŭ.

804
00:36:05,150 --> 00:36:06,410
Kaj denove, tio estas intenca.

805
00:36:06,410 --> 00:36:08,535
La fakto ke ili estas prenante
paŝas antaŭen kaj reen

806
00:36:08,535 --> 00:36:12,997
celas reprezenti ke ni ne povas
do tiu algoritmo en loko tiel facile

807
00:36:12,997 --> 00:36:15,830
kiel bobelo speco, kaj selektado speco,
kaj inserción speco kie ni ĵus

808
00:36:15,830 --> 00:36:16,960
tenis interŝanĝante popolo.

809
00:36:16,960 --> 00:36:19,940
Mi laŭvorte bezonas ian
de nulo papero en kiu

810
00:36:19,940 --> 00:36:21,827
meti tiujn ulojn
dum mi faras la fandado,

811
00:36:21,827 --> 00:36:23,410
kaj tiam mi povas meti ilin en lokon.

812
00:36:23,410 --> 00:36:27,260
Kaj tio estas ŝlosilo ĉar mi uzas
nova rimedo, spaco, ne nur tempon.

813
00:36:27,260 --> 00:36:28,270
>> OK, tiu estas mirinda.

814
00:36:28,270 --> 00:36:32,050
Maldekstra duono estas ordo, dekstra duono estas
ordo, nun ke ŝlosilo kunfando paŝo.

815
00:36:32,050 --> 00:36:33,450
Kiamaniere mi povos kunfandi ĉi?

816
00:36:33,450 --> 00:36:35,470
Do se vi sekvas mian
maldekstra mano kaj dekstren

817
00:36:35,470 --> 00:36:38,930
Mi tuj atentigi mia maldekstra mano
ĉe la maldekstra duono, mia dekstra mano

818
00:36:38,930 --> 00:36:42,680
ĉe la dekstra duono, kaj nun mi devas
decidi paŝo post paŝo, kiun por enkunigi.

819
00:36:42,680 --> 00:36:44,650
Kiu evidente venas unue?

820
00:36:44,650 --> 00:36:45,150
Nombro unu.

821
00:36:45,150 --> 00:36:47,327
Do venu tien,
jen nia scratch pad.

822
00:36:47,327 --> 00:36:49,910
Do nun la numero unu, kaj avizo
kion mi faru kun mia dekstra mano,

823
00:36:49,910 --> 00:36:54,152
Mi iras al movi mian dekstran manon unu
Transpaŝi atentigi nombro tri,

824
00:36:54,152 --> 00:36:55,860
kaj nun mi devas fari
la sama decido.

825
00:36:55,860 --> 00:36:58,387
Kaj efektive staras dekstre en
antaŭ Luko tie se vi povus,

826
00:36:58,387 --> 00:36:59,720
ĉar tio estas nia scratch pad.

827
00:36:59,720 --> 00:37:00,610
Do kiu venas tuj?

828
00:37:00,610 --> 00:37:05,000
Ni havas Luke kun numero du
aŭ Chris kun numero tri.

829
00:37:05,000 --> 00:37:07,460
Evidente Luko, nombro
du, do vi venis.

830
00:37:07,460 --> 00:37:11,270
>> Sed mia maldekstra mano nun tuj
esti incremented noti al Darren,

831
00:37:11,270 --> 00:37:15,160
kaj jen la ŝlosilo forpreni kun
kunfando, Mi iras por subteni fari tion,

832
00:37:15,160 --> 00:37:17,340
Evidente, se vi speco
de sekvi la logikon.

833
00:37:17,340 --> 00:37:19,670
Sed miaj manoj estas neniam
tuj iru malantaŭen,

834
00:37:19,670 --> 00:37:23,861
kio signifas ke mi nur iam movanta al
maldekstren kun mia kuniĝo procezo,

835
00:37:23,861 --> 00:37:26,360
kaj ke tuj estos ŝlosilo
nian analizon en nur momento.

836
00:37:26,360 --> 00:37:27,859
>> Do nun ni finos tiun supren rapide.

837
00:37:27,859 --> 00:37:31,650
Do tri venas proksima,
tiam kvar venas proksima,

838
00:37:31,650 --> 00:37:38,750
kaj nun kvin venas proksima, do ses,
kaj sep, kaj tiam fine ok.

839
00:37:38,750 --> 00:37:42,960
Sentas la plej malrapida algoritmo
tamen, sed ne se ni reale

840
00:37:42,960 --> 00:37:45,510
kuri al la sama speco
de horloĝo rapido, tiel

841
00:37:45,510 --> 00:37:48,106
paroli kun la sama
tiktakas horloĝo kiel antaŭe.

842
00:37:48,106 --> 00:37:48,605
Kial?

843
00:37:48,605 --> 00:37:51,100
Nu, Ni prenu
rigardi la rezultita fino.

844
00:37:51,100 --> 00:37:56,990
>> Ni reiru tien, lasu min
elsxiros manifestacio vide

845
00:37:56,990 --> 00:37:59,030
kion ni ĵus faris.

846
00:37:59,030 --> 00:38:06,110
Zoom tie, sur tiu
paĝo ĉi tie, dirante Firefox

847
00:38:06,110 --> 00:38:08,200
ke ni volas enviciĝi
en tiu skatolo, ni

848
00:38:08,200 --> 00:38:11,260
diru bobelo varo, kun kiu
ni estas nun bone konata,

849
00:38:11,260 --> 00:38:14,130
selektado speco, kiu estas alia
sufiĉe simpla unu,

850
00:38:14,130 --> 00:38:18,250
Nun hodiaŭa merge varon, kiun
estos nia klimataj finaĵo.

851
00:38:18,250 --> 00:38:21,530
La kialo postrestis tiel plu
tien kun homoj kaj mi parole estas,

852
00:38:21,530 --> 00:38:23,480
Evidente, mi klarigante ĉiu paŝo.

853
00:38:23,480 --> 00:38:26,920
Sed se vi simple ekzekuti ĉi, multe
kiel ni faris bobelo varo kaj selektado

854
00:38:26,920 --> 00:38:30,890
speco ne nur vide, horloĝo
kiom multe pli efike

855
00:38:30,890 --> 00:38:33,330
tio utiligante de
divido kaj konkerante

856
00:38:33,330 --> 00:38:39,150
povas kiam aplikita al aro de datumoj kiuj estas
eĉ grandeco ok, sed eĉ tiel,

857
00:38:39,150 --> 00:38:39,970
multe pli granda.

858
00:38:39,970 --> 00:38:44,585
Mi donos al vi kunigi varon, flankon ĉe
flanke kun tiuj aliaj algoritmoj.

859
00:38:44,585 --> 00:38:56,364

860
00:38:56,364 --> 00:38:58,530
Tiu tuj alvenos dolora
rapide, kaj la finaĵo

861
00:38:58,530 --> 00:39:00,890
ne estas aparte klimataj,
ili nur finos ordo.

862
00:39:00,890 --> 00:39:05,280
Sed la ŝlosilo forpreni estas ke
aspektas kiel multe pli rapida kunfandi speco

863
00:39:05,280 --> 00:39:08,110
estis, krom se vi kredas ke mi estas
nur ia rompado kun vi.

864
00:39:08,110 --> 00:39:13,100
Se ni faros ĉi tiu lasta fojo,
Ni reŝargi tiun, ni iru reen

865
00:39:13,100 --> 00:39:14,960
kaj elekti bobelo speco,
kaj ĝuste por piedbatoj,

866
00:39:14,960 --> 00:39:17,330
ni elektos inserción
speco, nur por bonan mezuron.

867
00:39:17,330 --> 00:39:20,020
Kaj ĉi tiu fojo, ni
elekti merge varo kaj ni

868
00:39:20,020 --> 00:39:21,595
reale kuri tiuj flank.

869
00:39:21,595 --> 00:39:24,140

870
00:39:24,140 --> 00:39:26,930
>> Kaj ne, fakte, bonŝancaĵo.

871
00:39:26,930 --> 00:39:31,140
Kion mi efektive farata Mi havas
dividita mia eniro en la duono, denove,

872
00:39:31,140 --> 00:39:32,240
kaj denove, kaj denove.

873
00:39:32,240 --> 00:39:35,590
Kaj tie estas nur tiom da fojoj vi povas
dividi via enigo en duonoj, maldekstra

874
00:39:35,590 --> 00:39:36,240
kaj dekstra.

875
00:39:36,240 --> 00:39:39,425
Kio estas la formulo kiu ni daŭre vidas
kiu priskribas la divido en duono

876
00:39:39,425 --> 00:39:41,050
denove kaj denove, kaj denove, kaj denove?

877
00:39:41,050 --> 00:39:41,890
>> Publiko: Log n.

878
00:39:41,890 --> 00:39:42,760
>> SPEAKER: Log n.

879
00:39:42,760 --> 00:39:46,300
Sed tiam ekzistas unu alia ŝlosilo paŝo,
tiu algoritmo ne log n paŝoj.

880
00:39:46,300 --> 00:39:48,992
Se ĝi nur ensaluti n paŝoj,
ni estus en la sama problemo

881
00:39:48,992 --> 00:39:51,200
kiel antaŭe, kie ni ne povas esti
certe ĉio ordo.

882
00:39:51,200 --> 00:39:54,480
Vi devas minimume rigardi n elementoj
certi n elementoj estas ordigitaj,

883
00:39:54,480 --> 00:39:55,950
alie ĝi estas salto de fido.

884
00:39:55,950 --> 00:39:59,810
>> Do estas minimume log n paŝojn, sed
kio pri tiu klavo kuniĝo ŝtupo

885
00:39:59,810 --> 00:40:04,370
kie mi kunfandis mia maldekstra duono kaj dekstra
duono kaj marŝis trans la scenejo?

886
00:40:04,370 --> 00:40:06,980
Kiom da paŝoj estas ke kunfandi?

887
00:40:06,980 --> 00:40:10,150
Estas n, sed mi ne faris nur
kunfandi la fina tempo.

888
00:40:10,150 --> 00:40:15,089
Sur ĉiu el tiuj neston alvokojn, sur ĉiu
de tiuj neston kunigoj Mi ankoraŭ ordo.

889
00:40:15,089 --> 00:40:18,380
Mi kunfandis tiujn du knaboj, tiam tiuj du
Knaboj, tiam tiuj du onkloj ktp.

890
00:40:18,380 --> 00:40:19,955
>> Do mi kunfando denove kaj denove.

891
00:40:19,955 --> 00:40:20,580
Kiom da fojoj?

892
00:40:20,580 --> 00:40:23,510
Do ĉiufoje mi dividis la
lerta en duono, mi faris merge.

893
00:40:23,510 --> 00:40:25,460
Dishaku la listo en duono, fari merge.

894
00:40:25,460 --> 00:40:28,570
Do se dividante la elenco
povas fari log n fojojn,

895
00:40:28,570 --> 00:40:33,880
kaj la kombino finfine prenas n
paŝojn, kio povus esti nun la supra

896
00:40:33,880 --> 00:40:37,000
baro sur la kurado
tempo de nia algoritmo?

897
00:40:37,000 --> 00:40:37,980
n log n.

898
00:40:37,980 --> 00:40:40,560
>> Kaj efektive, jen kion
ni atingis tien.

899
00:40:40,560 --> 00:40:44,650
Do la sento ke vi vidu vide kiam
tiujn tri aferojn kuras flanko ĉe flanko

900
00:40:44,650 --> 00:40:47,930
Estas n kvadratoj kontraŭ n
kvadrato kontraŭ n log n.

901
00:40:47,930 --> 00:40:51,010
Kio fundamente ni vidos,
Ne nur hodiaŭ sed en la estonteco,

902
00:40:51,010 --> 00:40:52,760
estas multe, multe pli rapida.

903
00:40:52,760 --> 00:40:56,010
A ĉirkaŭvojon de aplaŭdoj por tiuj infanoj,
Mi repagos kun streso pilkojn.

904
00:40:56,010 --> 00:41:00,260
Ni adjourn tie hodiaŭ, kaj
Ni vidos vin lunde.

905
00:41:00,260 --> 00:41:02,255