1
00:00:00,000 --> 00:00:11,100
>> [MUZIKO ludi]

2
00:00:11,100 --> 00:00:11,490
>> DAVID J. Malan: Bone.

3
00:00:11,490 --> 00:00:12,170
Do bonvenigas dorso.

4
00:00:12,170 --> 00:00:15,180
Ĉi tiu estas CS50, kaj la estas
la finon de semajno tri.

5
00:00:15,180 --> 00:00:17,770
>> Do memoras en la lastaj semajnoj,
ni estis pasi sufiĉe da

6
00:00:17,770 --> 00:00:20,820
tempo sur C, en programado, en sintakso.

7
00:00:20,820 --> 00:00:24,680
Kaj estas tute normala, se vi ankoraŭ
baraktante kun Problemo Serio 2, esti

8
00:00:24,680 --> 00:00:25,950
banging vian kapon kontraŭ la muro.

9
00:00:25,950 --> 00:00:28,310
Ĝi estas kamufla-aspekta erarmesaĝojn
kaj bugs kiu vi

10
00:00:28,310 --> 00:00:29,220
ne povas sufiĉe persekuti malsupren.

11
00:00:29,220 --> 00:00:32,310
Ĉar, ripozi certigis, ke en nur
kelkaj semajnoj tempo vi retrorigardas la

12
00:00:32,310 --> 00:00:35,930
aĵoj kiel Cezaro, kaj [? V-genair,?]
eble eĉ Crack, kaj

13
00:00:35,930 --> 00:00:40,050
rimarki kiom multe vi venis
en mallonga periodo de tempo.

14
00:00:40,050 --> 00:00:43,670
Do se tiu estas ajna konsolo,
pendigi tien nun.

15
00:00:43,670 --> 00:00:46,610
>> Hodiaŭ, tamen, ni komencos transiro
al aĵoj pli alta nivelo.

16
00:00:46,610 --> 00:00:49,820
Kaj ni komencas preni por koncedis ke
you guys scipovas plani, aŭ

17
00:00:49,820 --> 00:00:52,090
Almenaŭ la komencoj de
ke komforto nivelo.

18
00:00:52,090 --> 00:00:56,520
Kaj ni komencas konsideri kiel ni povas
irad desegni programoj pli

19
00:00:56,520 --> 00:00:57,440
efike.

20
00:00:57,440 --> 00:01:01,090
Kiel ni povas iri optimizando la
efikeco de nia algoritmoj, kaj

21
00:01:01,090 --> 00:01:03,110
ĝenerale solvanta pli
interesaj problemoj.

22
00:01:03,110 --> 00:01:06,850
Kaj komencante preni por koncedis ke,
se ni volis, ni povus programi ĉe ajna

23
00:01:06,850 --> 00:01:08,350
el la ekzemploj havas en menso.

24
00:01:08,350 --> 00:01:11,430
Do hodiaŭ, ni ne tuŝas la klavaro
por ajna formo de kodo.

25
00:01:11,430 --> 00:01:15,150
Estos multe pli alta nivelo, kaj
fine, pri problemo-solvado.

26
00:01:15,150 --> 00:01:20,490
>> Do por atingi tiun punkton, mi proponas
ke la sekvaj sep

27
00:01:20,490 --> 00:01:24,290
ortanguloj reprezentas sep pordoj, malantaŭ
kio estas tuta aro da

28
00:01:24,290 --> 00:01:26,340
nombroj, inter kiuj estas la nombro 50.

29
00:01:26,340 --> 00:01:30,470
Lasu min projekti tion en ĉi tiu
ekrano tie ankaŭ.

30
00:01:30,470 --> 00:01:36,770
Kaj proponas ke ni bezonas volontulon por
helpi min trovi nombro antaŭ

31
00:01:36,770 --> 00:01:38,140
la interreto tie vidi.

32
00:01:38,140 --> 00:01:40,755
Venu supren, en la rozkoloraj.

33
00:01:40,755 --> 00:01:43,050
Ĉio bone.

34
00:01:43,050 --> 00:01:43,930
Kio estas via nomo?

35
00:01:43,930 --> 00:01:44,850
>> Jennifer: [inaudibles]

36
00:01:44,850 --> 00:01:45,170
>> DAVID J. Malan: Pardonu?

37
00:01:45,170 --> 00:01:45,860
>> Jennifer: Jennifer.

38
00:01:45,860 --> 00:01:46,390
>> DAVID J. Malan: Jennifer.

39
00:01:46,390 --> 00:01:46,980
Bone, Jennifer.

40
00:01:46,980 --> 00:01:47,630
Nice to meet you.

41
00:01:47,630 --> 00:01:48,370
Venu supren.

42
00:01:48,370 --> 00:01:52,430
Tiuj ĉi tie estas sep pordoj, kaj kio
Mi ŝatus ke vi faru por ni ĉi tie,

43
00:01:52,430 --> 00:01:56,560
antaŭ ĉiuj de viaj samklasanoj,
estas trovi nin la numero, 50.

44
00:01:56,560 --> 00:02:00,860
Por trovi numeron, vi povas peek malantaŭ
iu el tiuj pordoj per simple tapping

45
00:02:00,860 --> 00:02:03,030
sur unu el la pordoj, kaj ĝi
malkaŝos lian numeron.

46
00:02:03,030 --> 00:02:06,080
Kaj ni vidos kiel rapide vi
povas trovi nin la numero, 50.

47
00:02:06,080 --> 00:02:09,979

48
00:02:09,979 --> 00:02:11,229
>> 15.

49
00:02:11,229 --> 00:02:13,110

50
00:02:13,110 --> 00:02:14,360
16.

51
00:02:14,360 --> 00:02:16,270

52
00:02:16,270 --> 00:02:16,530
50.

53
00:02:16,530 --> 00:02:17,350
Bele farita.

54
00:02:17,350 --> 00:02:18,040
Ĉio bone.

55
00:02:18,040 --> 00:02:19,906
Ronda de aplaŭdo por Jennifer.

56
00:02:19,906 --> 00:02:21,530
>> [Aplaŭdo]

57
00:02:21,530 --> 00:02:22,320
>> Ĉio bone.

58
00:02:22,320 --> 00:02:25,254
Do kio estis via strategio por
trovi la numero, 50?

59
00:02:25,254 --> 00:02:27,222
>> Jennifer: Um, mi pensis ke eble se -

60
00:02:27,222 --> 00:02:27,714
[Inaudibles]

61
00:02:27,714 --> 00:02:28,206
>> DAVID J. Malan: Ho.

62
00:02:28,206 --> 00:02:29,630
Donu ĝin unu sekundo.

63
00:02:29,630 --> 00:02:32,420
Do estis via strategio por
trovi la numero, 50?

64
00:02:32,420 --> 00:02:34,760
>> Jennifer: Do mi simple komencu ĉe la
komencas vidi, kion la unua numero

65
00:02:34,760 --> 00:02:38,590
estis, kaj tiam mi pensis, eble se
ili estas ordo, mi nur konservi

66
00:02:38,590 --> 00:02:39,970
tapping pli alte?

67
00:02:39,970 --> 00:02:40,140
>> DAVID J. Malan: okej.

68
00:02:40,140 --> 00:02:42,910
Kaj ni ŝajnas esti trovita
ke por esti la kazo.

69
00:02:42,910 --> 00:02:45,670
Kvankam, ni ŝelo redonas la manteloj
malmulta, kaj vi volas iri

70
00:02:45,670 --> 00:02:47,640
antaŭeniris kaj malkaŝi la alia pordo
vi povus esti elektita?

71
00:02:47,640 --> 00:02:50,400

72
00:02:50,400 --> 00:02:51,712
>> Jennifer: Ho, kara.

73
00:02:51,712 --> 00:02:53,128
>> DAVID J. Malan: Ah.

74
00:02:53,128 --> 00:02:54,280
>> Jennifer: Mi ĵus bonŝanca.

75
00:02:54,280 --> 00:02:55,270
>> DAVID J. Malan: Do vi havas sorton.

76
00:02:55,270 --> 00:02:55,710
Ĉio bone.

77
00:02:55,710 --> 00:02:56,795
Do ne estas malbona.

78
00:02:56,795 --> 00:02:58,750
Sed tio estas interesa
komprenon, ĉu ne?

79
00:02:58,750 --> 00:03:01,870
Se vi supozis, kaj vi faris alveni,
ja, iom bonŝanca tie.

80
00:03:01,870 --> 00:03:05,350
Sed se vi supozas ke la numeroj estis
ordo, vi povas esti pli preciza

81
00:03:05,350 --> 00:03:08,750
pri kiel kiu influis
via konduto?

82
00:03:08,750 --> 00:03:11,715
>> Jennifer: Do se ili ordo, mi
pensis eble plej malgranda ĝis granda.

83
00:03:11,715 --> 00:03:11,970
>> DAVID J. Malan: okej.

84
00:03:11,970 --> 00:03:15,260
>> Jennifer: Aŭ se tio finis estante
vere granda, tiam granda ol plej malgranda.

85
00:03:15,260 --> 00:03:15,540
>> DAVID J. Malan: okej.

86
00:03:15,540 --> 00:03:18,170
Tiel granda ol plej malgranda, aŭ
plej malgranda ĝis granda.

87
00:03:18,170 --> 00:03:21,990
Sed mi proponas, supozu ke vi havis
alveninta malfeliĉa, kaj supozu ke ili

88
00:03:21,990 --> 00:03:26,840
ne estis, fakte, ordo, kiom da
tiuj pordoj eble vi devis peek

89
00:03:26,840 --> 00:03:28,590
malantaŭ en tiu plej malbona kazo?

90
00:03:28,590 --> 00:03:29,860
>> Jennifer: Ĉiuj el ili.

91
00:03:29,860 --> 00:03:30,420
>> DAVID J. Malan: Ĉiuj el ili.

92
00:03:30,420 --> 00:03:31,740
Do ni ĝeneraligi ke kiel n.

93
00:03:31,740 --> 00:03:34,790
Tie okazas al esti 7, sed ni pli
ĝenerale diras, ke la n pordojn en la

94
00:03:34,790 --> 00:03:35,650
ekrano tie.

95
00:03:35,650 --> 00:03:40,110
Do, en la plej malbona kazo, vi havus
rigardi malantaŭen 7 pordojn, aŭ n pordoj.

96
00:03:40,110 --> 00:03:44,140
Kaj tiel ĉi vere estas, estas iom da
sorto hodiaŭ, sed estas vere lineara

97
00:03:44,140 --> 00:03:46,440
Algoritmo de varoj, kvankam vi
Estis speco de salti ĉirkaŭe.

98
00:03:46,440 --> 00:03:47,080
Ĉu tio estas justa?

99
00:03:47,080 --> 00:03:47,500
>> Jennifer: Jes.

100
00:03:47,500 --> 00:03:50,000
>> DAVID J. Malan: Nu, mi volas vidi se via
strategio ŝanĝojn se mi movi nin

101
00:03:50,000 --> 00:03:52,190
nia dua ekzemplo ĉi tie kun
7 malsamaj pordoj.

102
00:03:52,190 --> 00:03:55,240
Sama nombroj, sed ĉi tiu
tempo estas ordo.

103
00:03:55,240 --> 00:03:58,350
Kio estas via strategio tie tuj estos,
provante meti el via menso, kion

104
00:03:58,350 --> 00:03:59,310
la aliaj numeroj estis -

105
00:03:59,310 --> 00:03:59,930
>> Jennifer: okej.

106
00:03:59,930 --> 00:04:02,290
>> DAVID J. Malan: - pli frue?

107
00:04:02,290 --> 00:04:03,180
>> Jennifer: Ni komencu
kun la unua.

108
00:04:03,180 --> 00:04:03,540
>> DAVID J. Malan: Bone.

109
00:04:03,540 --> 00:04:05,190
Komencu kun la unua.

110
00:04:05,190 --> 00:04:05,960
4.

111
00:04:05,960 --> 00:04:08,810
Sed kie vi intencas iri, kaj kial?

112
00:04:08,810 --> 00:04:10,040
>> Jennifer: 4 estas vere malgranda.

113
00:04:10,040 --> 00:04:12,500
Do, se ili estas speco eble plej malgranda
al pli granda, ĝi devus

114
00:04:12,500 --> 00:04:13,290
esti duoble, kaj -.

115
00:04:13,290 --> 00:04:13,670
>> DAVID J. Malan: okej.

116
00:04:13,670 --> 00:04:15,990
Ni vidu, kion vi opinias?

117
00:04:15,990 --> 00:04:19,050
>> Jennifer: Provu la lasta.

118
00:04:19,050 --> 00:04:19,500
Nice.

119
00:04:19,500 --> 00:04:20,880
>> DAVID J. Malan: Tre bele farita.

120
00:04:20,880 --> 00:04:21,860
Ĉio bone.

121
00:04:21,860 --> 00:04:23,010
>> [Aplaŭdo]

122
00:04:23,010 --> 00:04:24,310
>> DAVID J. Malan: okej.

123
00:04:24,310 --> 00:04:26,790
Do vi fakte faras ĉi
terure, ĉar vi

124
00:04:26,790 --> 00:04:27,700
fari ĝin tre bone.

125
00:04:27,700 --> 00:04:31,150
Kiu lasas nin nekapablaj
fari kelkajn punktojn.

126
00:04:31,150 --> 00:04:32,565
Do ni provu ruliĝi reveni ĉi tien.

127
00:04:32,565 --> 00:04:34,560
>> Jennifer: okej.

128
00:04:34,560 --> 00:04:35,980
>> DAVID J. Malan: Tre bone
farita, tamen.

129
00:04:35,980 --> 00:04:39,060
Do vi komencis en la komenco,
Vi vidis, ke estis 4, tiam vi

130
00:04:39,060 --> 00:04:40,240
movis al la fino.

131
00:04:40,240 --> 00:04:42,320
Sed supozas ke vi ne ricevis bonŝanca
tie, kaj supozu 50

132
00:04:42,320 --> 00:04:42,890
estis aliloke.

133
00:04:42,890 --> 00:04:46,190
Kio via tria paŝo estis?

134
00:04:46,190 --> 00:04:47,680
>> Jennifer: Reiru al la komenco.

135
00:04:47,680 --> 00:04:48,320
>> DAVID J. Malan: Reiru
al la komenco.

136
00:04:48,320 --> 00:04:51,320
Bone, do vi devus jam tuŝis
ĉi pordo, kiu estis 8.

137
00:04:51,320 --> 00:04:51,660
Ĉio bone.

138
00:04:51,660 --> 00:04:52,650
Do tio ne estas 50.

139
00:04:52,650 --> 00:04:55,380
Kie vi aspektis poste?

140
00:04:55,380 --> 00:04:56,720
>> Jennifer: Se mi ne
konas ili ordo.

141
00:04:56,720 --> 00:04:57,005
>> DAVID J. Malan: Correct.

142
00:04:57,005 --> 00:04:58,490
Nu, se vi efektive scias
ili ordo -

143
00:04:58,490 --> 00:04:58,700
>> Jennifer: Ho, ne scias, yeah.

144
00:04:58,700 --> 00:05:00,910
>> DAVID J. Malan: - sed vi ne
scias, kie 50 estis ankoraux?

145
00:05:00,910 --> 00:05:01,785
>> Jennifer: Just plu iri.

146
00:05:01,785 --> 00:05:02,130
>> DAVID J. Malan: Bone.

147
00:05:02,130 --> 00:05:02,520
Akcepti.

148
00:05:02,520 --> 00:05:03,800
Konservu iras.

149
00:05:03,800 --> 00:05:05,270
Bone, ke mi povas labori kun ili.

150
00:05:05,270 --> 00:05:05,610
>> Jennifer: okej.

151
00:05:05,610 --> 00:05:07,210
>> DAVID J. Malan: Nun, se vi estas nur
iri plu iri, kio estas via

152
00:05:07,210 --> 00:05:09,680
algoritmo devolving apogita en.

153
00:05:09,680 --> 00:05:10,740
>> Jennifer: La lineara -.

154
00:05:10,740 --> 00:05:11,820
>> DAVID J. Malan: Estas speco de lineara.

155
00:05:11,820 --> 00:05:13,480
Sed mi proponas, estu
Mi surmetis la makulo.

156
00:05:13,480 --> 00:05:14,900
Lasu min refreŝigi la paĝon.

157
00:05:14,900 --> 00:05:17,120
sama nombro, sama aranĝo,
sama pordoj.

158
00:05:17,120 --> 00:05:21,350
Sed pensu reen al tiu unua tago
klaso kiam oni ŝiris telefono libro en

159
00:05:21,350 --> 00:05:25,480
duono, speco de, kaj kio estis
nia strategio tie?

160
00:05:25,480 --> 00:05:26,450
>> Jennifer: Komencdato en la mezo.

161
00:05:26,450 --> 00:05:26,690
>> DAVID J. Malan: okej.

162
00:05:26,690 --> 00:05:27,610
Do starti je la mezo.

163
00:05:27,610 --> 00:05:28,790
Do ni iru antaŭen kaj simuli tion.

164
00:05:28,790 --> 00:05:30,720
Komenci je la mezo de
malkaŝi tiun pordon.

165
00:05:30,720 --> 00:05:31,660
Do la nombro 16.

166
00:05:31,660 --> 00:05:35,290
Do kio estus la forta viro faris,
kiuj disŝiris la telefonon libro en duono,

167
00:05:35,290 --> 00:05:38,450
por atingi la najbaran konjekton?

168
00:05:38,450 --> 00:05:39,400
>> Jennifer: Iru kun cxi tiu duono.

169
00:05:39,400 --> 00:05:41,700
>> DAVID J. Malan: Kaj kial al la dekstra?

170
00:05:41,700 --> 00:05:43,900
>> Jennifer: Se ili estus speco de malgranda
al pli granda, tiam 50 devus esti

171
00:05:43,900 --> 00:05:44,720
en tiu fino.

172
00:05:44,720 --> 00:05:44,920
>> DAVID J. Malan: Bonan.

173
00:05:44,920 --> 00:05:45,390
Plene racia.

174
00:05:45,390 --> 00:05:48,380
Do kiel telefono libro, vi iras al la
dekstra kontraste al maldekstre, sed ĉi tie

175
00:05:48,380 --> 00:05:49,500
estas la ŝlosilo takeaway.

176
00:05:49,500 --> 00:05:53,930
Vi nun povas forĵeti, aŭ ŝiras for,
duono de ĉi tiu problemo, lasante vin ne

177
00:05:53,930 --> 00:05:55,970
kun 7 pordoj, sed vere kun nur 3.

178
00:05:55,970 --> 00:05:57,870
Kiu estas proksimume la duono de la
grandeco de la problemo.

179
00:05:57,870 --> 00:05:58,350
Ĉio bone.

180
00:05:58,350 --> 00:06:01,890
Do nun tio, kion vi havus
farita post vi ĝuste iros?

181
00:06:01,890 --> 00:06:05,870
>> Jennifer: Do 16 estas ankoraŭ sufiĉe malgrandaj,
relativa al 50, do eble mi provos,

182
00:06:05,870 --> 00:06:06,700
kiel, ĉi tiu.

183
00:06:06,700 --> 00:06:07,890
>> DAVID J. Malan: Bone.

184
00:06:07,890 --> 00:06:08,720
42.

185
00:06:08,720 --> 00:06:10,830
Bone, do kion estas via
instinkto diras al vi?

186
00:06:10,830 --> 00:06:12,100
>> Jennifer: Mi povas forĵeti
ĉi tio kaj tiam simple -

187
00:06:12,100 --> 00:06:12,360
>> DAVID J. Malan: okej.

188
00:06:12,360 --> 00:06:14,212
Bone, vi povas forĵeti
la maldekstra duono tie.

189
00:06:14,212 --> 00:06:14,890
>> Jennifer: - elektu ĉi tiu.

190
00:06:14,890 --> 00:06:15,530
>> DAVID J. Malan: Kaj la dekstran.

191
00:06:15,530 --> 00:06:15,760
>> Jennifer: Jes.

192
00:06:15,760 --> 00:06:17,820
>> DAVID J. Malan: Do kvankam estas malfacile
vidi eble, kiam ekzistas nur

193
00:06:17,820 --> 00:06:21,320
7 pordoj, pensi, nun,
la konsekvenco de la

194
00:06:21,320 --> 00:06:22,620
Algoritmo vi ĵus aplikita.

195
00:06:22,620 --> 00:06:24,510
En la antaŭa kazo, vi faris
akiri bonŝanca, kiu estis granda.

196
00:06:24,510 --> 00:06:26,540
Sed vi faris uzi heŭristiko,
Mi dirus.

197
00:06:26,540 --> 00:06:29,150
Vi uzis specon de via instinktoj, kaj
scii ĝin ordo, se ĝi estas sufiĉe

198
00:06:29,150 --> 00:06:31,600
malgrandaj komence, evidente, ni
devas iri pli dekstre.

199
00:06:31,600 --> 00:06:34,990
Sed en iu senco, vi havas sorton,
ĉar eble tio estis la nombro 100,

200
00:06:34,990 --> 00:06:36,220
kaj eble 50 estis pli en la mezo.

201
00:06:36,220 --> 00:06:37,910
Eble 50 estis eĉ pli tie.

202
00:06:37,910 --> 00:06:40,960
>> Sed kion vi faris iom alie
tiu tempo estis, vi faris la samon

203
00:06:40,960 --> 00:06:42,150
denove kaj denove.

204
00:06:42,150 --> 00:06:45,310
Kaj mi dirus ke kion vi ĵus
ne, kvankam influita de la telefono

205
00:06:45,310 --> 00:06:48,100
libro ekzemple, estas io multe
pli algoritma, kaj multe

206
00:06:48,100 --> 00:06:49,930
malpli speciala cased.

207
00:06:49,930 --> 00:06:51,620
Multe malpli instinkta.

208
00:06:51,620 --> 00:06:57,160
Do, en la fino de la tago, kiel farus
vi priskribas la efikeco de la

209
00:06:57,160 --> 00:07:00,530
unua algoritmo, kien vi venis
maldekstre dekstren, kontraý la

210
00:07:00,530 --> 00:07:03,430
dua algoritmon ĉi tie?

211
00:07:03,430 --> 00:07:06,460
>> Jennifer: Ĉi tiu devus, kiel, eble
Halve la tempo, aŭ eĉ pli, jes.

212
00:07:06,460 --> 00:07:07,320
>> DAVID J. Malan: Bone, eble eĉ pli.

213
00:07:07,320 --> 00:07:10,150
Ni puŝi iom pli malfacila en tiu.

214
00:07:10,150 --> 00:07:13,030
Kio vere, se ni daŭrigas tiun
logiko, ni definitive redukti al la duono de la

215
00:07:13,030 --> 00:07:15,830
rula tempo kun ĉi tiu dua algoritmo
ĵetante sin duonon de la

216
00:07:15,830 --> 00:07:18,470
nombroj, sed kion ni faru la sekvantan
ripeta, kiam Jennifer malkaŝis

217
00:07:18,470 --> 00:07:20,615
la dua numero?

218
00:07:20,615 --> 00:07:22,830
>> Ni redukti al la duono de la numeroj de pordoj denove.

219
00:07:22,830 --> 00:07:25,270
Kaj poste kion ni faros post tio, se
estis pli pordojn por ludi kun?

220
00:07:25,270 --> 00:07:27,520
Ni estus Halve ilin, kaj denove,
kaj denove, kaj denove.

221
00:07:27,520 --> 00:07:30,420
Kaj tio estis ĝuste kiel vi knaboj ĉiuj
piedo en la unua semajno de

222
00:07:30,420 --> 00:07:33,000
klaso, duono el vi sidas duono
vi sidas meze de vi

223
00:07:33,000 --> 00:07:35,440
sidiĝi, ĝis unu sola
animo staris.

224
00:07:35,440 --> 00:07:39,050
Kaj ni diris ke la rula tempo de
tio, la nombro da paŝoj prenis estis

225
00:07:39,050 --> 00:07:40,430
en la ordo de kio?

226
00:07:40,430 --> 00:07:41,230
>> Parolanto 1: [inaudibles]

227
00:07:41,230 --> 00:07:43,970
>> DAVID J. Malan: Do log bazo 2 de n,
aŭ simple pli simple, ensaluti de n.

228
00:07:43,970 --> 00:07:45,060
Do io logaritma.

229
00:07:45,060 --> 00:07:48,380
Kaj la grafeo ne estis rekta linio
ke nur plimalbonigis kaj malbona, estis

230
00:07:48,380 --> 00:07:52,490
tiu interesa kurbo kiu ne
akiri tiel malbona tempo.

231
00:07:52,490 --> 00:07:53,910
Do ni tenas al tiu ideo.

232
00:07:53,910 --> 00:07:54,690
Ni dankas al Jennifer.

233
00:07:54,690 --> 00:07:56,150
Danke tiel por veni supren.

234
00:07:56,150 --> 00:07:57,400
Kaj, unu sek.

235
00:07:57,400 --> 00:08:00,170

236
00:08:00,170 --> 00:08:02,925
Neniu skribtablo lampoj hodiaŭ, sed ni
ja havas CS50 streso pilkojn.

237
00:08:02,925 --> 00:08:03,420
>> Jennifer: Yay.

238
00:08:03,420 --> 00:08:04,410
>> DAVID J. Malan: Bone, ĉi tie.

239
00:08:04,410 --> 00:08:06,545
Dankon por fali
la streĉo ĝis ĉi tie.

240
00:08:06,545 --> 00:08:07,350
Ĉio bone.

241
00:08:07,350 --> 00:08:10,620
Do ni vidu, se ni ne povas nun
formaligi tiun iom pli.

242
00:08:10,620 --> 00:08:14,820
Do denove, kion ni ĵus faris estis
esence la sama afero kiel ni faris

243
00:08:14,820 --> 00:08:16,660
en tiu unua semajno.

244
00:08:16,660 --> 00:08:23,780
Sed anstataŭ fino kun nur linearaj
algoritmo, kiun ni reprezentas

245
00:08:23,780 --> 00:08:27,210
antaŭe kiel tiu rekta linio,
per kio, se ni metis pli pordon

246
00:08:27,210 --> 00:08:29,610
la ekrano, kaj poste Jennifer farus
ili devis rigardi, potenciale,

247
00:08:29,610 --> 00:08:30,600
malantaŭ pli pordo.

248
00:08:30,600 --> 00:08:33,490
Se ni metas du pordojn, ŝi povus havi
rigardi malantaŭ du pordoj.

249
00:08:33,490 --> 00:08:35,990
>> Kaj do, tie estis jena lineara
rilato inter la amplekso de la

250
00:08:35,990 --> 00:08:39,059
problemo en, ekzemple, la x-akso, kaj
la kvanton de tempo necesa por

251
00:08:39,059 --> 00:08:40,440
solvi sur la y.

252
00:08:40,440 --> 00:08:43,330
Sed la foto mi aludante
pli frua estis tiu verda linio.

253
00:08:43,330 --> 00:08:45,970
Verda intence, ĉar
ĝi simple sentis pli bone.

254
00:08:45,970 --> 00:08:49,790
En teorio, la algoritmo, kiam ni faris
kun la telefono libro, kiam ni faris

255
00:08:49,790 --> 00:08:52,420
kun vi infanoj rakonti reciproke, kaj
en la dua kazo, kiam Jennifer nur

256
00:08:52,420 --> 00:08:55,250
faris ĝin ĉi tie, estis speco
de fundamente bona.

257
00:08:55,250 --> 00:08:57,180
Ĉar ĝi estis ne nur duoble pli rapide.

258
00:08:57,180 --> 00:08:58,870
Ne estis eĉ kvaroble pli rapida.

259
00:08:58,870 --> 00:09:03,290
Ĝi estis tute dependa de kion la
grandeco de la eniga estis, kiel al kiom

260
00:09:03,290 --> 00:09:05,220
paŝojn ĝi finfine prenis.

261
00:09:05,220 --> 00:09:08,040
>> Kaj tial tiu simpla ideo, ke ni ĉiuj portis
por sentado kun la telefono libro,

262
00:09:08,040 --> 00:09:10,200
povas simile esti aplikita
al io kiel tio.

263
00:09:10,200 --> 00:09:12,380
Kaj ĉi tiu povus esti pli hazarde
konata kiel, kiel vi povus

264
00:09:12,380 --> 00:09:13,940
imagi, dividi kaj venki.

265
00:09:13,940 --> 00:09:16,390
Ne kontraste kion ni faris, kompreneble,
kun la telefono libro.

266
00:09:16,390 --> 00:09:18,300
>> Sed la _pseudocode_, revokon, estis jena.

267
00:09:18,300 --> 00:09:21,800
Do ni ne faros ĉi denove, sed memoras
tiu unua semajno, ni ĉiuj ekstaris

268
00:09:21,800 --> 00:09:25,140
kaj tiam duono el vi sidiĝis, la duono de
vi sidiĝis, duono el vi eksidis.

269
00:09:25,140 --> 00:09:29,280
Tiu algoritmo estis implementado en
bito de kaptiloj maniero, en tio,

270
00:09:29,280 --> 00:09:32,870
Ne estis nur unu el min rakonti,
fundamente, pli efike.

271
00:09:32,870 --> 00:09:35,830
En tiu kazo, mi estis utiligante
malĉefan rimedo.

272
00:09:35,830 --> 00:09:39,470
Ordigi de, multnombraj CPU, multnombraj cerbon,
multnombraj inteligenta homo en la

273
00:09:39,470 --> 00:09:42,740
ĉambro helpis min preni de io
lineara ion

274
00:09:42,740 --> 00:09:45,190
logaritma, de io
ruĝa al io verda.

275
00:09:45,190 --> 00:09:48,650
>> Sed en tiu kazo, Jennifer sole povas
funde plibonigi sur la

276
00:09:48,650 --> 00:09:52,370
agado de ŝia unua algoritmo de,
denove, nur pensante iom pli malfacila.

277
00:09:52,370 --> 00:09:56,650
Kaj nun, kiam venas tempo por apliki
tion, elŝeligi

278
00:09:56,650 --> 00:10:00,670
kio linioj de kodo povas skribi tiajn
ke vi povas ripeti ilin denove, kaj

279
00:10:00,670 --> 00:10:03,350
denove, kaj denove, ia
en looping modo.

280
00:10:03,350 --> 00:10:06,370
Ĉar vi ne tuj havos la
lukso, kiel Jennifer faris unue, al

281
00:10:06,370 --> 00:10:10,460
nur havi tutan aron da oj kaj diru:
hmm, se tiu unua nombro estas 4,

282
00:10:10,460 --> 00:10:11,800
lasu min salti tuta vojo al la fino.

283
00:10:11,800 --> 00:10:14,180
Ooh, se tiu numero estas tro granda,
lasu min movi arbitre reen

284
00:10:14,180 --> 00:10:15,220
al la dua elemento.

285
00:10:15,220 --> 00:10:18,210
Vi trovos ke ĝi tuj estos multe
malfacile formaligi kion ni homoj

286
00:10:18,210 --> 00:10:21,270
preni por donita kiel tre racia
heurísticas, sed komputilo estas nur

287
00:10:21,270 --> 00:10:23,260
faros kion vi sciigus tion fari.

288
00:10:23,260 --> 00:10:25,280
>> Nun ĉi havas tre interesan
implikaĵoj.

289
00:10:25,280 --> 00:10:29,950
Ĉi tiu grafikaĵo estas speco de intencis ordigi de
Colmar vide, sed rimarki, kie

290
00:10:29,950 --> 00:10:32,230
estas la rekta linio en ĉi tiu grafikaĵo?

291
00:10:32,230 --> 00:10:35,330
Kie estas la lineara grafikaĵo
ke ni nomas n?

292
00:10:35,330 --> 00:10:37,580
Nu, estas speco de cele la fundon
de tiu bildo, ĉu ne?

293
00:10:37,580 --> 00:10:40,500
Do ĉiuj ni faris estas ni ia
zomita al la x-akso kaj la

294
00:10:40,500 --> 00:10:44,780
y-akso por provi akiri senton de kio
aliaj specoj de kurboj aspekti.

295
00:10:44,780 --> 00:10:47,760
>> Kaj la specifaj detaloj de la matematika
esprimoj hodiaŭ ne gravas tiom

296
00:10:47,760 --> 00:10:52,440
da, sed rimarkas ke estas multe da
algoritmoj kiuj estas multe pli malbone ol

297
00:10:52,440 --> 00:10:53,470
iu kiu estas lineara.

298
00:10:53,470 --> 00:10:55,410
Ja, n cubed aspektas sufiĉe malbone.

299
00:10:55,410 --> 00:10:58,400
2 al la n aspektas sufiĉe malbone.
n kvadrata aspektas sufiĉe malbone.

300
00:10:58,400 --> 00:11:01,630
Kaj ni vidos kion iuj el tiuj
povus esti en la realo nuntempe.

301
00:11:01,630 --> 00:11:05,430
Kaj log n ne sentas tiel malbone, sed
pli bona ol n estas log bazo 2 de n.

302
00:11:05,430 --> 00:11:08,080
Sed vi scias, estus estinta inkluzive
pli mirinda se Jennifer, aŭ se ni,

303
00:11:08,080 --> 00:11:12,910
tiu unua semajno, venis kun
iu kiu estas log de logo de n.

304
00:11:12,910 --> 00:11:15,880
>> Do alivorte, ne estas tio tutajn
gamo de eblaj solvaĵoj al

305
00:11:15,880 --> 00:11:18,570
problemoj, sed eĉ tie, avizo
kio okazos.

306
00:11:18,570 --> 00:11:22,910
Kiam mi malzomi, kiu el tiuj kurboj
tuj pruvi al esti la absoluta

307
00:11:22,910 --> 00:11:26,630
plej malbonajn el la sur la ekrano nun?

308
00:11:26,630 --> 00:11:28,680
Do la n cubed aspektas bela
malbona nuntempe.

309
00:11:28,680 --> 00:11:32,470
Sed se ni malzomi kaj vidi pli de la
x kaj la y-akso, kiu tuj

310
00:11:32,470 --> 00:11:34,550
regi finfine?

311
00:11:34,550 --> 00:11:37,120
Do fakte rezultas ke 2 al la
n, kaj vi povas kompreni tion ĉi nur

312
00:11:37,120 --> 00:11:39,990
ŝtopanta en iu pli granda
nombroj, kaj vi vidos ke 2 al la

313
00:11:39,990 --> 00:11:42,070
n, ja, ricevas pli multe rapida.

314
00:11:42,070 --> 00:11:45,530
Se ni vere malzomi, a 2 al la
n algoritmo absolute sucks.

315
00:11:45,530 --> 00:11:48,170
Mi volas diri tuj preni
sufiĉe da tempo por la

316
00:11:48,170 --> 00:11:49,460
komputilo Mazar tra.

317
00:11:49,460 --> 00:11:52,500
>> Sed vi vidos la tempo, speciale
kun estonteco problemo aroj kaj eĉ

318
00:11:52,500 --> 00:11:55,600
fina projektoj, estas via datumoj
aro ricevas grandajn, ĉiuj rajtas?

319
00:11:55,600 --> 00:11:58,300
Eĉ en la unua versio de Facebook,
kiel la nombro de amikoj, kaj la

320
00:11:58,300 --> 00:12:01,840
nombro de registritaj uzantoj atingis grandan,
vi povas ordigi de telefono en kaj

321
00:12:01,840 --> 00:12:05,530
apliki iun kun lineara serĉo,
aŭ tre simpla ordigado

322
00:12:05,530 --> 00:12:07,030
algoritmo, kiel ni vidos hodiaŭ.

323
00:12:07,030 --> 00:12:09,280
Vi devos komenci pensi pli malfacila
kaj pli malfacile pri tiuj problemoj.

324
00:12:09,280 --> 00:12:12,070
Kaj la tipoj de problemoj lokoj kiel
Facebook, kaj Google kaj Microsoft,

325
00:12:12,070 --> 00:12:16,350
kaj aliaj laboras sur estas ĝuste tiuj
speco de granda datumoj ia demandoj

326
00:12:16,350 --> 00:12:18,530
ĉiufoje tiuj tagoj.

327
00:12:18,530 --> 00:12:18,900
>> Ĉio bone.

328
00:12:18,900 --> 00:12:23,800
Do Jennifer sukceso en tiu dua
algoritmo, sincere, ŝi faris mirinde

329
00:12:23,800 --> 00:12:26,110
bone la unuan fojon, sed ni
skribi ĝin kiel sorto tiel ke ni

330
00:12:26,110 --> 00:12:27,000
povas fari ĉi tiu punkto.

331
00:12:27,000 --> 00:12:30,970
En la dua kazo, ŝi leveraged an
algoritmo kiu ripetis denove kaj

332
00:12:30,970 --> 00:12:34,670
denove, sed ŝi prenis por koncedis
certa supozo, ke ni permesis

333
00:12:34,670 --> 00:12:39,370
ŝi, sed ŝi eksplodis detale al la
duan fojon, ke sxi ne havis la

334
00:12:39,370 --> 00:12:39,840
unua fojo.

335
00:12:39,840 --> 00:12:41,800
Kiu estis kio?

336
00:12:41,800 --> 00:12:43,050
>> Ke la listo estis ordo.

337
00:12:43,050 --> 00:12:46,350
Tuj, kiam la listo estis ordo, ni
asertas ke Jennifer povis fari

338
00:12:46,350 --> 00:12:47,480
fundamente bona.

339
00:12:47,480 --> 00:12:51,450
7 pordoj, jes, ne estas tiel interesa,
sed supozas ke ni estas 7 milionoj pordoj.

340
00:12:51,450 --> 00:12:54,080
Ensalutu de n estas definitive irante
plenumi multe, multe

341
00:12:54,080 --> 00:12:55,610
rapida en la longa.

342
00:12:55,610 --> 00:12:58,880
Sed ŝi devis havi la
pordojn ordo por ŝi.

343
00:12:58,880 --> 00:13:02,320
Nun, mi prenis la liberecon fari tion
anticipe sur la komputila ekrano

344
00:13:02,320 --> 00:13:05,160
ĉi tie, sed supozas ke Jennifer
devis fari tion mem?

345
00:13:05,160 --> 00:13:10,120
Supozu ke la pordoj en demando
reprezentis datumoj en la datumbazo, aŭ

346
00:13:10,120 --> 00:13:14,260
amikoj registrita Facebook, aŭ
neniu retpaĝoj en interreto ke

347
00:13:14,260 --> 00:13:16,880
diversaj retejoj povus bezoni
al indekso aŭ serĉo finiĝis.

348
00:13:16,880 --> 00:13:20,940
>> Supozu ke vi ĵus havis krudaj datumoj
aro kaj estis lasita al vi, aŭ al

349
00:13:20,940 --> 00:13:23,010
Jennifer fari tion ordigado?

350
00:13:23,010 --> 00:13:26,950
Tio, pli ĝuste, postulas, ke ni respondu
la demando, nu, kiom da tempo

351
00:13:26,950 --> 00:13:31,080
estus preninta Jennifer, aŭ eĉ mi,
ordigi tiujn numerojn anticipe tiel

352
00:13:31,080 --> 00:13:32,680
ke ŝi povis utiligi tiun?

353
00:13:32,680 --> 00:13:32,880
Ĝuste?

354
00:13:32,880 --> 00:13:36,620
Pro la implico, kompreneble, estas
se ĝi prenas min sufiĉe tempo por ordigi

355
00:13:36,620 --> 00:13:40,800
la ciferoj, kiujn la heck zorgas ke vi
povas trovi nombro kiel 50 tiel rapide,

356
00:13:40,800 --> 00:13:44,850
kiel en Jennifer la kazo, se ni pli ol
premita la kvanto de tuta tempo

357
00:13:44,850 --> 00:13:46,920
ĝin prenis por ordigi aferojn anticipe?

358
00:13:46,920 --> 00:13:49,320
>> Do ni vidu, se ni ne povas la
pentri la bildon tie.

359
00:13:49,320 --> 00:13:51,370
Mi havas tutan faskon pli streso
pilkoj, se tio helpas

360
00:13:51,370 --> 00:13:52,270
rompi la glacion tie.

361
00:13:52,270 --> 00:13:55,690
Kaj se vi ne atentas, ni
bezonas sep volontulon -

362
00:13:55,690 --> 00:13:57,060
on, OK.

363
00:13:57,060 --> 00:13:57,240
Wow.

364
00:13:57,240 --> 00:13:59,250
Do ni ne devas elspezi
sur tablo lucernojn similas.

365
00:13:59,250 --> 00:13:59,690
Ĉio bone.

366
00:13:59,690 --> 00:14:01,530
Do kiel pri vi du en fronto.

367
00:14:01,530 --> 00:14:04,160
Kion pri vi du infanoj en dorso.

368
00:14:04,160 --> 00:14:04,870
Do jen kvar.

369
00:14:04,870 --> 00:14:09,890
Kion pri vi en fronto
kvin, ses kaj sep.

370
00:14:09,890 --> 00:14:10,320
Ĝuste tie.

371
00:14:10,320 --> 00:14:13,260
Via amiko estas montrante vin,
tial vi ricevos la premion.

372
00:14:13,260 --> 00:14:13,700
>> Ĉio bone.

373
00:14:13,700 --> 00:14:14,410
Venu supren.

374
00:14:14,410 --> 00:14:17,120
Kaj kial ni ne havas vin
infanoj venu ĉi tien.

375
00:14:17,120 --> 00:14:18,960
Mi tuj donos al vi ĉiu numero.

376
00:14:18,960 --> 00:14:22,150
Kaj iru antaŭen kaj aranĝi mem
idente al kio

377
00:14:22,150 --> 00:14:25,180
bildigita sur la ekrano.

378
00:14:25,180 --> 00:14:26,530
>> [Intermetante voĉoj]

379
00:14:26,530 --> 00:14:28,160
>> DAVID J. Malan: OOP, sorry.

380
00:14:28,160 --> 00:14:30,210
Insekto.

381
00:14:30,210 --> 00:14:32,180
Ĉio bone.

382
00:14:32,180 --> 00:14:32,750
Nu, jen ni iru.

383
00:14:32,750 --> 00:14:34,180
Numero kvin.

384
00:14:34,180 --> 00:14:35,136
Numero ses.

385
00:14:35,136 --> 00:14:37,770
Unu, du, tri, kvar,
kvin, ses, sep.

386
00:14:37,770 --> 00:14:39,410
Ho, tio estas mallerta.

387
00:14:39,410 --> 00:14:41,210
>> Speaker 2: mi nur ricevas -.

388
00:14:41,210 --> 00:14:41,900
>> DAVID J. Malan: Bona traktadon.

389
00:14:41,900 --> 00:14:43,130
Ĉio bone.

390
00:14:43,130 --> 00:14:44,611
Dankon por partopreni.

391
00:14:44,611 --> 00:14:47,200
>> [Aplaŭdo]

392
00:14:47,200 --> 00:14:48,580
>> Akcepti.

393
00:14:48,580 --> 00:14:48,860
Ĉio bone.

394
00:14:48,860 --> 00:14:51,970
Do ni havas kvar, du, ses,
unu, tri, sep, kvin.

395
00:14:51,970 --> 00:14:56,010
Perfektigi tiel ni havas sep volontuloj
ĉi tie, kiuj estas egalaj je larĝeco al la

396
00:14:56,010 --> 00:14:57,430
tabelo, ke ni ludas
kun la antaŭaj.

397
00:14:57,430 --> 00:14:59,470
Kaj mi elektis sep por kialoj
ke estos ĝuste

398
00:14:59,470 --> 00:15:00,840
oportuna en iomete.

399
00:15:00,840 --> 00:15:04,400
Kaj mi tuj proponi unua kiu
ni ordigi tiujn sep volontuloj.

400
00:15:04,400 --> 00:15:06,786
Se vi ŝatus, unue,
por diri saluton kvankam.

401
00:15:06,786 --> 00:15:08,970
Ekde ĉi tiu tuj estos
mallerta pluraj minutoj.

402
00:15:08,970 --> 00:15:10,370
Enkonduki vin.

403
00:15:10,370 --> 00:15:10,980
>> GRACIA: Saluton, mi estas Grace.

404
00:15:10,980 --> 00:15:14,190
Mi estas sophomore en Leverett Domo.

405
00:15:14,190 --> 00:15:14,620
>> Branson: Hi.

406
00:15:14,620 --> 00:15:15,620
Mi Branson.

407
00:15:15,620 --> 00:15:16,920
Mi estas novulo en Veldo.

408
00:15:16,920 --> 00:15:19,755

409
00:15:19,755 --> 00:15:20,230
>> Gabe: Hi.

410
00:15:20,230 --> 00:15:21,040
Mi Gabe.

411
00:15:21,040 --> 00:15:22,300
Mi estas juna en Cabot.

412
00:15:22,300 --> 00:15:24,826

413
00:15:24,826 --> 00:15:25,980
>> Neil: Mi estas Neil.

414
00:15:25,980 --> 00:15:29,090
Mi estas novulo en Matthews.

415
00:15:29,090 --> 00:15:29,550
>> JASON: Mi Jason.

416
00:15:29,550 --> 00:15:32,816
Mi estas novulo en Greenough.

417
00:15:32,816 --> 00:15:33,700
>> MIKE: Mi Mike.

418
00:15:33,700 --> 00:15:37,360
Mi estas novulo en Grays.

419
00:15:37,360 --> 00:15:37,990
>> Jess: Mi Jess.

420
00:15:37,990 --> 00:15:40,313
Mi estas sophomore en Leverett.

421
00:15:40,313 --> 00:15:41,300
>> DAVID J. Malan: Bonega.

422
00:15:41,300 --> 00:15:41,850
Ĉio bone.

423
00:15:41,850 --> 00:15:44,190
Nu, dankon al ĉiuj niaj
volontuloj tie tiom.

424
00:15:44,190 --> 00:15:47,110
Kaj la defio al la mano nun tuj
esti ordigi de ĉi tiuj infanoj, sed tiam

425
00:15:47,110 --> 00:15:50,250
ni tuj devos pensi iom
malmola pri kiel kompetente ni efektive

426
00:15:50,250 --> 00:15:51,110
ordo ilin.

427
00:15:51,110 --> 00:15:52,580
Do ni unue provu tion.

428
00:15:52,580 --> 00:15:55,970
Vi infanoj povas vidi reciprokajn nombroj
nur metante ĉirkaŭ la anguloj.

429
00:15:55,970 --> 00:15:59,380
Antaŭen kaj preni kelkajn sekundojn, kaj
speco vin el malgranda en la

430
00:15:59,380 --> 00:16:01,240
lasis al plej dekstre.

431
00:16:01,240 --> 00:16:02,490
Iru.

432
00:16:02,490 --> 00:16:07,010

433
00:16:07,010 --> 00:16:07,530
>> Akcepti.

434
00:16:07,530 --> 00:16:08,030
Bona.

435
00:16:08,030 --> 00:16:09,370
Tio estis vere Darn rapida.

436
00:16:09,370 --> 00:16:14,040
Nun iu tie, kiu estis la algoritmo
ke tiuj infanoj aplikita?

437
00:16:14,040 --> 00:16:14,900
>> Parolanto 1: Malplej al la plej granda.

438
00:16:14,900 --> 00:16:15,000
>> DAVID J. Malan: okej.

439
00:16:15,000 --> 00:16:18,070
Almenaŭ al la plej granda estas vere ordigi de la
objektiva, sed mi ne certas ke estas

440
00:16:18,070 --> 00:16:18,890
vere algoritmo.

441
00:16:18,890 --> 00:16:21,810
Almenaŭ al la plej granda ne diri
Mi iom post paŝo, kion fari.

442
00:16:21,810 --> 00:16:22,833
Jes?

443
00:16:22,833 --> 00:16:24,083
>> Parolanto 1: [inaudibles]

444
00:16:24,083 --> 00:16:26,010

445
00:16:26,010 --> 00:16:26,280
>> DAVID J. Malan: okej.

446
00:16:26,280 --> 00:16:28,920
Do se vi vidas personon pli malgranda ol
via numero, tiam kopii al

447
00:16:28,920 --> 00:16:29,680
dekstre de ili.

448
00:16:29,680 --> 00:16:32,800
Por ke estas nun ricevas pli esprima,
pli kiel algoritmo, ĉar vi

449
00:16:32,800 --> 00:16:35,410
povas diri, se tio, tiam tiu.

450
00:16:35,410 --> 00:16:37,050
Do ni havas ian
kondiĉa konstruo.

451
00:16:37,050 --> 00:16:39,700
Kaj ĉi tiuj infanoj ŝajnis fari ke en kelkaj
tempoj, ĉar kelkaj el vi kopiis iom

452
00:16:39,700 --> 00:16:40,420
de malproksime.

453
00:16:40,420 --> 00:16:43,410
Kaj estis supozeble ian
looping okazas en iliaj mensoj.

454
00:16:43,410 --> 00:16:44,610
>> Sed ni provu formaligi tio.

455
00:16:44,610 --> 00:16:47,540
Se vi infanoj povis nuligi reen
al ĉi aranĝo.

456
00:16:47,540 --> 00:16:50,650
Ni vidu se ni ne povas formaligi tiun oni
iom, kaj poste demandi la demandon, nur

457
00:16:50,650 --> 00:16:51,580
kiom efikaj estas tio?

458
00:16:51,580 --> 00:16:54,220
Kompreneble, kiam ni devas fari tion pli malrapide,
ĝi tuj sentas kiel bono de

459
00:16:54,220 --> 00:16:57,210
algoritmo, sed ni vidu, se ni povas
meti niajn fingrojn sur la preciza paŝoj.

460
00:16:57,210 --> 00:16:58,670
>> Do vi du infanoj estas kvar kaj du.

461
00:16:58,670 --> 00:17:01,020
Aŭ vi ĝentila aŭ malĝusta ordo?

462
00:17:01,020 --> 00:17:01,900
Evidente malĝusta.

463
00:17:01,900 --> 00:17:02,710
Do ni interŝanĝis.

464
00:17:02,710 --> 00:17:05,170
Nun mi iros por movi flanken
ĉi tie kaj diru, kvar al ses.

465
00:17:05,170 --> 00:17:06,240
Ĉu vi estas ĝentila aŭ malĝusta?

466
00:17:06,240 --> 00:17:06,599
>> Gabe: Correct.

467
00:17:06,599 --> 00:17:07,180
>> DAVID J. Malan: Correct.

468
00:17:07,180 --> 00:17:08,300
Ses kaj unu?

469
00:17:08,300 --> 00:17:08,609
Nope.

470
00:17:08,609 --> 00:17:09,630
Interŝanĝi.

471
00:17:09,630 --> 00:17:10,490
Do jen du svopoj.

472
00:17:10,490 --> 00:17:11,710
Ses kaj tri?

473
00:17:11,710 --> 00:17:11,980
Nope.

474
00:17:11,980 --> 00:17:13,000
Interŝanĝi.

475
00:17:13,000 --> 00:17:13,930
Ses kaj sep?

476
00:17:13,930 --> 00:17:14,630
Aspektas bone.

477
00:17:14,630 --> 00:17:15,396
Sep kaj kvin?

478
00:17:15,396 --> 00:17:16,150
>> Jess: [inaudibles]

479
00:17:16,150 --> 00:17:17,089
>> DAVID J. Malan: OK, interŝanĝi.

480
00:17:17,089 --> 00:17:19,770
Kaj ordo.

481
00:17:19,770 --> 00:17:19,980
Ĉio bone.

482
00:17:19,980 --> 00:17:21,440
Do evidente ne, ĉu ne?

483
00:17:21,440 --> 00:17:22,470
Do tie estis pli okazas.

484
00:17:22,470 --> 00:17:24,920
Sed ja, tiuj knaboj, eĉ
nur instinkte.

485
00:17:24,920 --> 00:17:25,450
tenis moviĝas.

486
00:17:25,450 --> 00:17:27,710
Ili ne nur ĉesas, kiam ili
korektis unu problemo.

487
00:17:27,710 --> 00:17:27,839
Tiel.

488
00:17:27,839 --> 00:17:29,390
Ja, mi tuj devos
fari la samon.

489
00:17:29,390 --> 00:17:32,720
Mi tuj devos ordigi de rebobinado reen
al la komenco de ĉi tiu problemo,

490
00:17:32,720 --> 00:17:35,630
aŭ la komenco de ĉi tiu tabelo de
popolo, ni komencu nomante ilin.

491
00:17:35,630 --> 00:17:38,366
>> Kaj nun kio devus mia algoritmo
en la dua paŝo estu?

492
00:17:38,366 --> 00:17:39,220
>> Parolanto 1: Sama afero.

493
00:17:39,220 --> 00:17:39,940
>> DAVID J. Malan: Sama afero.

494
00:17:39,940 --> 00:17:41,460
Kaj jen, Mi komencas ŝatas, ĉu ne?

495
00:17:41,460 --> 00:17:44,720
Tuj kiam vi povos trovi vin mem fari
la sama afero denove kaj denove, tio estas

496
00:17:44,720 --> 00:17:47,890
igante pli kiel algoritmo,
kaj malpli homa instinkto.

497
00:17:47,890 --> 00:17:48,680
>> Do nun, ni tie iri denove.

498
00:17:48,680 --> 00:17:49,870
Du kaj kvar?

499
00:17:49,870 --> 00:17:50,220
No

500
00:17:50,220 --> 00:17:51,050
Kvar kaj unu?

501
00:17:51,050 --> 00:17:53,380
Ha, tie ja estis kelkaj
labori ankoraŭ farenda.

502
00:17:53,380 --> 00:17:53,620
Por kaj tri?

503
00:17:53,620 --> 00:17:54,572
Bona.

504
00:17:54,572 --> 00:17:56,000
Kvar kaj ses?

505
00:17:56,000 --> 00:17:58,380
Ses kaj kvin?

506
00:17:58,380 --> 00:17:59,470
Ses kaj sep?

507
00:17:59,470 --> 00:18:00,970
OK, nun faris.

508
00:18:00,970 --> 00:18:01,550
OK, ne.

509
00:18:01,550 --> 00:18:02,710
Mi devas iri reen.

510
00:18:02,710 --> 00:18:05,130
>> Do nun, denove, ni faras ĉi
iom pli intence.

511
00:18:05,130 --> 00:18:08,700
Kaj nun, estas nur unu cerbon
ekzekuti tiu algoritmo.

512
00:18:08,700 --> 00:18:10,290
CPU, se vi volas.

513
00:18:10,290 --> 00:18:13,090
Kaj sincere, ke estas la sola rimedo
Ni tuj havas aliron al.

514
00:18:13,090 --> 00:18:16,280
Kaj unufoje ni reiru al klavaro
kaj havi iun kiel C en nia

515
00:18:16,280 --> 00:18:19,600
dispozicio, ni nur skribi programon
kiu povas fari unu afero je tempo.

516
00:18:19,600 --> 00:18:22,900
Dum ĉi tiuj infanoj antaŭ momento, ni
leveraged ilia kolektiva cerbostreĉa

517
00:18:22,900 --> 00:18:24,180
kiel vi infanoj faris en semajno nulo.

518
00:18:24,180 --> 00:18:24,980
Do ni daŭre fari tion.

519
00:18:24,980 --> 00:18:26,260
>> Du kaj unu.

520
00:18:26,260 --> 00:18:26,945
Du kaj tri.

521
00:18:26,945 --> 00:18:27,460
Tri kaj kvar.

522
00:18:27,460 --> 00:18:28,310
Kvar kaj kvin.

523
00:18:28,310 --> 00:18:28,620
Kvin ses.

524
00:18:28,620 --> 00:18:30,510
Ses kaj sep.

525
00:18:30,510 --> 00:18:31,880
Faris?

526
00:18:31,880 --> 00:18:34,560
Do mi estas, sed lasu min ludi
advokato de la diablo.

527
00:18:34,560 --> 00:18:37,950
Ĉu Mi, la speco de komputilo kiu ĵus
faris pasas tra ĉi tiu tabelo de

528
00:18:37,950 --> 00:18:40,225
homoj, sciu ke mi faris?

529
00:18:40,225 --> 00:18:40,670
>> Parolanto 1: N-ro

530
00:18:40,670 --> 00:18:41,050
>> DAVID J. Malan: Do kial?

531
00:18:41,050 --> 00:18:46,900
Kion mi devas fari por
konkludi decide, ke mi faris?

532
00:18:46,900 --> 00:18:48,230
Probable pli pasas.

533
00:18:48,230 --> 00:18:48,430
Ĝuste?

534
00:18:48,430 --> 00:18:51,760
Pro ĉio mi scias el kiu antaŭaj
pass estas ke mi korektas eraron.

535
00:18:51,760 --> 00:18:53,920
Kaj tio signifas, eble tie estas
ankoraŭ alia eraro

536
00:18:53,920 --> 00:18:54,840
ke mi bezonas korekti.

537
00:18:54,840 --> 00:18:58,680
Do mi nur povas esti certa per rebobinado, kaj
tiam kontrolanta, unu al du, du kaj

538
00:18:58,680 --> 00:19:00,940
tri, tri kaj kvar, kvar kaj kvin,
kvin kaj ses, ses kaj sep.

539
00:19:00,940 --> 00:19:02,510
OK, nun mi faris nenian laboron.

540
00:19:02,510 --> 00:19:05,990
>> Mi povas certe memoras, ke mi ja ne faris
labori kun iu kiel variablon,

541
00:19:05,990 --> 00:19:06,975
ŝatas al int.

542
00:19:06,975 --> 00:19:12,490
Nomu ĝin svopoj, kaj se svopoj estas 0 kiam mi
tien, kaj gxi komencis je 0, tiam

543
00:19:12,490 --> 00:19:15,520
Mi estus nur stulta plu iri
tien kaj reen, kontrolanta denove, kaj

544
00:19:15,520 --> 00:19:16,450
denove, kaj denove, ĉu ne?

545
00:19:16,450 --> 00:19:18,450
Ĉar vi get ŝtopita en kelkaj
speco de senfina iteracio.

546
00:19:18,450 --> 00:19:21,250
Tuj, kiam ekzistas 0 svopoj,
ni povas aserti, ke tiu

547
00:19:21,250 --> 00:19:23,810
algoritmo estas ja kompleta.

548
00:19:23,810 --> 00:19:25,400
>> Nun, ni metis nomon sur tiu ĉi.

549
00:19:25,400 --> 00:19:28,930
La algoritmo, kiun Mi proponas ke ni nur
implementado estas iu nomita bobelo

550
00:19:28,930 --> 00:19:32,800
varon, konata kiel tiaj en la senco ke
la numeroj kiuj estas pli grandaj speco de

551
00:19:32,800 --> 00:19:37,990
bobelo sian vojon sur la supron, aŭ supren
al la fino de la tabelo de nombroj.

552
00:19:37,990 --> 00:19:40,270
Sed kiom efika estis jena algoritmo?

553
00:19:40,270 --> 00:19:44,600
Kiom da ŝtupoj ĉu mi fizike devas
prenu, ekzemple, ordigi tiujn

554
00:19:44,600 --> 00:19:45,850
sep homoj?

555
00:19:45,850 --> 00:19:48,560

556
00:19:48,560 --> 00:19:49,550
>> Kvar al kvin?

557
00:19:49,550 --> 00:19:51,420
OK, tro multaj estas finfine
tuj estos la respondo.

558
00:19:51,420 --> 00:19:54,960
Sed eĉ tiam, la specifa nombro
ne estas tiom interesa.

559
00:19:54,960 --> 00:19:56,670
Ni ĝeneraligi ĝin kiel n.

560
00:19:56,670 --> 00:20:00,520
Do, se mi n popolon tien, kaj ili
estis, ia, en hazarda ordo en la

561
00:20:00,520 --> 00:20:02,180
komencante, en tiu originala ordo.

562
00:20:02,180 --> 00:20:04,910
Nu, kiom da ŝtupoj ĉu mi devas
preni sur la unua paŝo?

563
00:20:04,910 --> 00:20:09,810
Ĝi estis unu, du, tri, kvar, kvin,
ses, kaj ili estas sep personoj, tiel

564
00:20:09,810 --> 00:20:13,670
jen sep, ses -, do tio n
minus unu paŝas la unua fojo.

565
00:20:13,670 --> 00:20:16,280
>> Nun, kiom da ŝtupoj ĉu mi devas
preni kiam mi rewound?

566
00:20:16,280 --> 00:20:19,310
Nu, ni povus efektive duobligi ke se
Ni vere volis, sed por nun mi estas

567
00:20:19,310 --> 00:20:22,300
nur intencas diri, ĉiuj pravas,
alia n minus 1.

568
00:20:22,300 --> 00:20:25,240
Do la n minus 1 tuj akiri
ĝena por sekvigi, do ni

569
00:20:25,240 --> 00:20:26,400
nur rastas iomete.

570
00:20:26,400 --> 00:20:27,770
Do 2n paŝoj.

571
00:20:27,770 --> 00:20:29,310
Do 14 paŝoj, donos nek preni.

572
00:20:29,310 --> 00:20:31,930
>> Multfoje prenis mi
paŝo la venonta tempo?

573
00:20:31,930 --> 00:20:33,740
Nu, estas 3n.

574
00:20:33,740 --> 00:20:34,510
vere.

575
00:20:34,510 --> 00:20:37,920
Kaj nun, en la plej malbona kazo,
Ekzemple, kiom da fojoj mi volis havi

576
00:20:37,920 --> 00:20:41,730
iris tien kaj reen, tien kaj reen,
ekzekuti tiu algoritmo, interŝanĝante

577
00:20:41,730 --> 00:20:44,620
homoj sur ĉiu paŝo, proksimume?

578
00:20:44,620 --> 00:20:47,720

579
00:20:47,720 --> 00:20:50,010
Ĝi estas fakte n kvadratoj, ĉu ne?

580
00:20:50,010 --> 00:20:53,000
>> Ĉar en la plej malbona kazo, vi povas speco
de opinias pri tiu intuicie,

581
00:20:53,000 --> 00:20:54,800
kvankam ĝi povus preni iom
iom da tempo por enprofundigi in

582
00:20:54,800 --> 00:20:57,590
En la plej malbona kazo, kio estus tiuj
sep homoj aspektis kiel, en

583
00:20:57,590 --> 00:21:00,230
kondiĉoj de la aranĝo
de siaj ciferoj?

584
00:21:00,230 --> 00:21:01,460
Tute malantaŭen, ĉu ne?

585
00:21:01,460 --> 00:21:02,815
Kaj ĝuste por simuli tion,
kio estas via nomo denove?

586
00:21:02,815 --> 00:21:03,360
>> MIKE: Mike.

587
00:21:03,360 --> 00:21:03,640
>> DAVID J. Malan: Mike?

588
00:21:03,640 --> 00:21:08,100
OK, Mike, vi povas simple aliĝi min super
ĉi tie dum nur unu dua?

589
00:21:08,100 --> 00:21:08,880
Efektive, ne.

590
00:21:08,880 --> 00:21:10,150
Pardonu Mike, ni rebobinado.

591
00:21:10,150 --> 00:21:10,910
Kio estas via nomo denove?

592
00:21:10,910 --> 00:21:11,180
>> Neil: Neil.

593
00:21:11,180 --> 00:21:11,640
>> DAVID J. Malan: Neil.

594
00:21:11,640 --> 00:21:13,750
OK, Neil, vi venos kun
min, se vi ne gravas.

595
00:21:13,750 --> 00:21:17,150
Do mi tuj proponi, nur por
simpleco, ke Neil estas nun en siaj

596
00:21:17,150 --> 00:21:18,510
plej malbona ebla kazo.

597
00:21:18,510 --> 00:21:20,720
Sed memoru, kiel mi implementado
mia algoritmo.

598
00:21:20,720 --> 00:21:24,530
Mi komparas, komparante, komparante,
komparante, komparante, oh.

599
00:21:24,530 --> 00:21:26,640
Nun tiuj infanoj estas ekstere
de ordo, do mi ripari.

600
00:21:26,640 --> 00:21:27,980
Do you guys interŝanĝi.

601
00:21:27,980 --> 00:21:31,630
Sed pripensu nun, kiom pli malproksima
tio Neil devas iri?

602
00:21:31,630 --> 00:21:32,690
Ĝi estas proksimume n.

603
00:21:32,690 --> 00:21:33,570
Vi scias, ĝi estas ne reale n.

604
00:21:33,570 --> 00:21:36,040
Estas kiel, n minus 1, sed mi ricevas
tedita konservanta trako de la eta

605
00:21:36,040 --> 00:21:37,550
nombro, do ni nur nomas ĝin n.

606
00:21:37,550 --> 00:21:42,860
>> Do se Neil movas unu paŝon maksimume ĉiu
tempo, kaj movi unu paŝon Neil,

607
00:21:42,860 --> 00:21:46,580
Mi devas fari ĉi vere teda pass
tien kaj reen, ĉi tiu estas krude

608
00:21:46,580 --> 00:21:52,080
faranta tion, n paŝoj, entute n fojoj,
ĉar ĝi estas tuj portos min

609
00:21:52,080 --> 00:21:55,820
ke multaj ŝtupoj por atingi Neil ĉiuj
la vojo, kie li apartenas.

610
00:21:55,820 --> 00:21:58,620
Lasu ĉiuj aliaj se vi infanoj
ĉiuj estis mis-ordigita tiel.

611
00:21:58,620 --> 00:22:01,100
>> Do ni nomas bobelo speco n kvadratoj.

612
00:22:01,100 --> 00:22:04,860
La rula tempo de ĉi tiu algoritmo, la
okupas de ĉi tiu algoritmo, la

613
00:22:04,860 --> 00:22:07,120
efikeco de ĉi tiu algoritmo,
ni estos ĝuste priskribi pli

614
00:22:07,120 --> 00:22:08,800
ĝenerale kiel n akordis.

615
00:22:08,800 --> 00:22:11,650
Kiu estas bela, ĉar mi povis fari la
sama ekzemplo kun ok personoj, naŭ

616
00:22:11,650 --> 00:22:15,450
popolo, miliono da homoj, kaj ke
respondo ne tuj ŝanĝos.

617
00:22:15,450 --> 00:22:18,870
>> Do se vi infanoj ne gravas, ni
reset vi kie vi komencis.

618
00:22:18,870 --> 00:22:22,510
Kaj ni provu du aliaj aliroj kaj
ĉu ni ne povas fari funde

619
00:22:22,510 --> 00:22:23,820
pli bona ol ĉi tio.

620
00:22:23,820 --> 00:22:27,130
Do ĉi tiu fojo, mi tuj proponi
speco de malsamaj algoritmo.

621
00:22:27,130 --> 00:22:29,950
Tio estis tre saĝa el ni lasta fojo,
kaj vi infanoj pravis havi la

622
00:22:29,950 --> 00:22:32,470
dekstra instinktoj de nur speco
de swapping duoplarĝa.

623
00:22:32,470 --> 00:22:36,500
Sed se mi vere volis alproksimigi tiun
simple, kaj mia celo estas movi

624
00:22:36,500 --> 00:22:39,800
ĉiuj iom nombroj ĉi vojo kaj
puŝi ĉiuj el la grandaj numeroj kiu

625
00:22:39,800 --> 00:22:43,030
maniero, kial ne mi nur faras tion en la
plej naiva maniero ebla kaj vidu se mi

626
00:22:43,030 --> 00:22:45,730
povas fari pli bone ol kio estis
sufiĉe kompleksa algoritmo?

627
00:22:45,730 --> 00:22:46,620
>> Do ni vidu.

628
00:22:46,620 --> 00:22:48,940
Kvar estas sufiĉe malgranda nombro, do mi estas
tuj forlasos vin tie momento.

629
00:22:48,940 --> 00:22:50,610
Ooh, numero du estas eĉ pli bona.

630
00:22:50,610 --> 00:22:52,230
Do vi povas simple paŝas antaŭen
nur momenta?

631
00:22:52,230 --> 00:22:55,670
Ĉi tio estas nuntempe mia malgranda prikalkulis
kandidato, kaj mi iros por memori

632
00:22:55,670 --> 00:22:57,000
ke kun, kiel, variablo.

633
00:22:57,000 --> 00:22:57,930
Sed mi tuj subteni kontrolanta.

634
00:22:57,930 --> 00:22:59,890
Ĉu estas iu kies
nombro estas malgranda?

635
00:22:59,890 --> 00:23:00,460
Ses, ne.

636
00:23:00,460 --> 00:23:01,390
Ho, tie estas Neil denove.

637
00:23:01,390 --> 00:23:04,050
>> Do mi tuj peli vin
speco de koncepte.

638
00:23:04,050 --> 00:23:05,120
Neil venos plue.

639
00:23:05,120 --> 00:23:08,440
Kaj nun, la variablo kiu Mi uzas por
sekvigi kiu havas la plej malgrandan

640
00:23:08,440 --> 00:23:11,390
nombro estas ĝisdatigita enhavi
Neil loko.

641
00:23:11,390 --> 00:23:12,110
Nu, vidu.

642
00:23:12,110 --> 00:23:13,960
Tri, sep, kvin.

643
00:23:13,960 --> 00:23:15,590
Bone, mi scias Neil estis la plej malgranda.

644
00:23:15,590 --> 00:23:18,110
Kio estas la plej simpla afero
al mi, fari nun?

645
00:23:18,110 --> 00:23:21,410
Mi ne tuj malŝparos mian tempon por nur
bobelis Neil unu loko al la maldekstra.

646
00:23:21,410 --> 00:23:25,350
Kial ne Mi nur metis Neil kie li
apartenas, kiu estas kompreneble kie?

647
00:23:25,350 --> 00:23:26,160
>> Tuta vojo al la komenco.

648
00:23:26,160 --> 00:23:27,720
Do Neil, venu kun mi.

649
00:23:27,720 --> 00:23:28,910
Kaj kio estis via nomo denove?

650
00:23:28,910 --> 00:23:29,310
>> GRACIA: Graco.

651
00:23:29,310 --> 00:23:29,710
>> DAVID J. Malan: Graco.

652
00:23:29,710 --> 00:23:29,920
Akcepti.

653
00:23:29,920 --> 00:23:32,490
Do Graco, bedaŭrinde, vi estas
speco de la vojo.

654
00:23:32,490 --> 00:23:34,290
Nu do kiel ni solvi tiun problemon?

655
00:23:34,290 --> 00:23:34,490
Ĝuste?

656
00:23:34,490 --> 00:23:37,500
Se tio estas tabelo, ekzistas
nur sep lokoj.

657
00:23:37,500 --> 00:23:40,830
Memoru ke, kun Rob, ni parolis pri
deklarante aĝoj, kaj ni nur havis

658
00:23:40,830 --> 00:23:41,740
finia nombro de aĝoj?

659
00:23:41,740 --> 00:23:42,535
Sama ideo tie.

660
00:23:42,535 --> 00:23:44,300
Ni havas nur finia nombro de ints.

661
00:23:44,300 --> 00:23:47,590
Graco estas speco de en nia
maniero, tiel kiel ni ripari?

662
00:23:47,590 --> 00:23:49,555
>> La plej simpla maniero estas kiel,
Graco, sorry.

663
00:23:49,555 --> 00:23:51,870
Vi tuj devas iri super
tie do ni povas fari ĉambro.

664
00:23:51,870 --> 00:23:55,290
Nun, se vi opinias pri tio, eble
Ni ĵus faris la problemo malbona.

665
00:23:55,290 --> 00:23:58,510
Kaj eble ni faris, ĉar kion se
Graco estis en la gxusta loko?

666
00:23:58,510 --> 00:24:01,730
Sed ni scias, ŝi ne, ĉar
alie, estus estinta

667
00:24:01,730 --> 00:24:03,980
staras antaŭen anstataŭ
Neil tiun fojon, ĉu ne?

668
00:24:03,980 --> 00:24:05,550
Ni jam kontrolis sian numeron eksteren.

669
00:24:05,550 --> 00:24:05,770
>> Ĉio bone.

670
00:24:05,770 --> 00:24:09,110
Do nun, Neil estas en la ĝusta loko, kaj
Mi povas fari etan optimumigo.

671
00:24:09,110 --> 00:24:11,740
Por la sekvan minuton, mi tuj ignori
Neil ĉiuj kune, por ne

672
00:24:11,740 --> 00:24:15,280
malŝpari sian tempon, aŭ hazarde
interŝanĝi lin al la malĝusta loko.

673
00:24:15,280 --> 00:24:17,805
Do nun, kiel mi trovos la sekvanta
elemento kiu estas plej malgranda?

674
00:24:17,805 --> 00:24:18,480
Du.

675
00:24:18,480 --> 00:24:20,225
Tio estas sufiĉe bona numero, se
vi volas treti antaŭen kaj

676
00:24:20,225 --> 00:24:21,100
Mi memoras vin.

677
00:24:21,100 --> 00:24:21,980
Ses, neniu bona.

678
00:24:21,980 --> 00:24:24,820
Kvar, tri, sep, kvin, ne bona.

679
00:24:24,820 --> 00:24:26,800
Do lasu min movi vin
via ĝusta loko.

680
00:24:26,800 --> 00:24:28,470
Kaj ni ĵus bonŝanca ĉi tiu tempo.

681
00:24:28,470 --> 00:24:31,350
>> Nu, mi tuj ignori tiujn
du infanoj, kaj nun faras pli

682
00:24:31,350 --> 00:24:32,260
trapasi ĉi.

683
00:24:32,260 --> 00:24:33,490
Ses, ke bela malgranda nombro.

684
00:24:33,490 --> 00:24:34,300
Venu antaŭen.

685
00:24:34,300 --> 00:24:35,220
Ho, pardonu.

686
00:24:35,220 --> 00:24:37,640
Grace nombro estas pli bone,
do tretas antaŭen.

687
00:24:37,640 --> 00:24:38,260
Kvar.

688
00:24:38,260 --> 00:24:39,120
Pardonu, Grace.

689
00:24:39,120 --> 00:24:39,950
Iru returne.

690
00:24:39,950 --> 00:24:41,550
Numero tri estas bona.

691
00:24:41,550 --> 00:24:42,290
Sep.

692
00:24:42,290 --> 00:24:42,720
Kvin.

693
00:24:42,720 --> 00:24:43,550
Kaj nun kio estas via nomo denove?

694
00:24:43,550 --> 00:24:44,000
>> JASON: Jason.

695
00:24:44,000 --> 00:24:44,420
>> DAVID J. Malan: Jason.

696
00:24:44,420 --> 00:24:47,050
Do Jason estas nun la plej malgranda
elemento mi elektitaj.

697
00:24:47,050 --> 00:24:49,160
Kie estas tiu tuj iros?

698
00:24:49,160 --> 00:24:50,380
Do kie ses estas.

699
00:24:50,380 --> 00:24:51,210
Kaj via nomo estas denove?

700
00:24:51,210 --> 00:24:51,710
>> Gabe: Gabe.

701
00:24:51,710 --> 00:24:52,340
>> DAVID J. Malan: Gabe.

702
00:24:52,340 --> 00:24:53,220
Gabe estas en la vojo.

703
00:24:53,220 --> 00:24:54,640
Kio estas la plej facila afero por fari?

704
00:24:54,640 --> 00:24:58,390
Interŝanĝi tiujn du infanoj kaj daŭrigi.

705
00:24:58,390 --> 00:24:59,020
Do nun ni vidu.

706
00:24:59,020 --> 00:25:00,170
Kiu estas la plej malgranda?

707
00:25:00,170 --> 00:25:01,030
Kvar.

708
00:25:01,030 --> 00:25:01,990
Lasu min nur speco de cheat.

709
00:25:01,990 --> 00:25:03,090
Kvin tuj estos la plej malgranda.

710
00:25:03,090 --> 00:25:05,220
Mi trovas proksima, se vi volas treti
antaŭen, kion mi devas fari kun

711
00:25:05,220 --> 00:25:06,820
ĉi tiuj infanoj, kun Gabe?

712
00:25:06,820 --> 00:25:08,450
Interŝanĝi denove.

713
00:25:08,450 --> 00:25:10,740
Do nun, ankoraŭ iomete el ordo.

714
00:25:10,740 --> 00:25:14,140
Mi trovis Gabe esti la plej malgranda, tiel
Mi pop lin eksteren, movi vin infanoj super.

715
00:25:14,140 --> 00:25:15,190
Kaj faris.

716
00:25:15,190 --> 00:25:17,200
>> Do respondo estas la sama.

717
00:25:17,200 --> 00:25:18,600
La fina rezulto estas la sama.

718
00:25:18,600 --> 00:25:22,730
Kiu el tiuj du algoritmoj
estas pli bona?

719
00:25:22,730 --> 00:25:23,500
La dua, mi aŭdis.

720
00:25:23,500 --> 00:25:24,252
Kial?

721
00:25:24,252 --> 00:25:25,900
>> Parolanto 3: Oni n paŝoj [inaudibles].

722
00:25:25,900 --> 00:25:27,600
>> DAVID J. Malan: Estas n paŝojn maksimume.

723
00:25:27,600 --> 00:25:28,490
Interesa.

724
00:25:28,490 --> 00:25:30,610
Do ĉu kvankam?

725
00:25:30,610 --> 00:25:33,630
Do kiamaniere mi trovas la
plej malgranda elemento?

726
00:25:33,630 --> 00:25:37,060
Kiom da ŝtupoj ĉu mi devas preni
la trovos la plej malgranda ero?

727
00:25:37,060 --> 00:25:39,220
Mi havis rigardi la tuta vojo
fine, ĉu ne?

728
00:25:39,220 --> 00:25:41,530
Ĉar en tiu plej malbona kazo, kion
se Neil estis super ĉi tie?

729
00:25:41,530 --> 00:25:45,700
Do ĝuste trovi la plej malgranda ero
prenas min n paŝoj, aŭ n minus 1.

730
00:25:45,700 --> 00:25:46,100
Sed, OK.

731
00:25:46,100 --> 00:25:46,980
Do ripari Neil.

732
00:25:46,980 --> 00:25:48,740
Memoru ke, unu minuton antaŭe.

733
00:25:48,740 --> 00:25:51,680
>> Sed kiel mi trovos la sekvanta
plej malgranda elemento?

734
00:25:51,680 --> 00:25:54,830
Estas n minus 1, aŭ n minus 2 vere,
de la nombro de paŝoj.

735
00:25:54,830 --> 00:25:55,440
Do okej.

736
00:25:55,440 --> 00:25:57,390
Do mi n minus 2.

737
00:25:57,390 --> 00:25:57,600
Ĉio bone.

738
00:25:57,600 --> 00:25:59,130
Do kiu sentas iom pli bone.

739
00:25:59,130 --> 00:25:59,730
Ĉio bone.

740
00:25:59,730 --> 00:26:03,270
Kiom da paŝoj la proksima fojo
trovi numero tri?

741
00:26:03,270 --> 00:26:04,420
Do la n minus 4.

742
00:26:04,420 --> 00:26:07,670
Do ĝi estas malkreskanta, unu malpli
treti ĉiu ripeto.

743
00:26:07,670 --> 00:26:08,740
Do tio ne senti pli bona, ĉu ne?

744
00:26:08,740 --> 00:26:13,450
Se lasta tempo estis krude n × n,
ĉi tiu tempo estas n minus 1, plus n minus

745
00:26:13,450 --> 00:26:16,500
2, plus n minus 3, plus n
minus 4, punkto, ĝi pentras, ĝi pentras.

746
00:26:16,500 --> 00:26:18,750
Sed se vi memoras el via alta lernejo
lernolibroj, la eta cheat

747
00:26:18,750 --> 00:26:24,380
folion en la fono kiu havas formuloj, se
vi aldonas tiun serio de nombroj,

748
00:26:24,380 --> 00:26:31,280
kio estas la tuteca kvanto de paŝoj
tuj estos ke mi prenu ĉi tie?

749
00:26:31,280 --> 00:26:36,580
>> Tiu estas unu el tiuj, kiel, n minus
1, tempoj n, dividita per 2.

750
00:26:36,580 --> 00:26:39,040
Do lasu min vidi se mi povas tiri
ĉi supre por nur momento.

751
00:26:39,040 --> 00:26:42,230
Kaj denove, mi estas speco de rondigo iuj
nombroj nur por teni nian vivon simpla,

752
00:26:42,230 --> 00:26:47,830
sed kiel mi memoras, estas io kiel se
Mi faras n minus 1 aĵojn, tiam n minus

753
00:26:47,830 --> 00:26:53,570
2, tiam n minus 3, estas krude
iu kiel tiu super 2, kaj se mi

754
00:26:53,570 --> 00:26:55,510
multipliki ĉi tiu ekster, jen
fakte n kvadrata.

755
00:26:55,510 --> 00:26:58,940
Tio ne sentante tro bona.
n minus n super 2.

756
00:26:58,940 --> 00:27:00,350
>> Sed jen la afero.

757
00:27:00,350 --> 00:27:03,720
En komputiko, kiam la problemoj
komencu akiri interesa estas kiam n

758
00:27:03,720 --> 00:27:04,700
ricevas vere granda.

759
00:27:04,700 --> 00:27:08,110
Kaj kiam n ricevas vere granda, kiu el
ĉi tiuj valoroj tuj regi ĉiujn

760
00:27:08,110 --> 00:27:09,750
de la aliaj?

761
00:27:09,750 --> 00:27:10,990
Ĝi estas speco de la n kvadratoj, ĉu ne?

762
00:27:10,990 --> 00:27:13,340
Jes, dividanta per 2 estas sufiĉe bonaj.

763
00:27:13,340 --> 00:27:16,740
Sed se vi parolas pri miliardoj
de pecoj de datumoj, aŭ bilionoj de

764
00:27:16,740 --> 00:27:18,700
pecoj de datumo, okej, do
vi estas duoble pli rapide.

765
00:27:18,700 --> 00:27:22,440
Sed kiu vere zorgas se tiu granda nombro,
se tiu faktoro estas kion ricevas

766
00:27:22,440 --> 00:27:23,040
pli kaj pli granda.

767
00:27:23,040 --> 00:27:25,990
Kaj certe, faras pli
diferenco ol tiu ulo.

768
00:27:25,990 --> 00:27:29,120
Do kvankam vi infanoj pravas, la
dua algoritmo, ni nomas ĝin

769
00:27:29,120 --> 00:27:32,970
selektado varon, estas, en la reala mondo,
iom pli rapide potenciale, ĉar mi estas

770
00:27:32,970 --> 00:27:35,360
preni malpli kaj malpli
paŝas ĉiufoje.

771
00:27:35,360 --> 00:27:37,340
>> Ĝi estas ne vere funde rapida.

772
00:27:37,340 --> 00:27:41,430
Ĉar se ni reale ludi ĉi eliris por
grandaj valoroj de n, fine de

773
00:27:41,430 --> 00:27:44,750
la tago, por sufiĉe granda n, ĝi estas ankoraŭ
tuj sentos sufiĉe malrapidaj.

774
00:27:44,750 --> 00:27:46,770
Nu, mi prenas unu
lasta paŝo en tiu.

775
00:27:46,770 --> 00:27:48,920
Tion mi nomus
selektado varo.

776
00:27:48,920 --> 00:27:51,040
Can you guys retrovu vin
unu lastan fojon?

777
00:27:51,040 --> 00:27:53,550
Kaj en ĉi tiu lasta kazo, mi tuj
proponi ion

778
00:27:53,550 --> 00:27:54,970
vokis inserción varo.

779
00:27:54,970 --> 00:27:57,470
Insertion speco esti, koncepte,
iom malsama.

780
00:27:57,470 --> 00:28:00,980
>> Anstataŭ iri tien kaj reen kaj
elektante la plej malgranda ero, mi estas

781
00:28:00,980 --> 00:28:05,030
nur tuj trakti kun ĉiu de ĉi tiuj
infanoj kiel mi renkontas ilin, kaj enmeti

782
00:28:05,030 --> 00:28:06,850
ilin en ilia ĝusta loko.

783
00:28:06,850 --> 00:28:10,160
Do mi simple tuj komenci kun Grace,
kaj mi vidas ke ŝi estas la numero kvar.

784
00:28:10,160 --> 00:28:11,720
Kie numero kvar apartenas?

785
00:28:11,720 --> 00:28:14,940
Mi ne komencis ordigi nenion,
tial Grace ricevas resti rajton tie.

786
00:28:14,940 --> 00:28:18,355
Kaj nun mi iras al postuli, se vi povus
paŝon al via dekstra, ĉi

787
00:28:18,355 --> 00:28:21,650
mia ordo listo, ĉi tiu estas mia
unsorted ceteraj listo.

788
00:28:21,650 --> 00:28:23,260
Do nun mi iros al procedi proksima,
kaj kio estas via nomo denove?

789
00:28:23,260 --> 00:28:23,700
>> Branson: Branson.

790
00:28:23,700 --> 00:28:24,150
>> DAVID J. Malan: Branson.

791
00:28:24,150 --> 00:28:25,375
Do Branson estas numero du.

792
00:28:25,375 --> 00:28:27,490
Do mi tuj prenos vin
dum momento.

793
00:28:27,490 --> 00:28:30,940
Kaj nun, kie vi apartenas
en ĉi tiu tabelo?

794
00:28:30,940 --> 00:28:32,360
Do por la rajto de Graco.

795
00:28:32,360 --> 00:28:35,670
Do denove, ni estas speco de fari
Graco faras multan laboron tie.

796
00:28:35,670 --> 00:28:37,290
Kie ni metos vin?

797
00:28:37,290 --> 00:28:40,120
Do ni iras gliti vin al la
restis, kaj enigi Branson tie.

798
00:28:40,120 --> 00:28:41,680
Sed nun mi asertas ke
you guys estas farita.

799
00:28:41,680 --> 00:28:43,240
Sed avizo, mi ne uzas ekstra spaco.

800
00:28:43,240 --> 00:28:45,130
Ĝi estas ankoraŭ 2 eroj
ĉi tie, 5 pli ol ĉi tie.

801
00:28:45,130 --> 00:28:47,910
Sumo tabelo grandeco estas 7, do mi estas
ne trompas, ĉiuj rajtas?

802
00:28:47,910 --> 00:28:51,950
>> Do nun ni havas, kun Gabe tie, la
numero ses, kie vi apartenas?

803
00:28:51,950 --> 00:28:52,650
You got bonŝanca denove.

804
00:28:52,650 --> 00:28:53,820
Do vi ricevas resti rajton tie.

805
00:28:53,820 --> 00:28:57,210
Nur prenu malpeza paŝo al la ĝusta
nur por klarigi ke vi ordo.

806
00:28:57,210 --> 00:29:00,520
Kaj nun ni havas Neil denove, numero
unu, kie vi iras?

807
00:29:00,520 --> 00:29:03,540
Kaj nun estas kie ni komencos vidi ke
ĉi tiu algoritmo, kvankam en la unua

808
00:29:03,540 --> 00:29:05,950
rigardo, sentas sufiĉe inteligenta, rigardi
kio estas okazonta.

809
00:29:05,950 --> 00:29:07,370
Se vi povus treti antaŭen.

810
00:29:07,370 --> 00:29:09,260
>> Kie ni volas meti Neil?

811
00:29:09,260 --> 00:29:11,830
Do evidente ĉi tie, do kiel
do ni preni Neil tie?

812
00:29:11,830 --> 00:29:12,970
Ni faras tiun paŝon post iom.

813
00:29:12,970 --> 00:29:15,620
Gabe, kie vi devas iri?

814
00:29:15,620 --> 00:29:19,590
Yep, do prenu unu granda paŝo,
aŭ du duon-ŝtupoj por fari

815
00:29:19,590 --> 00:29:20,820
unu paŝon tie.

816
00:29:20,820 --> 00:29:21,750
Graco, kie vi iras?

817
00:29:21,750 --> 00:29:22,510
Bona.

818
00:29:22,510 --> 00:29:23,500
Do alia paŝo.

819
00:29:23,500 --> 00:29:24,960
Kaj fine, Branson?

820
00:29:24,960 --> 00:29:25,460
Alia paŝo.

821
00:29:25,460 --> 00:29:27,190
Kaj nun ni povas meti Neil en loko.

822
00:29:27,190 --> 00:29:28,440
>> Do nun, daŭrigu tiun logikon.

823
00:29:28,440 --> 00:29:32,420
Eĉ se ni ne sxangxigxantaj Neil
plus, plus plus metu lin

824
00:29:32,420 --> 00:29:36,420
kie li iras, en la plej malbona kazo, la
sekva numero ni povus renkonti povis

825
00:29:36,420 --> 00:29:42,220
estu la numero, diras, estis numero
nulo, tiam ni tuj ŝanĝi ĉiujn

826
00:29:42,220 --> 00:29:42,730
ĉi tiuj infanoj.

827
00:29:42,730 --> 00:29:44,950
Supozu ke estas kelkaj, negativa
unu, tiam ni devas ŝanĝi

828
00:29:44,950 --> 00:29:46,080
ĉiuj de ĉi tiuj infanoj.

829
00:29:46,080 --> 00:29:48,500
Do ni estas vere nur speco de klakanta
la problemo ĉirkaŭe, tia, ke ni estas

830
00:29:48,500 --> 00:29:52,620
trapasante la elspezo de la
procezo de selektado por la inserción

831
00:29:52,620 --> 00:29:56,930
procezo, tia ke vi infanoj ĵus havis
movi malglate n minus ion

832
00:29:56,930 --> 00:29:57,940
nombro da paŝoj.

833
00:29:57,940 --> 00:30:01,200
Kaj tiu numero de paŝoj nur tuj
pliigi kiel mi elektu pli nombroj,

834
00:30:01,200 --> 00:30:04,730
se mi devas gardi shoving you guys
dorso, kaj reen, kaj reen.

835
00:30:04,730 --> 00:30:08,320
>> Do la malĝoja afero nun estas ĉiuj de ĉi tiuj
algoritmoj n kvadratoj.

836
00:30:08,320 --> 00:30:10,570
Ni iru antaŭen kaj dankon al tiuj
knaboj, kaj bildigi tiujn iom

837
00:30:10,570 --> 00:30:11,090
malsame.

838
00:30:11,090 --> 00:30:12,312
Tre bone farita.

839
00:30:12,312 --> 00:30:14,120
>> [Aplaŭdo]

840
00:30:14,120 --> 00:30:15,030
>> Ĉio bone.

841
00:30:15,030 --> 00:30:16,280
Tie vi iros.

842
00:30:16,280 --> 00:30:18,390

843
00:30:18,390 --> 00:30:18,470
Dankon por -

844
00:30:18,470 --> 00:30:19,190
>> Branson: [inaudibles] konservi la numeroj.

845
00:30:19,190 --> 00:30:21,990
>> DAVID J. Malan: Ne, vi rajtas
observos la numerojn tiel.

846
00:30:21,990 --> 00:30:23,440
Ĉio bone.

847
00:30:23,440 --> 00:30:24,100
Bele farita.

848
00:30:24,100 --> 00:30:25,300
Ĉio bone.

849
00:30:25,300 --> 00:30:30,510
Do ni vidu se ni ne povas nun resumi
pli rapide, kaj pli vide,

850
00:30:30,510 --> 00:30:33,410
ĝuste kio ĵus okazis
tie kiel sekvas.

851
00:30:33,410 --> 00:30:36,510

852
00:30:36,510 --> 00:30:38,770
Mi tuj iros antaŭen
kaj elsxiros Firefox.

853
00:30:38,770 --> 00:30:41,310
Ni ligi tiu pruvo
en la kurso de afiŝinto.

854
00:30:41,310 --> 00:30:43,870
Java estas iom ĝena to get laborante
en iuj retumiloj tiuj tagoj.

855
00:30:43,870 --> 00:30:46,760
Do se vi ludos kun ĉi hejme,
realigi vi eble bezonas uzi Firefox

856
00:30:46,760 --> 00:30:47,990
akiri ĝin funkcii.

857
00:30:47,990 --> 00:30:50,440
Kaj kion mi faros kun ĉi
pruvo estas la jena.

858
00:30:50,440 --> 00:30:54,875
>> Funde, mi havas tutan faskon da
menuo ebloj, inkludante komenco kaj

859
00:30:54,875 --> 00:30:55,840
halti butonon.

860
00:30:55,840 --> 00:30:59,450
Ankaŭ, kiel flanken, ne ŝajnas esti
cimo en tiuj programoj, per kiu vi

861
00:30:59,450 --> 00:31:03,720
ne povas vere vidi la komenco aŭ ĉesi
butono krom se vi tenas Ordonu aŭ Alt

862
00:31:03,720 --> 00:31:06,560
pli kaj zomi, kiu scivoleme
montras al vi pli da butonoj.

863
00:31:06,560 --> 00:31:09,090
Do ĝuste FYI se vi ludas
kun tiu en la hejmo.

864
00:31:09,090 --> 00:31:12,870
Nun mi iros al klaku Komenco en nur
momento, post preciziganta malfruo de,

865
00:31:12,870 --> 00:31:16,810
kiel, 200 milisekundoj tien, simple
tiel ni povas vidi kio okazas.

866
00:31:16,810 --> 00:31:20,180
>> Do mi asertas ke ĉi tiu estas videbligo
de la unua algoritmo

867
00:31:20,180 --> 00:31:23,730
ĉi tiuj infanoj faris, bobelo varon, per kiu
Ni interŝanĝis homoj paro-saĝa.

868
00:31:23,730 --> 00:31:27,490
La ŝlosilo enrigardo al ĉi videbligo
estas ke la alteco de la stangoj

869
00:31:27,490 --> 00:31:30,510
reprezentas la grandeco de la nombro.

870
00:31:30,510 --> 00:31:32,210
Do la altkreska la trinkejo, la
pli granda la nombro.

871
00:31:32,210 --> 00:31:33,680
Shorter la trinkejo, pli malgranda la nombro.

872
00:31:33,680 --> 00:31:38,630
Kaj se vi rimarkas, ni iras tra
la unua ripeto de ĉi tiu algoritmo,

873
00:31:38,630 --> 00:31:42,620
swapping grandaj kaj malgrandaj nombroj, por ke
la malgranda nombro venas unue kaj

874
00:31:42,620 --> 00:31:44,280
la granda nombro iras dekstre.

875
00:31:44,280 --> 00:31:48,770
>> Kaj tuj kiam ni atingas la finon de tabelo
de multaj pli nombroj ol sep, ni estas

876
00:31:48,770 --> 00:31:49,900
tuj reiros al la komenco.

877
00:31:49,900 --> 00:31:51,140
Kaj anticipi tion.

878
00:31:51,140 --> 00:31:54,860
Sur la malantaŭa maldekstra, ke iom ulo tuj
por interŝanĝi al la flanko, kaj ĉi

879
00:31:54,860 --> 00:31:56,010
procezo ripetas.

880
00:31:56,010 --> 00:31:59,450
Nun ĉi videbligo rapide akiras
enuiga, tiel lasu min antaŭeniri kaj halti

881
00:31:59,450 --> 00:32:04,170
ĝin, ŝanĝi la malfruo io multe
rapida nur por akiri nun, emo al

882
00:32:04,170 --> 00:32:05,060
tiu algoritmo.

883
00:32:05,060 --> 00:32:07,840
>> Do eĉ se mi rapidis ĝin, tio estas
kiel ĝisdatigo mia procesoro, aĉetante

884
00:32:07,840 --> 00:32:08,580
nova komputilo.

885
00:32:08,580 --> 00:32:12,980
Mi ne funde ŝanĝiĝis mia
algoritmo, sed vi povas ja vidi pli

886
00:32:12,980 --> 00:32:16,800
klare, ol kun homoj, ke la granda
nombroj estas bobelis ĝis la supro,

887
00:32:16,800 --> 00:32:20,900
kaj la malgrandaj nombroj estas bobelis
malsupren al la fundo.

888
00:32:20,900 --> 00:32:22,390
Kaj nun tiu afero ĉi tie ordo.

889
00:32:22,390 --> 00:32:25,260
Kaj kiel flanken, sur la placoj, estas
nur iuj librotenado tie

890
00:32:25,260 --> 00:32:28,010
helpi vin kalkulu kiom da komparoj,
aŭ kiom da svopoj havas

891
00:32:28,010 --> 00:32:28,950
fakte estis farita.

892
00:32:28,950 --> 00:32:30,750
>> Nu, ni provu unu el
la aliaj ni vidis.

893
00:32:30,750 --> 00:32:37,116
Lasu min alklaku bobelo speco ĉi tie, kaj
lasu min elekti, kaj ĉi tiu tuta retpaĝo

894
00:32:37,116 --> 00:32:38,936
estas iom kalesxo.

895
00:32:38,936 --> 00:32:41,155
Ni akceptas la riskon
kaj ruli ĝin denove.

896
00:32:41,155 --> 00:32:44,560

897
00:32:44,560 --> 00:32:45,030
Tie ni iru.

898
00:32:45,030 --> 00:32:47,180
Do ni faru selektado varo.

899
00:32:47,180 --> 00:32:49,140
Mi ne scias kial la menuo
aperas tie.

900
00:32:49,140 --> 00:32:54,070
Ni zomi ripari ke
cimon, ŝanĝi ĉi tion al 50.

901
00:32:54,070 --> 00:32:56,020
Ha, ni vere faras
ke multe pli rapida.

902
00:32:56,020 --> 00:32:59,160
Kvin milisekundoj aŭ tiel, kaj Starto.

903
00:32:59,160 --> 00:33:00,470
>> Do tiu estas elekto varo.

904
00:33:00,470 --> 00:33:03,070
Do denove, pensi kion ni
faris kun la homoj tie supre.

905
00:33:03,070 --> 00:33:08,490
Ni trapasis la tabelo kaj selektita
la plej malgranda ero denove,

906
00:33:08,490 --> 00:33:09,250
kaj denove, kaj denove.

907
00:33:09,250 --> 00:33:11,110
Nun mi asertas, ke estis ankoraŭ sufiĉe malbone.

908
00:33:11,110 --> 00:33:15,010
Estis ankoraŭ n kvadrataj, donos nek prenos,
sed ĝi estis, en la reala mondo, iom

909
00:33:15,010 --> 00:33:18,280
pli rapida, ĉar mi ja prenante
iomete malpli paŝojn ĉiufoje.

910
00:33:18,280 --> 00:33:19,800
Sed ni nur parolas kio?

911
00:33:19,800 --> 00:33:21,830
Eble 40 aŭ tiel trinkejoj tie?

912
00:33:21,830 --> 00:33:23,200
Ni ne parolas 40 milionoj.

913
00:33:23,200 --> 00:33:27,430
Do ĝi ne estas tute klara al mi ke
estis ja signifa gajno.

914
00:33:27,430 --> 00:33:32,530
>> Permesu al mi iri tien kaj ŝanĝi nian
tria algoritmo, kiu estis elekti

915
00:33:32,530 --> 00:33:33,180
inserción varo.

916
00:33:33,180 --> 00:33:36,380
Kaj nun estas vere kalesxon ĉar la
menuo vere ne devus esti tie.

917
00:33:36,380 --> 00:33:40,840
Do nun ni rulumi reen tien
kaj komenci tiun algoritmon.

918
00:33:40,840 --> 00:33:43,270
Whoop, komenci kaj ĉesi.

919
00:33:43,270 --> 00:33:47,160
Do ĉi tiu speco de havas belan desegnon
al ĝi, per kiu ni estas denove

920
00:33:47,160 --> 00:33:50,240
enmeto de la homoj, aŭ en
tiu kazo, la riglilojn en

921
00:33:50,240 --> 00:33:52,620
ilia taŭga loko.

922
00:33:52,620 --> 00:33:55,430
Kaj ĝi estas jam faris antaŭe
Mi turniĝis.

923
00:33:55,430 --> 00:33:58,940
Sed ĉi tiu ankaŭ, en teorio,
ankoraŭ n kvadratoj.

924
00:33:58,940 --> 00:34:01,430
>> Do ni vidu se ni ne povas resumi
tiujn kiel sekvas.

925
00:34:01,430 --> 00:34:04,750
Mi tuj iros antaŭen kaj justa por doni
ni speco de komuna maniero paroli

926
00:34:04,750 --> 00:34:08,489
pri tiuj aferoj, lasu min enkonduki
nur iom de skribmaniero tie.

927
00:34:08,489 --> 00:34:12,480
Vi estas por vidi iun nomita granda
Ho, ĉar ĝi estas laŭvorte granda

928
00:34:12,480 --> 00:34:16,320
O. Kaj tio estas maniero, ke komputilo
sciencisto aŭ matematikisto eĉ uzas

929
00:34:16,320 --> 00:34:19,230
por priskribi la rula tempo
de iu algoritmo.

930
00:34:19,230 --> 00:34:21,400
Kiom da paŝoj reale preni?

931
00:34:21,400 --> 00:34:25,080
>> Nun mi iros al hontigi min per
mia skribo tie en nur momento.

932
00:34:25,080 --> 00:34:29,020
Sed lasu min antaŭeniri kaj diri ke
tio estos granda a super tie.

933
00:34:29,020 --> 00:34:33,610
Kaj lasu min enkonduki unu alia
simbolo, majuskla omega.

934
00:34:33,610 --> 00:34:37,080
Omega tuj estos la malon,
esence, de granda O. Dum granda O

935
00:34:37,080 --> 00:34:40,790
rimedoj, en la plej malbona kazo, kiom da tempo
eble iu algoritmo prenas, en

936
00:34:40,790 --> 00:34:43,480
terminoj de n, omega tuj
estu kiom da tempo povus ĝin

937
00:34:43,480 --> 00:34:45,409
preni en la plej bona kazo.

938
00:34:45,409 --> 00:34:48,090
Kaj ni vidos kion ni celas diri per
bona kazo en nur momento.

939
00:34:48,090 --> 00:34:49,940
>> Do ni komencu ion simpla.

940
00:34:49,940 --> 00:34:54,719
Permesu min komenci per lineara serĉo.

941
00:34:54,719 --> 00:34:55,679
Do ne imitu.

942
00:34:55,679 --> 00:34:58,000
Ni nomas tiun lineara serĉo.

943
00:34:58,000 --> 00:35:01,140
Kaj nun, fari iom
tablo el ĉi.

944
00:35:01,140 --> 00:35:06,600
Kaj nun, en la kazo de linearaj serĉo,
en la plej malbona kazo, kiom da paŝoj estas

945
00:35:06,600 --> 00:35:11,770
ĝi tuj portos min trovi
numeron de arbitra elekto?

946
00:35:11,770 --> 00:35:14,540
Kaj tie estas n tuta pordoj
aŭ n tuta nombroj.

947
00:35:14,540 --> 00:35:15,940
Plej malbona kazo.

948
00:35:15,940 --> 00:35:18,800
Kiom da paŝoj mi tuj devos
preni por trovi la numero 50 en tabelo

949
00:35:18,800 --> 00:35:20,830
de n pordoj?

950
00:35:20,830 --> 00:35:21,410
Kaj kial?

951
00:35:21,410 --> 00:35:23,680
Ĉar ĝi povus esti la tuta
vojo super sur la fino.

952
00:35:23,680 --> 00:35:27,120
Tiel kiel Jennifer renkontis, la
numero 50 estis la tuta vojo finiĝis, tiel en

953
00:35:27,120 --> 00:35:30,760
la plej malbona kazo lineara serĉo
estas granda O de n, ni diras.

954
00:35:30,760 --> 00:35:33,430
>> Kio pri la plej bona kazo,
se vi ricevas vere bonŝanca?

955
00:35:33,430 --> 00:35:36,200
Ĝi simple tuj prenos unu paŝon,
aŭ konstanta nombro da paŝoj.

956
00:35:36,200 --> 00:35:37,830
Do ni devos priskribi ke kiel 1.

957
00:35:37,830 --> 00:35:39,010
Do ĉi tiu estas sufiĉe bonaj.

958
00:35:39,010 --> 00:35:41,210
Nun kio se ni faris ion
kiel duuma serĉo?

959
00:35:41,210 --> 00:35:43,860

960
00:35:43,860 --> 00:35:47,846
Do duuma serĉo, en la plej malbona
kazo, prenis kiom da tempo?

961
00:35:47,846 --> 00:35:49,250
>> [Intermetante voĉoj]

962
00:35:49,250 --> 00:35:51,310
>> DAVID J. Malan: Do fakte, mi
aŭdis ĝin en paro lokoj.

963
00:35:51,310 --> 00:35:56,390
Do ĝi estas reale log n, doni aŭ forpreni de
ĉar kiel ni dividos la listo en duono

964
00:35:56,390 --> 00:36:00,730
denove, kaj denove, kaj denove, ni povis
trovi, finfine, la valoro,

965
00:36:00,730 --> 00:36:04,750
se ĝi estas tie, sed ekzistas kaptaĵo.

966
00:36:04,750 --> 00:36:08,590
Kio estas la supozo, ke ni devas
preni por donita por duuma serĉo?

967
00:36:08,590 --> 00:36:09,700
Ĝi devas esti ordo.

968
00:36:09,700 --> 00:36:12,770
Tio ne ordo, vi povas fendi la afero
en duono denove kaj denove, kaj vi

969
00:36:12,770 --> 00:36:15,490
povas iri forlasis, kaj vi povas iri dekstren, kaj
vi povas iri maldekstren kaj dekstren, sed vi estas

970
00:36:15,490 --> 00:36:18,070
ne tuj trovos la elemento se
la listo estas ne ordigita, ĉar

971
00:36:18,070 --> 00:36:18,790
vi povus perdi ĝin.

972
00:36:18,790 --> 00:36:22,120
Ĉar via heŭristiko, por iri maldekstren
aŭ dekstra tuj estos misa se estas

973
00:36:22,120 --> 00:36:23,420
ja ne ordo.

974
00:36:23,420 --> 00:36:26,110
Do tie estas ia kaŝita kosto
uzi iun kiel ĉi tio.

975
00:36:26,110 --> 00:36:29,250
>> Nun, ni eniru nian ordigado
algoritmoj ne serĉado -

976
00:36:29,250 --> 00:36:31,140
oh, fakte ni iru en ĉi tiu celo.

977
00:36:31,140 --> 00:36:33,190
Duuma serĉo en la plej bona kazo?

978
00:36:33,190 --> 00:36:36,290
Ĝi estas ankaŭ 1 se ĝi nur hazarde estas
en la mezo de la tabelo, aŭ

979
00:36:36,290 --> 00:36:37,810
Meze de la telefono libro.

980
00:36:37,810 --> 00:36:39,710
Nun ni faru bobelo varo.

981
00:36:39,710 --> 00:36:42,570
Do denove, nun ni eniri la
varojn, ne la serĉojn.

982
00:36:42,570 --> 00:36:47,220
>> En la plej malbona kazo, kiom da paŝoj faris nin
aserto bobelo speco tuj preni?

983
00:36:47,220 --> 00:36:48,410
n akordis.

984
00:36:48,410 --> 00:36:49,200
Do mi tuj, por cxerpi tio.

985
00:36:49,200 --> 00:36:51,710
Ooh, mia skribo aspektas eĉ pli malbona
kiam ĝi projektis ke granda.

986
00:36:51,710 --> 00:36:52,510
Ĉio bone.

987
00:36:52,510 --> 00:36:53,570
Por ke estas n kvadratoj.

988
00:36:53,570 --> 00:36:59,460
Kaj en la plej bona kazo de bobelo varon,
kiom da paŝoj estas ĝi tuj preni?

989
00:36:59,460 --> 00:37:00,980
1, Mi aŭdis.

990
00:37:00,980 --> 00:37:01,760
>> Parolanto 1: n.

991
00:37:01,760 --> 00:37:03,286
>> DAVID J. Malan: n, mi aŭdis.

992
00:37:03,286 --> 00:37:04,200
>> Parolanto 1: 2.

993
00:37:04,200 --> 00:37:05,010
>> DAVID J. Malan: 2, mi aŭdis.

994
00:37:05,010 --> 00:37:06,670
Ĉu mi aŭdas 3?

995
00:37:06,670 --> 00:37:07,080
Ĉio bone.

996
00:37:07,080 --> 00:37:11,390
Do mi aŭdis 1, n, 2, sed ni pick
aparte almenaŭ la unua de tiuj

997
00:37:11,390 --> 00:37:12,330
sugestojn, 1.

998
00:37:12,330 --> 00:37:15,370
Ĝi ne estas malbona instinkto, ĉar ĝi
ia sekvas mastro ĉi tie.

999
00:37:15,370 --> 00:37:19,670
Sed se ĝi nur prenas 1 paŝo, kiel en la
mondo mi povus aserti, ke la listo

1000
00:37:19,670 --> 00:37:22,900
estas ordo, ĉar se mi nur permesis
preni 1 paŝo, kiom da elementoj

1001
00:37:22,900 --> 00:37:25,230
mi povus efektive kontroli por certiĝi?

1002
00:37:25,230 --> 00:37:28,270
Nu, nur 1, kiu signifas ke estas n
minus 1 elementoj kiuj povus esti el

1003
00:37:28,270 --> 00:37:31,310
ordo, kaj mi simple okazas fido post
rigardas 1 elemento kiu la

1004
00:37:31,310 --> 00:37:31,850
afero ordo.

1005
00:37:31,850 --> 00:37:33,930
Do 1 Ne korekti ĉi tie.

1006
00:37:33,930 --> 00:37:35,710
Do minimume, kiom da
Mi devas rigardi?

1007
00:37:35,710 --> 00:37:36,680
>> [Intermetante voĉoj]

1008
00:37:36,680 --> 00:37:40,160
>> DAVID J. Malan: n minus 1, aŭ vere,
n, ĉar mi bezonas rigardi ĉiun

1009
00:37:40,160 --> 00:37:42,190
elemento por certigi ke
ĝi ne estas el ordo.

1010
00:37:42,190 --> 00:37:44,750
Sed denove, ni ordigi de ondo nia
manoj al la pli malgrandaj nombroj kaj

1011
00:37:44,750 --> 00:37:47,100
supozi ke, kiel n prenas grandaj, ili estas
neinteresa ĉiuokaze.

1012
00:37:47,100 --> 00:37:48,380
Do jen bobelo varo.

1013
00:37:48,380 --> 00:37:49,830
Kaj nun, ni faras cxi du lastaj.

1014
00:37:49,830 --> 00:37:53,520
Selektado varo, kaj tiam ni instruos vin
fari inserción varo.

1015
00:37:53,520 --> 00:37:57,160
Kaj tiam ni blovu via
mensoj per io multe

1016
00:37:57,160 --> 00:37:58,926
pli bona ol ĉiuj tiuj.

1017
00:37:58,926 --> 00:38:00,410
Ĉio bone.

1018
00:38:00,410 --> 00:38:04,700
>> Kio estas la plej malbona kazo kurante
tempo de selektado speco?

1019
00:38:04,700 --> 00:38:05,680
>> Parolanto 4: n kvadratoj.

1020
00:38:05,680 --> 00:38:06,710
>> DAVID J. Malan: n kvadrata, mi aŭdi.

1021
00:38:06,710 --> 00:38:09,790
Sed kial n akordis, intuicie?

1022
00:38:09,790 --> 00:38:11,170
>> Parolanto 4: Ĉar ni ĵus faris.

1023
00:38:11,170 --> 00:38:12,260
>> DAVID J. Malan: Ĉar ni ĵus faris.

1024
00:38:12,260 --> 00:38:12,550
Akcepti.

1025
00:38:12,550 --> 00:38:13,380
Bona respondo.

1026
00:38:13,380 --> 00:38:16,660
Sed intuicie, kial estas elekto
speco n kvadratoj?

1027
00:38:16,660 --> 00:38:18,980
Kion ni devas fari
denove kaj denove?

1028
00:38:18,980 --> 00:38:22,570
Ni devis konservi balaita tra, estas
vi la plej malgranda, vi estas la

1029
00:38:22,570 --> 00:38:24,020
plej malgranda, vi estas la plej malgranda.

1030
00:38:24,020 --> 00:38:27,480
Kaj koncedis, ni povis preni n
paŝoj, tiam n minus 1, tiam n minus 2.

1031
00:38:27,480 --> 00:38:30,700
Sed se vi speco de aldonu tiuj tuton,
aŭ preni ĝin sur fido kiun mi aldonis

1032
00:38:30,700 --> 00:38:34,810
ilin anticipe, ni preni malglate n
kvadrato minus iuj pli malgrandaj nombroj.

1033
00:38:34,810 --> 00:38:36,730
Do mi tuj nomas tiun n kvadratoj.

1034
00:38:36,730 --> 00:38:39,530
Sed kun selektado varo en la plej bona
kazo, kiom da paŝoj estas

1035
00:38:39,530 --> 00:38:40,632
tuj kapti min?

1036
00:38:40,632 --> 00:38:41,840
>> Parolanto 5: [inaudibles]

1037
00:38:41,840 --> 00:38:44,350
>> DAVID J. Malan: Estas bedaŭrinde
ankoraŭ n kvadratoj, ĉu ne?

1038
00:38:44,350 --> 00:38:49,590
Ĉar se mi elektante la plej malgranda
elemento, kaj ni havis sep personoj ĉi tie,

1039
00:38:49,590 --> 00:38:53,280
Mi nur scias, iam mi alvenas al la tre
fino, ke mi trovis la plej malgranda

1040
00:38:53,280 --> 00:38:55,670
nombro, kien ajn li aŭ
ŝi eble estis.

1041
00:38:55,670 --> 00:38:58,820
Sed kiel mi trovos la sekvanta
plej malgranda nombro?

1042
00:38:58,820 --> 00:39:00,160
Mi devas fari alian pasas.

1043
00:39:00,160 --> 00:39:04,810
Do, en la plej bona kazo, kio estas la
eniro al selektado speco?

1044
00:39:04,810 --> 00:39:07,830
Ĝi estas jam speco listo, numero unu,
numero du, numero tri, la numero kvar.

1045
00:39:07,830 --> 00:39:08,600
Sed mi estas komputilo.

1046
00:39:08,600 --> 00:39:10,190
Mi povas nur rigardi unu
afero je tempo.

1047
00:39:10,190 --> 00:39:12,465
Mi ne povas ordigi de paŝon
reen kiel homo, kaj diru:

1048
00:39:12,465 --> 00:39:14,030
ooh, ĉi aspektas korekta.

1049
00:39:14,030 --> 00:39:17,580
>> Mi povas nur ajudiki korekteco en
selektado varo por selekti la

1050
00:39:17,580 --> 00:39:18,370
plej malgranda nombro.

1051
00:39:18,370 --> 00:39:21,390
Sed eĉ se mi trovos numeron oni unue,
se mi ne konas ion alian pri

1052
00:39:21,390 --> 00:39:24,460
la aliaj nombroj, kiujn mi faras ne, ĉio mi
scias, ke mi estis transdonita tabelo

1053
00:39:24,460 --> 00:39:27,930
aŭ aro de pordoj malantaŭ kiuj estas
nombroj, la sola maniero mi scias, ke unu

1054
00:39:27,930 --> 00:39:28,680
estis la plej malgranda?

1055
00:39:28,680 --> 00:39:32,440
Se mi ricevas la tutan vojon tie kaj realigi,
malbenita, oni ja estis la plej malgranda.

1056
00:39:32,440 --> 00:39:34,870
>> Sed kiel mi povas tiam difini, ke
du estas la sekva pli malgranda?

1057
00:39:34,870 --> 00:39:38,350
Por fari la saman senefikeco
denove kaj denove.

1058
00:39:38,350 --> 00:39:42,210
Do fine, kun inserción varon,
kiel, en la plej malbona kazo,

1059
00:39:42,210 --> 00:39:44,990
ni diru ĝin plenumas?

1060
00:39:44,990 --> 00:39:49,100
Ĝi tro estas n kvadratoj.

1061
00:39:49,100 --> 00:39:53,020
Kaj kiel pri la plej bona kazo?

1062
00:39:53,020 --> 00:39:56,282
Ni lasos ke kiel cliffhanger.

1063
00:39:56,282 --> 00:40:00,090
Ni plenigu en tiu celo venontfoje,
sed unue permesu al mi proponas ke ni

1064
00:40:00,090 --> 00:40:02,620
fundamente fari pli bone ol
ĉiuj de ĉi tiuj, ĉiuj rajtas?

1065
00:40:02,620 --> 00:40:05,220
>> Do pensu mem kion inserción
speco tuj estos.

1066
00:40:05,220 --> 00:40:06,910
Nu, tio ne estis tre drama,
ĉar mi estas la sola

1067
00:40:06,910 --> 00:40:08,970
kiu vidis la ŝanĝon.

1068
00:40:08,970 --> 00:40:09,620
Wow.

1069
00:40:09,620 --> 00:40:10,420
Akcepti.

1070
00:40:10,420 --> 00:40:12,615
Do jen ni havas iom
malsama pruvo.

1071
00:40:12,615 --> 00:40:16,580
Se mi zomi tien, vi vidos, ke sur
la maldekstra havas bobelo varon, en la

1072
00:40:16,580 --> 00:40:20,740
mezo ni havas elekton varo, kaj sur
la ekstremdekstro, ni havas ion ni

1073
00:40:20,740 --> 00:40:23,380
ne rigardis ankoraŭ
vokis kunfandi varo.

1074
00:40:23,380 --> 00:40:26,080
Sed rigardu, kion ni estis
faras ĉi tie tiel multe hodiaŭ.

1075
00:40:26,080 --> 00:40:29,200
Kiam Jennifer unua supreniris sur la scenejo,
Ni trapasis la tabelo de nombroj

1076
00:40:29,200 --> 00:40:33,750
denove, kaj denove, kun lineara serĉo,
kaj ni akiris lineara rultempo, granda O

1077
00:40:33,750 --> 00:40:35,100
de n, por tiel diri.

1078
00:40:35,100 --> 00:40:41,000
>> Kiam ni nun konsideras la unua semajno de
klaso, kiam ni dividu kaj venkos,

1079
00:40:41,000 --> 00:40:43,740
kaj ni estis la telefonon libro ŝiri,
kaj Jennifer, kaj ni kolektive

1080
00:40:43,740 --> 00:40:47,500
leveraged tiu ŝlosilo komprenon, kiu estis
ripeti mem denove kaj denove por

1081
00:40:47,500 --> 00:40:50,930
iel ĵeti for, ĵetante for,
ĵeti for, duono de la problemo, aŭ

1082
00:40:50,930 --> 00:40:55,320
ĝenerale, dividanta problemo en duono,
kaj poste trakti la plej malgranda peco de

1083
00:40:55,320 --> 00:40:59,630
la problemo kiel koncepte ekvivalenta
al la aliaj, ni iel faris

1084
00:40:59,630 --> 00:41:00,910
fundamente bona.

1085
00:41:00,910 --> 00:41:04,720
Sed kun bobelo varo, kun elekto
varo, kun inserción varon, ni povas

1086
00:41:04,720 --> 00:41:06,560
ne tia komprenojn kiu Jennifer faris.

1087
00:41:06,560 --> 00:41:10,220
Ni preskaux nur marsxis tien kaj
devenos tutan faskon da fojoj, kaj ni

1088
00:41:10,220 --> 00:41:12,650
tweaked aferojn iomete, interŝanĝante
en ĉi tiu ordo, eble

1089
00:41:12,650 --> 00:41:13,730
enmeto aŭ selektante.

1090
00:41:13,730 --> 00:41:16,950
Sed je la fino de la tago, mi faris multajn
de talpoj marŝi tien kaj reen.

1091
00:41:16,950 --> 00:41:21,160
Ni faris ne vere influo ion
inteligenta kiel Jennifer faris kiel dividanta

1092
00:41:21,160 --> 00:41:22,040
kaj konkerante.

1093
00:41:22,040 --> 00:41:25,620
>> Do kunfandi varon, per kontrasto, kiun ni
ne vidos ĝis la proksima semajno, ĝi okazas

1094
00:41:25,620 --> 00:41:29,540
de utiligi tiu ŝlosilo ideo per dividanta
la enigo, kaj poste _halving_, kaj poste

1095
00:41:29,540 --> 00:41:30,580
_halving_, kaj poste _halving_.

1096
00:41:30,580 --> 00:41:34,590
Kaj en ĉiu ripeto de tiu ciklo,
ordigi la maldekstra duono, kaj la dekstran

1097
00:41:34,590 --> 00:41:38,200
duono, poste la maldekstran duonon de la maldekstra duono,
kaj la dekstra duono de la maldekstra, tiam

1098
00:41:38,200 --> 00:41:40,990
la maldekstra duono de la dekstra duono, kaj
la dekstra duono de la dekstra duono.

1099
00:41:40,990 --> 00:41:42,840
Kaj ripetante denove kaj denove.

1100
00:41:42,840 --> 00:41:46,170
>> Tiel vi vidos ĉi vide, sed ĉi tiu
estas kio atendas nin la proksima semajno.

1101
00:41:46,170 --> 00:41:49,760
Kaj ĝenerale, kiam ni pensas iom
iom pli en tia problemo.

1102
00:41:49,760 --> 00:41:52,435

1103
00:41:52,435 --> 00:41:57,970
Ni n kvadrato maldekstre, n
kvadrato en la mezo, kaj n

1104
00:41:57,970 --> 00:41:59,400
log n dekstre.

1105
00:41:59,400 --> 00:42:00,590
Do tie estas via reala cliffhanger.

1106
00:42:00,590 --> 00:42:02,040
Ni vidos vin lunde.

1107
00:42:02,040 --> 00:42:05,163
>> [Aplaŭdo]