1
00:00:00,000 --> 00:00:00,990

2
00:00:00,990 --> 00:00:02,970
>> [MUSIC nagpe-play]

3
00:00:02,970 --> 00:00:10,400

4
00:00:10,400 --> 00:00:12,550
>> David J. MALAN: Ito ang CS50.

5
00:00:12,550 --> 00:00:14,612
At ito ay ang simula ng linggo tatlo.

6
00:00:14,612 --> 00:00:16,820
Kaya namin nakuha ng isang pulutong ng mga kapana-panabik na
mga bagay-bagay upang masakop ang araw na ito.

7
00:00:16,820 --> 00:00:20,160
Ang isang pulutong ng mga pagkakataon para sa
boluntaryo up sa entablado.

8
00:00:20,160 --> 00:00:22,780
At sa huli, ngayon ay
hindi tungkol sa code sa lahat.

9
00:00:22,780 --> 00:00:24,820
Ngunit ito ay tungkol sa mga ideya, at
ito ay tungkol sa mga algorithm,

10
00:00:24,820 --> 00:00:28,420
at ang tunay na nagdadala sa likod ng ilan sa
ang mga araling natutunan mula sa linggo zero,

11
00:00:28,420 --> 00:00:31,910
kung saan ang pagpapabalik, namin
ipinakilala ang isang napakapangit na bagay.

12
00:00:31,910 --> 00:00:33,880
At paghiram ng inspirasyon
mula sa na, upang simulan

13
00:00:33,880 --> 00:00:36,879
upang malutas kailanman mas sopistikadong
problema algorithmically.

14
00:00:36,879 --> 00:00:38,420
Ngunit una, isang pares ng mga anunsyo.

15
00:00:38,420 --> 00:00:42,020
Kaya isa, kung nais mong sumali
Kawani at mga kaklase CS50 sa tanghalian

16
00:00:42,020 --> 00:00:44,670
ito Biyernes, parehong dito at sa
Cambridge, at sa New Haven,

17
00:00:44,670 --> 00:00:48,060
mangyaring bisitahin ang kurso na iyon
website, kung saan ay matatagpuan sa isang URL.

18
00:00:48,060 --> 00:00:50,390
Magbigay ng panayam na ito Miyerkules
Hindi na dito sa Sanders.

19
00:00:50,390 --> 00:00:53,610
Ito lamang ay online, upang
tune in sa website CS50,

20
00:00:53,610 --> 00:00:55,850
kung dito sa Cambridge
o New Haven rin.

21
00:00:55,850 --> 00:00:58,110
>> At pagkatapos ay itakda ang problema ng dalawang
Nasa iyong mga kamay.

22
00:00:58,110 --> 00:01:03,067
Kung hindi mo pa dived sa pa, payagan ako
na nag-aalok ng malakas na worded suggestion

23
00:01:03,067 --> 00:01:05,150
na, lalo na ngayon, tulad ng
Nagtatakda ang problema advance,

24
00:01:05,150 --> 00:01:08,669
na tunay na nais na magsimula ngayon, kung hindi
magkawkaw ng kaunti sa katapusan ng linggo o bago

25
00:01:08,669 --> 00:01:10,710
kapag pumunta sila out muna sa
Biyernes, dahil bibigyan ka

26
00:01:10,710 --> 00:01:14,380
makita na ang mga ito ay hindi kinakailangan
nakakakuha ng mas matagal o mas mahirap na per

27
00:01:14,380 --> 00:01:14,950
se.

28
00:01:14,950 --> 00:01:17,575
Tingin ko makikita ninyo na, sa
pangkalahatan, sila ay madalas na tumagal ng humigit-kumulang

29
00:01:17,575 --> 00:01:18,892
sa paligid ng parehong halaga ng oras.

30
00:01:18,892 --> 00:01:20,850
Ngunit ito ay tiyak depende
sa mag-aaral, at ito

31
00:01:20,850 --> 00:01:22,880
depende sa mindset
na kung saan ang diskarte mo ito.

32
00:01:22,880 --> 00:01:24,910
Ngunit walang paltos, ikaw ay pagpunta
na tumakbo up laban sa ilang mga pader,

33
00:01:24,910 --> 00:01:26,350
at ikaw ay pagpunta sa hit
ilang bug, at ikaw lamang

34
00:01:26,350 --> 00:01:27,950
hindi pagpunta sa ma-
makakuha ng higit ito sa ilang mga punto.

35
00:01:27,950 --> 00:01:31,380
At ito ay hugely mahalaga para ma
sa hakbang ang layo, bumalik sa susunod na araw,

36
00:01:31,380 --> 00:01:35,286
pumunta sa mga oras ng opisina, post sa CS50 Talakayin
o ang gusto, sa aktwal na makakuha unblock.

37
00:01:35,286 --> 00:01:36,160
Kaya panatilihin na sa isip.

38
00:01:36,160 --> 00:01:40,830
Simula sa pinakamaagang panahon
ay ang pinakamahusay na bagay na maaari mong gawin.

39
00:01:40,830 --> 00:01:44,160
Kaya dito ay kung saan namin sinimulan
klase, higit sa week zero.

40
00:01:44,160 --> 00:01:47,441
At maaari naming makakuha ng isang volunteer
dito upang makatulong sa akin mahanap ang mics?

41
00:01:47,441 --> 00:01:47,940
SIGE.

42
00:01:47,940 --> 00:01:48,900
Nakatayo up na.

43
00:01:48,900 --> 00:01:50,080
Lumapit sa up.

44
00:01:50,080 --> 00:01:53,707
Hulaan na kung paano ito ay pagpunta sa trabaho.

45
00:01:53,707 --> 00:01:54,415
Ano ang pangalan mo?

46
00:01:54,415 --> 00:01:55,570
ALAN ESTRADA: Alan Estrada.

47
00:01:55,570 --> 00:01:56,778
David J. MALAN: Alan Estrada.

48
00:01:56,778 --> 00:01:57,910
Lumapit sa up.

49
00:01:57,910 --> 00:01:58,619
Masaya akong makilala kayo.

50
00:01:58,619 --> 00:01:59,910
ALAN ESTRADA: Masaya akong makilala kayo.

51
00:01:59,910 --> 00:02:02,772
David J. MALAN: At ikaw ay dito
sa amin sa linggo zero, siyempre.

52
00:02:02,772 --> 00:02:03,028
ALAN ESTRADA: ako ay.

53
00:02:03,028 --> 00:02:03,160
Ako ay.

54
00:02:03,160 --> 00:02:05,868
>> David J. MALAN: Kaya ikaw ay maaaring pumunta
magpatuloy at hanapin para sa amin Mike Smith,

55
00:02:05,868 --> 00:02:08,639
nang mas mabilis hangga't maaari mo?

56
00:02:08,639 --> 00:02:10,639
Nang mas mabilis hangga't maaari mong.

57
00:02:10,639 --> 00:02:13,756
Literal mapunit ang problema
sa kalahati ng iyong kailangan sa.

58
00:02:13,756 --> 00:02:15,130
>> ALAN ESTRADA: Um.

59
00:02:15,130 --> 00:02:17,380
David J. MALAN: Literal
mapunit ang problema sa kalahati.

60
00:02:17,380 --> 00:02:20,210

61
00:02:20,210 --> 00:02:22,083
>> ALAN ESTRADA: Oh.

62
00:02:22,083 --> 00:02:22,583
Mm.

63
00:02:22,583 --> 00:02:23,300
Napakabuti.

64
00:02:23,300 --> 00:02:23,700
>> David J. MALAN: OK.

65
00:02:23,700 --> 00:02:24,200
Good.

66
00:02:24,200 --> 00:02:24,701
Salamat.

67
00:02:24,701 --> 00:02:25,700
ALAN ESTRADA: Napakaganda.

68
00:02:25,700 --> 00:02:26,210
SIGE.

69
00:02:26,210 --> 00:02:27,610
>> David J. MALAN: At kaya ngayon,
na iyong whittled ito pababa

70
00:02:27,610 --> 00:02:29,320
sa kalahati ang laki ng problema.

71
00:02:29,320 --> 00:02:31,267
Ngayon, hindi namin down sa isang quarter.

72
00:02:31,267 --> 00:02:33,475
Ikaw ba ay nagbabayad ng pansin sa
kung aling bahagi Pinananatili namin?

73
00:02:33,475 --> 00:02:34,405
>> [Tumatawa]

74
00:02:34,405 --> 00:02:35,970
>> ALAN ESTRADA: Oo, think-- ko

75
00:02:35,970 --> 00:02:37,594
>> David J. MALAN: Ano section kami ay nasa?

76
00:02:37,594 --> 00:02:39,150
ALAN ESTRADA: Mufflers, kaya.

77
00:02:39,150 --> 00:02:39,941
>> David J. MALAN: OK.

78
00:02:39,941 --> 00:02:42,810
Ngunit Mike Smith ay pagpunta
upang maging pagkatapos Mufflers.

79
00:02:42,810 --> 00:02:44,130
So--

80
00:02:44,130 --> 00:02:48,180
>> [Tumatawa]

81
00:02:48,180 --> 00:02:48,742
>> Lahat tama.

82
00:02:48,742 --> 00:02:50,200
ALAN ESTRADA: Saan tayo naghahanap?

83
00:02:50,200 --> 00:02:52,049
David J. MALAN: Mike Smith.

84
00:02:52,049 --> 00:02:53,090
ALAN ESTRADA: Mike Smith.

85
00:02:53,090 --> 00:02:54,760
David J. MALAN: Ngayon, hindi namin sa surgical.

86
00:02:54,760 --> 00:02:57,840
Ngayon, ang mga manggagamot.

87
00:02:57,840 --> 00:02:58,340
Now--

88
00:02:58,340 --> 00:02:59,856
>> ALAN ESTRADA: pumunta sa real Let's- ipaalam.

89
00:02:59,856 --> 00:03:00,370
Real.

90
00:03:00,370 --> 00:03:00,970
>> David J. MALAN: Real.

91
00:03:00,970 --> 00:03:01,470
SIGE.

92
00:03:01,470 --> 00:03:03,700
Kung kailangan mo ng Real.

93
00:03:03,700 --> 00:03:05,250
Ngayon, kung aling paraan ay Mike Smith?

94
00:03:05,250 --> 00:03:06,250
>> ALAN ESTRADA: Sa ganitong paraan.

95
00:03:06,250 --> 00:03:07,333
>> David J. MALAN: Aling paraan?

96
00:03:07,333 --> 00:03:08,240
ALAN ESTRADA: Maghintay.

97
00:03:08,240 --> 00:03:08,790
M is-- right?

98
00:03:08,790 --> 00:03:09,110
Sinimulan na naming with--

99
00:03:09,110 --> 00:03:10,090
>> David J. MALAN: Oo.

100
00:03:10,090 --> 00:03:10,650
Sila ay iniwan.

101
00:03:10,650 --> 00:03:11,430
Ang iyong karapatan.

102
00:03:11,430 --> 00:03:11,710
>> ALAN ESTRADA: Oo.

103
00:03:11,710 --> 00:03:13,126
>> David J. MALAN: Kaya ni Mike sa dito.

104
00:03:13,126 --> 00:03:13,990
ALAN ESTRADA: Ano?

105
00:03:13,990 --> 00:03:14,665
>> [Tumatawa]

106
00:03:14,665 --> 00:03:17,365

107
00:03:17,365 --> 00:03:18,330
>> Masamang halimbawa, guys.

108
00:03:18,330 --> 00:03:18,830
Sorry.

109
00:03:18,830 --> 00:03:21,610
David J. MALAN: Ito ay magturo
mong tumalon sa labas ng iyong upuan.

110
00:03:21,610 --> 00:03:22,318
>> ALAN ESTRADA: Oh.

111
00:03:22,318 --> 00:03:22,890
Oh.

112
00:03:22,890 --> 00:03:23,390
Nakatanggap ako sa iyo.

113
00:03:23,390 --> 00:03:24,670
Nakatanggap ako sa iyo.

114
00:03:24,670 --> 00:03:25,170
Oh.

115
00:03:25,170 --> 00:03:25,669
Oh.

116
00:03:25,669 --> 00:03:26,812
Ito is-- OK, ang nakuha ko sa iyo.

117
00:03:26,812 --> 00:03:27,520
Smith karapatan dito?

118
00:03:27,520 --> 00:03:28,894
>> David J. MALAN: Smith, salamat sa iyo.

119
00:03:28,894 --> 00:03:30,535
Kaya kailangan ko panatilihin ang hinahanap up Smith?

120
00:03:30,535 --> 00:03:30,790
>> ALAN ESTRADA: Oh, oo.

121
00:03:30,790 --> 00:03:31,340
Hindi, hindi, hindi.

122
00:03:31,340 --> 00:03:31,600
Oh hindi.

123
00:03:31,600 --> 00:03:31,940
Ito ay akin.

124
00:03:31,940 --> 00:03:32,580
>> David J. MALAN: Oh, nakuha mo Smith.

125
00:03:32,580 --> 00:03:33,415
SIGE.

126
00:03:33,415 --> 00:03:34,040
>> ALAN ESTRADA: Oo, ako
Nakakuha Smith karapatan dito.

127
00:03:34,040 --> 00:03:34,700
Paumanhin, guys.

128
00:03:34,700 --> 00:03:35,860
Akala ko Michael-- namin
hinahanap Michael.

129
00:03:35,860 --> 00:03:36,550
Sorry.

130
00:03:36,550 --> 00:03:37,550
>> David J. MALAN: Ito ay OK.

131
00:03:37,550 --> 00:03:39,950
Lahat ng karapatan, ngayon kami ay
sa Paccini at anak.

132
00:03:39,950 --> 00:03:41,242
>> ALAN ESTRADA: Paccini at mga anak.

133
00:03:41,242 --> 00:03:43,158
David J. MALAN: Tanging
at ako ay sa sa mga ito.

134
00:03:43,158 --> 00:03:44,050
SIGE.

135
00:03:44,050 --> 00:03:45,130
Hanapin sa amin Mike Smith.

136
00:03:45,130 --> 00:03:45,830
Smith.

137
00:03:45,830 --> 00:03:46,310
>> ALAN ESTRADA: Smith.

138
00:03:46,310 --> 00:03:46,750
>> David J. MALAN: Smith.

139
00:03:46,750 --> 00:03:47,728
Humihingi kami sa R ​​para sa basura.

140
00:03:47,728 --> 00:03:48,644
ALAN ESTRADA: basura.

141
00:03:48,644 --> 00:03:50,096
Oh.

142
00:03:50,096 --> 00:03:52,480
Ito ay pagpunta sa tumagal ng isang habang.

143
00:03:52,480 --> 00:03:54,340
>> [Tumatawa]

144
00:03:54,340 --> 00:03:55,804

145
00:03:55,804 --> 00:03:56,720
David J. MALAN: Shoes.

146
00:03:56,720 --> 00:03:58,080
Humihingi kami sa shoes.

147
00:03:58,080 --> 00:04:00,210
>> ALAN ESTRADA: Ngayon kami ay gonna--

148
00:04:00,210 --> 00:04:01,105
>> David J. MALAN: Nice.

149
00:04:01,105 --> 00:04:01,980
ALAN ESTRADA: Which--

150
00:04:01,980 --> 00:04:03,620
[Tumatawa]

151
00:04:03,620 --> 00:04:05,440
Oh, ito ay mahusay.

152
00:04:05,440 --> 00:04:06,910
[Tumatawa]

153
00:04:06,910 --> 00:04:08,380

154
00:04:08,380 --> 00:04:09,390
>> David J. MALAN: Ito ay OK.

155
00:04:09,390 --> 00:04:11,365
>> ALAN ESTRADA: Oh, ito ay mabuti.

156
00:04:11,365 --> 00:04:14,425
Hindi sa tingin ko ako pagpunta sa
Mayroon PSAT buddies matapos na ito.

157
00:04:14,425 --> 00:04:15,300
David J. MALAN: Magandang.

158
00:04:15,300 --> 00:04:16,078
Sporting.

159
00:04:16,078 --> 00:04:17,036
ALAN ESTRADA: Kagamitan.

160
00:04:17,036 --> 00:04:18,668
Um, L, M, N, O, P.

161
00:04:18,668 --> 00:04:19,459
David J. MALAN: OK.

162
00:04:19,459 --> 00:04:21,600
Kaya natin mapunit na ito sa kalahati ipaalam.

163
00:04:21,600 --> 00:04:22,270
Ito ay OK.

164
00:04:22,270 --> 00:04:25,606
Ito ay nagtatapos ng hindi maganda pa rin, dahil Mike
Smith ay hindi sa mga kulay-dilaw na mga pahina.

165
00:04:25,606 --> 00:04:26,430
>> ALAN ESTRADA: Aw.

166
00:04:26,430 --> 00:04:27,140
>> David J. MALAN: Hindi, ito ay OK.

167
00:04:27,140 --> 00:04:28,930
Ngunit sabihin magpanggap tulad ng ipaalam
siya ay sa pahinang ito.

168
00:04:28,930 --> 00:04:33,260
Kaya ngayon, mo na whittled ang problema down
sa isang pahina, at natagpuan namin ang Mike Smith.

169
00:04:33,260 --> 00:04:35,180
>> [Pagpalakpak]

170
00:04:35,180 --> 00:04:35,757

171
00:04:35,757 --> 00:04:36,340
Sige salamat.

172
00:04:36,340 --> 00:04:40,700

173
00:04:40,700 --> 00:04:41,200
SIGE.

174
00:04:41,200 --> 00:04:43,646
Iyon ay kahanga-hanga.

175
00:04:43,646 --> 00:04:45,954
Ngunit ito ay pa rin mas mabilis
kaysa sa linear paghahanap,

176
00:04:45,954 --> 00:04:47,870
kung saan namin magsimula sa
simula ng libro,

177
00:04:47,870 --> 00:04:51,210
at lumipat kami sa aming mga paraan mula kaliwa hanggang kanan,
kalaunan ay naghahanap para sa Mike Smith.

178
00:04:51,210 --> 00:04:53,540
At kaya, kung ang telepono ng libro
Nagkaroon siguro 1,000 mga pahina,

179
00:04:53,540 --> 00:04:56,300
marahil ito ay kinuha
sa amin ng 10 o kaya mga luha page.

180
00:04:56,300 --> 00:04:59,380
>> Ngunit kayo ay maaaring may leveraged
hinawakan ng isang palagay

181
00:04:59,380 --> 00:05:03,602
sa panahon ng lahat ng iyon, na ang ibig sabihin
na ang telepono ng libro nang maaga ay kung ano?

182
00:05:03,602 --> 00:05:04,310
Madla: Pinagbukud-bukod.

183
00:05:04,310 --> 00:05:05,000
David J. MALAN: Ito ay pinagsunod-sunod.

184
00:05:05,000 --> 00:05:05,160
Right?

185
00:05:05,160 --> 00:05:07,909
Ito ay inayos ayon sa alpabeto, kaya
na ang lahat ng mga pangalan at mga numero

186
00:05:07,909 --> 00:05:11,230
ay pinagsunod-sunod mula sa A sa
Z, at ayon sa alpabeto sa pagitan.

187
00:05:11,230 --> 00:05:13,100
Ngunit ngayon, kami ay magtatanong ngayon
ang tanong, well,

188
00:05:13,100 --> 00:05:16,170
paano ginawa Verizon o ang telepono
kumpanya makakuha ng ito sa na estado?

189
00:05:16,170 --> 00:05:19,560
>> Dahil ito ay isang bagay na pagkilos
na palagay, at sa gayon,

190
00:05:19,560 --> 00:05:22,570
malutas ang isang problema sa isang
algorithm nang mas mahusay.

191
00:05:22,570 --> 00:05:24,900
Ngunit hindi talaga namin
tinanong sa linggo zero, well,

192
00:05:24,900 --> 00:05:27,790
kung magkano ay ito gastos
Verizon o ng ibang tao

193
00:05:27,790 --> 00:05:29,620
upang makakuha ng na libro ng telepono sa inayos order?

194
00:05:29,620 --> 00:05:29,780
>> Right?

195
00:05:29,780 --> 00:05:31,529
Hindi mahalaga kung
naghahanap up Mike Smith

196
00:05:31,529 --> 00:05:35,190
ay sobrang mabilis, kung ito ay magdadala sa iyo ng isang
taon upang pagbukud-bukurin sa una ang mga pahina.

197
00:05:35,190 --> 00:05:35,690
Right?

198
00:05:35,690 --> 00:05:38,620
Maaaring gusto mo rin salain lamang
sa pamamagitan ng isang randomized phone book,

199
00:05:38,620 --> 00:05:40,690
kung ito ay magiging sobrang
mahal upang ayusin ito.

200
00:05:40,690 --> 00:05:42,350
Kaya kung kami ay maaaring magkaroon ng isa pang volunteer.

201
00:05:42,350 --> 00:05:46,350
Magpahinga ng isang tumingin hanggang dito sa
kung paano namin might-- puntahan up-- paano

202
00:05:46,350 --> 00:05:48,100
maaari naming pumunta tungkol sa pag-uuri ng mga ito.

203
00:05:48,100 --> 00:05:51,990
>> At kung Jordan maaaring aktwal
sumali sa amin dito sa entablado.

204
00:05:51,990 --> 00:05:55,100
Lumapit sa up para sa isang sandali lamang.

205
00:05:55,100 --> 00:05:56,359
Ano ang pangalan mo?

206
00:05:56,359 --> 00:05:57,150
CAROLINE: Caroline.

207
00:05:57,150 --> 00:05:58,691
David J. MALAN: Caroline, dumating sa up.

208
00:05:58,691 --> 00:06:02,070
At kayo ay sumali
sa pamamagitan ng sa akin at sa Jordan dito.

209
00:06:02,070 --> 00:06:03,800
Caroline, salamat.

210
00:06:03,800 --> 00:06:04,300
Lahat tama.

211
00:06:04,300 --> 00:06:08,330
Kaya kung ano ang mayroon kami dito para sa
Caroline ay 26 blue libro

212
00:06:08,330 --> 00:06:10,747
na FAS gumagamit upang tumulong
tiyak na huling pagsusulit.

213
00:06:10,747 --> 00:06:13,330
Ang mga ito ay pagkuha ng mahirap upang mahanap,
ngunit ano ang ginawa namin in advance

214
00:06:13,330 --> 00:06:15,800
ay na ilalagay namin ang pangalan ng isang tao
sa harap ng bawat isa sa mga ito,

215
00:06:15,800 --> 00:06:18,133
ngunit ko itinatago namin ito sa pamamagitan ng simpleng
pagkatapos paglalagay sa labas ng buong pangalan.

216
00:06:18,133 --> 00:06:22,720
Kaya gusto naming ilagay ang tao na may pangalan
L, D, J, B, ang lahat ng paraan A sa pamamagitan ng Z,

217
00:06:22,720 --> 00:06:24,090
ngunit ang mga ito sa random order.

218
00:06:24,090 --> 00:06:26,890
At kaya kung gusto mo, pakikipag-usap sa iyong
paraan sa pamamagitan ng mga problema tulad ng sa iyo

219
00:06:26,890 --> 00:06:31,620
gawin ito, maaari mong sige, at
ayusin ang mga ito para sa amin, mula A hanggang Z.

220
00:06:31,620 --> 00:06:34,070
>> Madla: OK, kaya L ay gusto mo, sa gitna.

221
00:06:34,070 --> 00:06:35,050
C ay simula.

222
00:06:35,050 --> 00:06:42,410
B. J bago L. B, Q.

223
00:06:42,410 --> 00:06:45,140
>> David J. MALAN: Pindutin ng matagal na
Naisip para sa isang segundo.

224
00:06:45,140 --> 00:06:48,910
Dahil kung hindi man, ito ay lamang
kawili-wili sa iyo, sa akin, at Jordan.

225
00:06:48,910 --> 00:06:49,724
Mayroon kaming pumunta.

226
00:06:49,724 --> 00:06:50,640
Madla: [hindi marinig].

227
00:06:50,640 --> 00:06:57,299
R.

228
00:06:57,299 --> 00:06:58,090
David J. MALAN: OK.

229
00:06:58,090 --> 00:06:59,310
Ano ang iyong ginagawa?

230
00:06:59,310 --> 00:07:01,730
>> CAROLINE: M dumating pagkatapos ng O.

231
00:07:01,730 --> 00:07:02,564
>> David J. MALAN: OK.

232
00:07:02,564 --> 00:07:03,064
>> CAROLINE: O.

233
00:07:03,064 --> 00:07:04,120
David J. MALAN: Oh, Good.

234
00:07:04,120 --> 00:07:04,970
>> CAROLINE: E.

235
00:07:04,970 --> 00:07:06,730
>> David J. MALAN: E, F. Oo.

236
00:07:06,730 --> 00:07:07,620
>> CAROLINE: T, U, V.

237
00:07:07,620 --> 00:07:10,689
>> David J. MALAN: V, T, U, V. Kaya ito
Mukhang ikaw making-- panatilihin ang pagpunta.

238
00:07:10,689 --> 00:07:12,730
Mukhang ikaw ay gumagawa ng
isang malaking tumpok sa paglipas dito,

239
00:07:12,730 --> 00:07:13,910
at uri ng isang malaking pile doon.

240
00:07:13,910 --> 00:07:16,230
Kaya ang unang kalahati ng alpabeto,
ikalawang kalahati ng alpabeto.

241
00:07:16,230 --> 00:07:16,460
SIGE.

242
00:07:16,460 --> 00:07:16,960
Good.

243
00:07:16,960 --> 00:07:19,680
Uri ng malakas ang problema sa dalawa.

244
00:07:19,680 --> 00:07:21,771
M, N, X. Oo.

245
00:07:21,771 --> 00:07:22,270
CAROLINE: K.

246
00:07:22,270 --> 00:07:22,980
David J. MALAN: OK.

247
00:07:22,980 --> 00:07:25,070
K. So uri ng pumipili ka
mga ito ng isa-isa,

248
00:07:25,070 --> 00:07:27,620
paglagay ito sa alinman sa kaliwa o kanan,
o Z ng pagpunta sa sahig.

249
00:07:27,620 --> 00:07:28,012
SIGE.

250
00:07:28,012 --> 00:07:29,190
>> CAROLINE: Z ang nangyayari sa sahig.

251
00:07:29,190 --> 00:07:29,360
>> David J. MALAN: OK.

252
00:07:29,360 --> 00:07:30,920
Y ay pagpunta sa sahig.

253
00:07:30,920 --> 00:07:31,735
Ngayon ay maaari naming ilagay ang X.

254
00:07:31,735 --> 00:07:32,409
>> CAROLINE: G.

255
00:07:32,409 --> 00:07:33,700
David J. MALAN: G pagpunta sa kaliwa.

256
00:07:33,700 --> 00:07:36,017
S ay pagpunta kanan.

257
00:07:36,017 --> 00:07:37,642
Lahat ng mga karapatan, A ay nangyayari sa lahat ng mga paraan sa kaliwa.

258
00:07:37,642 --> 00:07:38,790
>> CAROLINE: A, B, C, D.

259
00:07:38,790 --> 00:07:39,873
>> David J. MALAN: Ngayon, mabuti.

260
00:07:39,873 --> 00:07:43,260
Mayroon kami ng A, B, C. W pagpunta doon.

261
00:07:43,260 --> 00:07:45,566
Lahat ng mga karapatan, T.

262
00:07:45,566 --> 00:07:46,611
>> CAROLINE: H, I, J.

263
00:07:46,611 --> 00:07:47,860
David J. MALAN: H, I, J. Good.

264
00:07:47,860 --> 00:07:49,160
CAROLINE: Sa gitna, ako gonna--

265
00:07:49,160 --> 00:07:50,000
David J. MALAN: OK.

266
00:07:50,000 --> 00:07:52,375
Kaya ngayon, kami ay pagpunta sa uri
ng pagsamahin ang mga iba't-ibang mga piles.

267
00:07:52,375 --> 00:08:00,730
Kaya A sa pamamagitan ng C, pagkatapos ko makita D, at
E, at F, at G, at H, at I. Nice.

268
00:08:00,730 --> 00:08:05,540
J, K. At pagkatapos, ito tumpok ay
baligtad, ngunit iyan ay OK.

269
00:08:05,540 --> 00:08:06,040
Oo naman.

270
00:08:06,040 --> 00:08:07,240
Maaari naming i-cut ilang mga sulok.

271
00:08:07,240 --> 00:08:07,950
SIGE.

272
00:08:07,950 --> 00:08:10,530
At pagkatapos ay kailangan naming W, X, Y, Z.

273
00:08:10,530 --> 00:08:11,250
>> CAROLINE: Oo.

274
00:08:11,250 --> 00:08:11,880
>> David J. MALAN: Magaling.

275
00:08:11,880 --> 00:08:14,122
Kaya isang malaking salamat sa
Caroline para sa pagbubukod-bukod ng mga ito.

276
00:08:14,122 --> 00:08:15,030
>> [Pagpalakpak]

277
00:08:15,030 --> 00:08:17,287
>> Salamat.

278
00:08:17,287 --> 00:08:18,120
Maraming salamat.

279
00:08:18,120 --> 00:08:22,910
Kaya ngayon isaalang-alang para sa isang sandali
Kung paanong ang Caroline tungkol sa paggawa na,

280
00:08:22,910 --> 00:08:26,040
at kung ano ang eksaktong namin
Nagawa to-- kung paano namin

281
00:08:26,040 --> 00:08:28,409
nagawang lutasin na
kapag problema kami ay lamang

282
00:08:28,409 --> 00:08:29,950
bibigyan ng isang buong grupo ng mga random na input.

283
00:08:29,950 --> 00:08:31,610
>> Well, mukhang walang
ay isang piraso ng isang sistema doon?

284
00:08:31,610 --> 00:08:32,110
Right.

285
00:08:32,110 --> 00:08:34,495
Kaya ang mga naunang mga titik
sa alpabeto, siya

286
00:08:34,495 --> 00:08:37,120
ay paglagay sa kaliwa, at ang
mamaya mga titik sa alpabeto,

287
00:08:37,120 --> 00:08:38,270
siya ay paglagay sa kanan.

288
00:08:38,270 --> 00:08:40,500
At sa lalong madaling siya natagpuan
ilang proximal mga titik, mga

289
00:08:40,500 --> 00:08:43,124
na pumunta sa tabi mismo ng isa't isa,
siya ay ilagay ang mga order.

290
00:08:43,124 --> 00:08:46,750
At kaya namin uri ng nagkaroon ng mga maliliit
tambak na pinagsunod-sunod na mga input sa nangyari.

291
00:08:46,750 --> 00:08:50,540
>> At kaya na lubos na tulad ng kung ano ang
karamihan ng mga tao sa amin ay gawin.

292
00:08:50,540 --> 00:08:53,530
Gusto namin ang uri ng suriing mabuti sa pamamagitan ng ito,
at gusto naming uri ng magkaroon ng isang mekanismo.

293
00:08:53,530 --> 00:08:56,930
Ngunit maaaring maging mahirap na isulat
down na ito sa isang formula per se.

294
00:08:56,930 --> 00:08:59,010
Ito nadama ng kaunti pa sa organic kaysa.

295
00:08:59,010 --> 00:09:02,560
Kaya sabihin makita kung maaari naming ngayon bound
ang mga problema sa mas kaunting input.

296
00:09:02,560 --> 00:09:05,170
>> Sa halip na 26, sabihin
gawin ang isang bagay malayo mas kaunting

297
00:09:05,170 --> 00:09:09,890
may sabihin lang, pitong, sa likod
mga pinto, kaya na magsalita.

298
00:09:09,890 --> 00:09:11,300
Mayroon lamang pitong mga numero?

299
00:09:11,300 --> 00:09:15,240
At kung ang layunin na ngayon sa
kamay ay upang mahanap ang isang halaga,

300
00:09:15,240 --> 00:09:17,850
sabihin makita kung paano mahusay
maaari naming pumunta tungkol sa paggawa nito.

301
00:09:17,850 --> 00:09:22,460
At makita kung maaari naming ngayon hayaan
magsimula na mag-aplay ng ilang mga numero,

302
00:09:22,460 --> 00:09:26,310
o ang ilang mga formula na kung saan upang ilarawan
ang kahusayan ng aming phone book

303
00:09:26,310 --> 00:09:31,060
algorithm, ang aming algorithm aklat pagsusulit, at
higit pa sa pangkalahatan, sa paghahanap ng impormasyon.

304
00:09:31,060 --> 00:09:34,770
>> Kaya para sa mga ito, hayaan mo akong magpatuloy, at
ang touch screen sa paglipas dito,

305
00:09:34,770 --> 00:09:41,100
maglagay ng isang web browser na may
eksakto ang mga pitong pintuan.

306
00:09:41,100 --> 00:09:46,670
At kung kami ay maaaring makakuha ng isa sa iba pang mga
magboluntaryo upang dumating sa paglipas dito,

307
00:09:46,670 --> 00:09:48,480
Naglagay ako ng mga parehong mga pinto sa paglipas dito.

308
00:09:48,480 --> 00:09:49,170
Quick volunteer.

309
00:09:49,170 --> 00:09:51,130
>> Ito one-- demo ay pagpunta
sa isang mas mabilis at mas mabilis na ngayon.

310
00:09:51,130 --> 00:09:51,600
Halika sa down.

311
00:09:51,600 --> 00:09:52,308
Ano ang pangalan mo?

312
00:09:52,308 --> 00:09:53,040
TREVOR: Trevor.

313
00:09:53,040 --> 00:09:53,998
>> David J. MALAN: Trevor?

314
00:09:53,998 --> 00:09:55,770
Sige, Trevor, dumating sa pababa.

315
00:09:55,770 --> 00:09:59,212
Kaya Trevor ay nagboluntaryo para
gawin ng isang katulad na problema, ngunit isang bagay na

316
00:09:59,212 --> 00:10:02,170
makitid sa saklaw, at na ang nangyayari
sa daan sa amin upang subukan upang gawing pormal ngayon

317
00:10:02,170 --> 00:10:03,970
ang proseso para sa pag-uuri ng mga numero.

318
00:10:03,970 --> 00:10:05,500
>> Kaya Trevor, Natutuwa akong makilala kayo.

319
00:10:05,500 --> 00:10:08,720
Kaya dito ay isang array, para sa
magsalita, isang listahan ng mga pitong pintuan.

320
00:10:08,720 --> 00:10:10,327
Sige at hanapin sa amin ang numero 50.

321
00:10:10,327 --> 00:10:12,410
At pagkatapos ay pagkatapos ng katotohanan,
sabihin sa amin kung paano mo natagpuan ito.

322
00:10:12,410 --> 00:10:19,124

323
00:10:19,124 --> 00:10:20,040
Dapat be-- lahat ng karapatan.

324
00:10:20,040 --> 00:10:21,945
Oo, ito ay ang isa dito?

325
00:10:21,945 --> 00:10:24,680
Naku.

326
00:10:24,680 --> 00:10:25,560
SIGE.

327
00:10:25,560 --> 00:10:26,680
Nag-click ka na ang isa.

328
00:10:26,680 --> 00:10:28,690
Good.

329
00:10:28,690 --> 00:10:29,780
>> At mabuti.

330
00:10:29,780 --> 00:10:30,970
Ngayon mo na-click ang isa.

331
00:10:30,970 --> 00:10:34,060
At ipaalam sa akin magbibigay sa iyo ng mikropono,
upang ikaw ay may mga ito sa ilang sandali lamang.

332
00:10:34,060 --> 00:10:37,000
Sige at i-click ang
sa tabi ng pinto na iyong balak.

333
00:10:37,000 --> 00:10:39,812
Oo, magaling.

334
00:10:39,812 --> 00:10:41,020
TREVOR: Maaari ko bang unclick isang pinto?

335
00:10:41,020 --> 00:10:42,620
David J. MALAN: Hindi, hindi mo maaaring unclick.

336
00:10:42,620 --> 00:10:43,119
TREVOR: OK.

337
00:10:43,119 --> 00:10:43,974
Itong isa.

338
00:10:43,974 --> 00:10:45,640
David J. MALAN: Saan mo gustong pumunta?

339
00:10:45,640 --> 00:10:46,410
Alin?

340
00:10:46,410 --> 00:10:47,230
>> TREVOR: Ang isang iyon.

341
00:10:47,230 --> 00:10:48,042
>> David J. MALAN: No.

342
00:10:48,042 --> 00:10:48,450
>> TREVOR: OK.

343
00:10:48,450 --> 00:10:48,735
Itong isa.

344
00:10:48,735 --> 00:10:49,020
>> David J. MALAN: Oo.

345
00:10:49,020 --> 00:10:49,700
Iyon ay mabuti.

346
00:10:49,700 --> 00:10:50,380
Lahat tama.

347
00:10:50,380 --> 00:10:53,900
Kaya kung ano ang iyong algorithm o
pamamaraan para sa paggawa nito, Trevor?

348
00:10:53,900 --> 00:10:56,149
>> TREVOR: ko lang nagpunta sa pamamagitan ng
pinto hanggang sa nakita ko ang isang 50.

349
00:10:56,149 --> 00:10:56,940
David J. MALAN: OK.

350
00:10:56,940 --> 00:10:58,150
Magaling algorithm.

351
00:10:58,150 --> 00:10:59,540
Kaya na multa.

352
00:10:59,540 --> 00:11:03,120
Dahil sa katunayan, kung ibunyag ko kung ano ang
sa likod ng mga ito ng dalawang iba pang mga pinto, kung ano

353
00:11:03,120 --> 00:11:06,954
kami makahanap dito ay na
lamang kami ay may random input.

354
00:11:06,954 --> 00:11:08,870
Kaya na ay tulad ng aktwal na
mabuti bilang maaari mong makuha.

355
00:11:08,870 --> 00:11:12,509
At sa katunayan, nakakuha ka ng mas mahusay kaysa
exhaustively sinusuri ang buong array,

356
00:11:12,509 --> 00:11:15,300
dahil ito ay talagang
buwisit na kung ikaw ay pindutin ang numero ng

357
00:11:15,300 --> 00:11:16,604
50 sa huling pinto.

358
00:11:16,604 --> 00:11:18,520
Ngunit paano kung namin sa halip
ay nagbigay sa iyo ng isang palagay.

359
00:11:18,520 --> 00:11:20,630
Ipagpalagay ko maisasa-ayos ang lahat ng
ang mga pinto sa paligid,

360
00:11:20,630 --> 00:11:23,500
upang ikaw ay may mga
numero inayos oras na ito,

361
00:11:23,500 --> 00:11:29,730
ngunit oras na ito ito ay aktwal na
isang different-- oras na ito,

362
00:11:29,730 --> 00:11:32,640
tunay na ito ay pinagsunod-sunod para sa iyo.

363
00:11:32,640 --> 00:11:35,380
At ngayon, ang layunin sa kamay
ay na matumbok ang bilang 50.

364
00:11:35,380 --> 00:11:36,090
>> TREVOR: OK.

365
00:11:36,090 --> 00:11:37,670
>> David J. MALAN: Ano ang
iyong algorithm magiging?

366
00:11:37,670 --> 00:11:39,628
>> TREVOR: Well, kung ito ay
inayos, ito ay alinman sa pagpunta

367
00:11:39,628 --> 00:11:42,710
upang be-- kung pinakamalaking sa pinakamalaking,
pababang, makikita ito ay ang unang isa,

368
00:11:42,710 --> 00:11:44,751
o kung ito ay ang kabaligtaran,
ito ay ang huling isa.

369
00:11:44,751 --> 00:11:48,897
Kaya makikita lamang i-tap ko ang pinto, at
pagkatapos ay i-tap lamang ang huling pinto.

370
00:11:48,897 --> 00:11:49,980
David J. MALAN: Magaling.

371
00:11:49,980 --> 00:11:50,270
Lahat tama.

372
00:11:50,270 --> 00:11:51,150
Kaya nakita namin ang bilang 50.

373
00:11:51,150 --> 00:11:52,970
Kaya sa lalong madaling alam mo
sila ay inayos, namin

374
00:11:52,970 --> 00:11:55,040
nagawang pagkilos na ito palagay.

375
00:11:55,040 --> 00:11:57,040
Kaya ang mga ito ng masyadong maraming tulad
mga halimbawa phone book.

376
00:11:57,040 --> 00:11:59,540
Sa sandaling mayroon ka, kahit na may
isang maliit na problema na tulad nito,

377
00:11:59,540 --> 00:12:02,380
pre-nakaayos ang iyong mga input, maaari naming
talagang mahanap ang halaga arguably

378
00:12:02,380 --> 00:12:03,130
mas mahusay.

379
00:12:03,130 --> 00:12:05,800
>> At hindi ko sabihin sa iyo kung ito ay
inayos sa maliit sa malaki, o malaki sa maliit,

380
00:12:05,800 --> 00:12:08,080
at sa gayon ito ay napaka-makatwirang
upang magsimula sa isang dulo o sa iba pang

381
00:12:08,080 --> 00:12:09,750
upang aktwal na makita na ang target na halaga.

382
00:12:09,750 --> 00:12:11,400
Kaya salamat pati na Trevor.

383
00:12:11,400 --> 00:12:13,260
At makikita ko propose-- mabuti tapos na.

384
00:12:13,260 --> 00:12:16,960
Kami ay may isang maliit na clip, talaga, na
ay kabilang sa aming mga paboritong sandali sa CS50,

385
00:12:16,960 --> 00:12:19,700
kung saan minsan ang mga demo
hindi lubos na pumunta ayon sa plano.

386
00:12:19,700 --> 00:12:22,050
At sa katunayan sa ngayon, ako
nakuha up sa mga maling interface

387
00:12:22,050 --> 00:12:23,508
na kung saan upang gamitin ang touch screen.

388
00:12:23,508 --> 00:12:24,660
Kaya na ay ang aking mga kasalanan doon.

389
00:12:24,660 --> 00:12:26,600
>> Kaya ito ay gumawa para sa
clip ng susunod na taon bilang

390
00:12:26,600 --> 00:12:28,570
sa kung bakit ako ay pag-click sa aking sariling mga screen.

391
00:12:28,570 --> 00:12:31,390
Ngunit tumagal ng isang mabilis na pagtingin hayaan
sa kung ano ang nangyari noong nakaraang taon

392
00:12:31,390 --> 00:12:34,770
Jay, na dumating up, marami
tulad Trevor dito, nagboluntaryo,

393
00:12:34,770 --> 00:12:39,380
at sa maikling clip, makikita mo ang
paano ginawa hindi lubos na ito parehong demo

394
00:12:39,380 --> 00:12:41,074
ibunyag ang parehong mga aralin natutunan.

395
00:12:41,074 --> 00:12:41,740
[Playback ng video]

396
00:12:41,740 --> 00:12:45,360
-Ang Lahat ng gusto ko sa iyo na gawin ngayon ay
upang mahanap para sa akin, at para sa amin,

397
00:12:45,360 --> 00:12:51,674
talaga, ang bilang ng 50
isang hakbang sa isang pagkakataon.

398
00:12:51,674 --> 00:12:52,450
>> -Ang Bilang 50?

399
00:12:52,450 --> 00:12:53,190
>> -Ang Bilang 50.

400
00:12:53,190 --> 00:12:55,356
At maaari mong ipakita kung ano ang
sa likod ng bawat isa sa mga pinto

401
00:12:55,356 --> 00:12:58,540
sa pamamagitan lamang ng pagpindot ito gamit ang isang daliri.

402
00:12:58,540 --> 00:13:00,910
Mapapahamak ang mga ito.

403
00:13:00,910 --> 00:13:02,870
>> [Tumatawa]

404
00:13:02,870 --> 00:13:03,806
>> [END playback]

405
00:13:03,806 --> 00:13:05,430
David J. MALAN: Kaya na nagpunta napakahusay.

406
00:13:05,430 --> 00:13:06,796
Yaong ang mga unsorted pintuan.

407
00:13:06,796 --> 00:13:08,670
At Jay, siyempre,
masyadong mabilis na natagpuan ang lahat ng ito.

408
00:13:08,670 --> 00:13:12,910
Trevor ay isang mas mas mahusay na trabaho
sa mga tuntunin ng isang madaling ituro sandali,

409
00:13:12,910 --> 00:13:15,850
wika nga, sa taong ito sa
mas matagal upang hanapin ito.

410
00:13:15,850 --> 00:13:17,950
Siyempre, pagkatapos ay nagbigay kami
Jay ng pangalawang pagkakataon,

411
00:13:17,950 --> 00:13:20,320
kung saan inayos namin ang mga pinto,
tulad ng ginawa namin para sa Trevor,

412
00:13:20,320 --> 00:13:22,300
at Trevor ay super rin oras na ito.

413
00:13:22,300 --> 00:13:26,124
Ngunit ito Jay half nang mabilis.

414
00:13:26,124 --> 00:13:26,790
[Playback ng video]

415
00:13:26,790 --> 00:13:29,650
-Ang Layunin ay ngayon upang din
hanapin sa amin sa bilang 50,

416
00:13:29,650 --> 00:13:33,030
ngunit gawin ito algorithmically, at
sabihin sa amin kung paano ka ng pagpunta sa.

417
00:13:33,030 --> 00:13:33,660
>> -SIGE.

418
00:13:33,660 --> 00:13:35,604
>> -At Kung iyong makita ito, ingatan mo ang pelikula.

419
00:13:35,604 --> 00:13:37,228
Kung hindi mo mahanap ito, binibigyan mo ang mga ito pabalik.

420
00:13:37,228 --> 00:13:38,044
>> -Man.

421
00:13:38,044 --> 00:13:38,860
>> -Oh!

422
00:13:38,860 --> 00:13:40,800
>> - [Hindi marinig] OK.

423
00:13:40,800 --> 00:13:46,236
Kaya ako pagpunta upang suriin ang mga dulo
unang upang matukoy kung there's-- Oh.

424
00:13:46,236 --> 00:13:48,646
>> [Palakpakan]

425
00:13:48,646 --> 00:13:53,948

426
00:13:53,948 --> 00:13:55,729
>> [END playback]

427
00:13:55,729 --> 00:13:56,520
David J. MALAN: OK.

428
00:13:56,520 --> 00:13:59,760
Kaya sa pag-uuri ng malinaw na pinto
hahantong sa higit na kahusayan.

429
00:13:59,760 --> 00:14:01,680
At ito, dalawang beses nang mas mabilis
ay kung ano ang ibig sabihin ko doon.

430
00:14:01,680 --> 00:14:03,270
At kaya Jay got mapalad parehong oras.

431
00:14:03,270 --> 00:14:06,685
At siya ay nakuha din sa mapalad na ang huling
taon, iniutos ko ang ilang mga Blu-ray discs

432
00:14:06,685 --> 00:14:07,560
upang aktwal na bigyan out.

433
00:14:07,560 --> 00:14:09,768
Sorry sa taong ito, kami ay
ay hindi magkakaroon ng parehong, Trevor.

434
00:14:09,768 --> 00:14:11,540
Ngunit ay mas mahusay pa rin ng ilang taon likod.

435
00:14:11,540 --> 00:14:14,820
At maaaring kilala ang ilan sa iyo na ito
kapwa, Sean, na kapag siya ay sa CS50,

436
00:14:14,820 --> 00:14:17,780
ay hinamon na may eksaktong
parehong problema, kahit na sa SD,

437
00:14:17,780 --> 00:14:19,360
tulad ng makikita mo agad makita, pabalik sa araw.

438
00:14:19,360 --> 00:14:22,622
At makikita mo na hindi lamang ay
siya ay kumuha ng isang maliit na mas mahaba kaysa sa Jay,

439
00:14:22,622 --> 00:14:25,580
isang maliit na mas mahaba kaysa sa Trevor, ito ay
tunay na ito kahanga-hangang pagkakataon

440
00:14:25,580 --> 00:14:29,820
upang hikayatin ang halos lahat ng tao sa
karamihan ng tao a la Presyo ay Kanan, na naghihikayat sa

441
00:14:29,820 --> 00:14:31,889
sa kanya upang mahanap ang numero ng aming hinahanap.

442
00:14:31,889 --> 00:14:32,930
Sabihin. kumuha ng isang mabilis na pagtingin.

443
00:14:32,930 --> 00:14:33,320
>> [Playback ng video]

444
00:14:33,320 --> 00:14:33,820
>> -SIGE.

445
00:14:33,820 --> 00:14:36,680
Kaya ang iyong mga gawain dito,
Sean, ay ang sumusunod.

446
00:14:36,680 --> 00:14:40,860
Ako ay may nakatago sa likod ng mga
pinto sa bilang pitong.

447
00:14:40,860 --> 00:14:45,120
Ngunit nakatago ang layo sa ilan sa mga pinto
pati na rin ang mga iba pang mga negatibong numero.

448
00:14:45,120 --> 00:14:47,500
At ang iyong layunin ay upang mag-isip
ng tuktok na hilera ito ng mga numero

449
00:14:47,500 --> 00:14:50,390
bilang lamang ng isang array, o lamang
pagkakasunod-sunod ng mga piraso ng papel

450
00:14:50,390 --> 00:14:51,510
na may mga numero sa likod ng mga ito.

451
00:14:51,510 --> 00:14:55,540
At ang iyong layunin ay, lamang gamit ang top
array dito, hanapin sa akin ang numero ng pitong.

452
00:14:55,540 --> 00:14:58,570
At kami ay pagkatapos ay pagpunta sa pumupuna
kung paano mo pumunta tungkol sa paggawa nito.

453
00:14:58,570 --> 00:14:59,070
-Lahat tama.

454
00:14:59,070 --> 00:15:00,850
-Find Sa amin ang numero ng pitong, please.

455
00:15:00,850 --> 00:15:10,500

456
00:15:10,500 --> 00:15:11,000
Hindi.

457
00:15:11,000 --> 00:15:15,050

458
00:15:15,050 --> 00:15:18,550
Five, 19, 13.

459
00:15:18,550 --> 00:15:22,240

460
00:15:22,240 --> 00:15:24,770
>> [Tumatawa]

461
00:15:24,770 --> 00:15:25,910
>> Ito ay hindi isang nanlilinlang tanong.

462
00:15:25,910 --> 00:15:29,410

463
00:15:29,410 --> 00:15:29,910
One.

464
00:15:29,910 --> 00:15:33,218

465
00:15:33,218 --> 00:15:34,695
>> [Tumatawa]

466
00:15:34,695 --> 00:15:37,861
Sa puntong ito, ang iyong iskor ay hindi masyadong
mabuti, sa gayon ay maaari mo rin panatilihin ang pagpunta.

467
00:15:37,861 --> 00:15:40,610

468
00:15:40,610 --> 00:15:41,110
Three.

469
00:15:41,110 --> 00:15:43,890

470
00:15:43,890 --> 00:15:45,378
>> [Tumatawa]

471
00:15:45,378 --> 00:15:46,370

472
00:15:46,370 --> 00:15:47,774
>> Ipagpatuloy mo.

473
00:15:47,774 --> 00:15:50,690
Lantaran, hindi ko maaaring makatulong ngunit magtaka
kung ano ang kahit na ang iyong iniisip tungkol sa, so--

474
00:15:50,690 --> 00:15:51,959
>> [Tumatawa]

475
00:15:51,959 --> 00:15:53,229

476
00:15:53,229 --> 00:15:55,020
Hanay sa itaas na lamang, para
Mayroon tatlong kaliwa.

477
00:15:55,020 --> 00:15:56,200
Kaya mahanap ako ng pitong.

478
00:15:56,200 --> 00:15:59,700

479
00:15:59,700 --> 00:16:02,167
>> [Tumatawa]

480
00:16:02,167 --> 00:16:14,870

481
00:16:14,870 --> 00:16:15,370
17.

482
00:16:15,370 --> 00:16:25,675

483
00:16:25,675 --> 00:16:26,946
Pitong.

484
00:16:26,946 --> 00:16:28,780
>> [Palakpakan]

485
00:16:28,780 --> 00:16:29,426
>> Lahat tama.

486
00:16:29,426 --> 00:16:30,360
>> [END playback]

487
00:16:30,360 --> 00:16:31,840
>> David J. MALAN: Kaya maaari namin
panoorin ang mga buong araw.

488
00:16:31,840 --> 00:16:34,090
At siyempre, ang ilan sa
demo na ito taon marahil

489
00:16:34,090 --> 00:16:36,330
ay ngayon ay napupunta sa susunod na
video taon pati na rin.

490
00:16:36,330 --> 00:16:39,040
Kaya ngayon sabihin aktwal
focus sa mga algorithm

491
00:16:39,040 --> 00:16:42,140
dito, at makita kung ito ay hindi natin
ngayon simulan upang gawing pormal

492
00:16:42,140 --> 00:16:46,650
kung paano namin pumunta tungkol sa pagkuha ng aming data
sa estadong ito na ito ay pinagsunod-sunod,

493
00:16:46,650 --> 00:16:50,054
para sa kalaunan, maaari naming aktwal
maghanap ng mas mahusay.

494
00:16:50,054 --> 00:16:52,470
At kahit na kami ay pagpunta
gamitin medyo maliit na set ng data,

495
00:16:52,470 --> 00:16:54,511
tulad ng mga walong numero namin
Mayroon dito sa board,

496
00:16:54,511 --> 00:16:58,230
sa huli ay maaaring gamitin ang mga parehong mga ideya
sa 1,000 na input, isang milyong input,

497
00:16:58,230 --> 00:17:02,100
4 na bilyon na input, dahil ang algorithm
ay magiging panimula ang parehong.

498
00:17:02,100 --> 00:17:05,359
>> At kaya ito ay ang aming huling
pagkakataon para sa mga boluntaryo na ngayon,

499
00:17:05,359 --> 00:17:09,790
ngunit marahil ang isa sa pinaka-kasangkot,
para sa kung saan kailangan namin ng walong volunteers

500
00:17:09,790 --> 00:17:12,960
na dumating up at paglalakad sa amin sa pamamagitan ng mga
proseso ng pag-uuri sa kung ano ang sa lalong madaling panahon

501
00:17:12,960 --> 00:17:15,212
maging sa mga music nakatayo dito.

502
00:17:15,212 --> 00:17:16,170
Hayaan akong magsimula bumalik dito.

503
00:17:16,170 --> 00:17:19,692
>> Kaya isa sa turquoise-- green ito?

504
00:17:19,692 --> 00:17:21,130
Ikaw ba gumawa?

505
00:17:21,130 --> 00:17:21,630
Dalawang.

506
00:17:21,630 --> 00:17:23,069
Halika sa down.

507
00:17:23,069 --> 00:17:23,569
SIGE.

508
00:17:23,569 --> 00:17:24,420
Three.

509
00:17:24,420 --> 00:17:25,400
Four.

510
00:17:25,400 --> 00:17:27,247
Hayaan me-- OK, lima.

511
00:17:27,247 --> 00:17:28,830
Na kayo ay hinirang ng iyong kaibigan.

512
00:17:28,830 --> 00:17:31,340
Anim, pito, walo.

513
00:17:31,340 --> 00:17:32,130
Lumapit sa up.

514
00:17:32,130 --> 00:17:32,630
Lahat tama.

515
00:17:32,630 --> 00:17:33,190
Salamat sa iyo kaya magkano.

516
00:17:33,190 --> 00:17:33,689
Lumapit sa up.

517
00:17:33,689 --> 00:17:34,790
Lumapit sa up.

518
00:17:34,790 --> 00:17:35,330
>> Lahat tama.

519
00:17:35,330 --> 00:17:38,890
Kaya kung ano ang mayroon kami here-- at ito
ay kabilang sa mga mas mahirap na mga,

520
00:17:38,890 --> 00:17:42,390
dahil ito ay kailangan na ikaw katatawanan
sa akin lamang ng isang maliit na piraso ng oras.

521
00:17:42,390 --> 00:17:43,442
Ikaw ay magiging bilang isa.

522
00:17:43,442 --> 00:17:44,150
Ano ang pangalan mo?

523
00:17:44,150 --> 00:17:44,610
>> ANNAN: Annan.

524
00:17:44,610 --> 00:17:45,526
>> David J. MALAN: Annan.

525
00:17:45,526 --> 00:17:46,092
David.

526
00:17:46,092 --> 00:17:46,800
Ano ang pangalan mo?

527
00:17:46,800 --> 00:17:47,140
>> JOSEPH: Joseph.

528
00:17:47,140 --> 00:17:49,190
>> David J. MALAN: Joseph,
mga numero ng dalawang mo.

529
00:17:49,190 --> 00:17:52,260
>> SERENA: Serena, numero ng tatlong.

530
00:17:52,260 --> 00:17:53,722
Stefan, bilang apat.

531
00:17:53,722 --> 00:17:54,430
CYNTHIA: Cynthia.

532
00:17:54,430 --> 00:17:57,548
David J. MALAN: Cynthia, numero ng limang.

533
00:17:57,548 --> 00:17:58,452
[Hindi marinig]

534
00:17:58,452 --> 00:17:59,618
David J. MALAN: [hindi marinig].

535
00:17:59,618 --> 00:18:00,391
David, numero ng anim.

536
00:18:00,391 --> 00:18:00,890
MATT: Mat.

537
00:18:00,890 --> 00:18:02,160
David J. MALAN: Matt numero ng pitong.

538
00:18:02,160 --> 00:18:02,850
At?

539
00:18:02,850 --> 00:18:03,210
>> WAVERLY: Waverly.

540
00:18:03,210 --> 00:18:04,470
>> David J. MALAN: Waverly, numero ng walong.

541
00:18:04,470 --> 00:18:04,970
Lahat tama.

542
00:18:04,970 --> 00:18:06,510
Kung could-- ka Oops.

543
00:18:06,510 --> 00:18:08,820
Kung sa iyo ang lahat, tulad ng iyong
unang hamon, may

544
00:18:08,820 --> 00:18:10,820
mga walong kinatatayuan musika
nakaharap dito ang madla.

545
00:18:10,820 --> 00:18:14,200
Kung maaari mong ilagay ang iyong numero sa
mga music nakatayo sa paraan

546
00:18:14,200 --> 00:18:16,560
na line up nila sa mga
parehong numero sa board.

547
00:18:16,560 --> 00:18:19,560
Kaya gumawa ng sarili hitsura na sa pamamagitan ng
paglalagay ng iyong mga numero sa mga music

548
00:18:19,560 --> 00:18:21,960
nakatayo dito.

549
00:18:21,960 --> 00:18:25,980
Magaling sa ngayon.

550
00:18:25,980 --> 00:18:26,600
>> Magaling.

551
00:18:26,600 --> 00:18:26,890
SIGE.

552
00:18:26,890 --> 00:18:29,556
Kaya ngayon, kami ay pagpunta sa hilingin sa mga
tanong sa loob ng ilang iba't-ibang paraan.

553
00:18:29,556 --> 00:18:31,610
Paano namin pumunta tungkol sa pag-uuri
dito ang mga tao up?

554
00:18:31,610 --> 00:18:34,500
Dahil nagkaroon kami ng ilang mga pamamaraang
mas maaga, kung saan tayo ay

555
00:18:34,500 --> 00:18:36,360
uri ng paggawa ng dalawang magkaibang mga bucket.

556
00:18:36,360 --> 00:18:38,842
At pagkatapos kami ay sa pangkalahatan
piecing bagay nang magkakasama.

557
00:18:38,842 --> 00:18:41,050
Nang makita kami ng dalawang mga numero
na pag-aari sama-sama,

558
00:18:41,050 --> 00:18:41,975
inilalagay namin ang mga ito nang magkakasama.

559
00:18:41,975 --> 00:18:43,350
Dalawang titik na pag-aari sama-sama.

560
00:18:43,350 --> 00:18:45,058
>> Ngunit sabihin makita kung kami
hindi maaaring gawing pormal ito,

561
00:18:45,058 --> 00:18:48,044
kaya na namin sa huli ay may
ilang tunay code ay sa iyo,

562
00:18:48,044 --> 00:18:49,710
na kung saan maaari mong malutas ang mga problemang ito.

563
00:18:49,710 --> 00:18:51,870
Kaya ngayon, Naghahanap ako ng out
sa mga numerong ito dito.

564
00:18:51,870 --> 00:18:55,030
At nakikita ko ang maramihang mga pagkakamali.

565
00:18:55,030 --> 00:18:57,750
Sa huli, gusto ko ang isa sa mga
kaliwa at walong sa kanan.

566
00:18:57,750 --> 00:19:00,650
>> At kaya Naghahanap ako sa
mga dalawang, apat at dalawa.

567
00:19:00,650 --> 00:19:02,930
At ano ang problema, malinaw naman?

568
00:19:02,930 --> 00:19:04,261
Oo.

569
00:19:04,261 --> 00:19:04,760
So.

570
00:19:04,760 --> 00:19:07,160
Dalawang malinaw na hinango bago
apat, sa gayon alam mo kung ano?

571
00:19:07,160 --> 00:19:10,210
Hayaan akong unang kumuha ng isang sakim na diskarte,
kung ikaw ay, magkano ang gusto problema

572
00:19:10,210 --> 00:19:13,790
itakda one-- kung isipin mo mula sa
Standard Edition ng Problema Itakda One,

573
00:19:13,790 --> 00:19:16,820
kung saan ko lang sa local na malutas ang problema
na dito mismo sa harap ng akin

574
00:19:16,820 --> 00:19:17,690
at makita kung saan ito ay humahantong sa akin.

575
00:19:17,690 --> 00:19:17,870
>> SIGE.

576
00:19:17,870 --> 00:19:20,161
Kaya dalawa at apat, hayaan mo akong
magpatuloy at lang magpalit ka dalawa.

577
00:19:20,161 --> 00:19:22,400
Kung maaari mong pisikal na ilipat
inyong sarili at ang iyong papel,

578
00:19:22,400 --> 00:19:25,040
Mukhang ako na may tapat na paraan ng
ilista sa isang mas mahusay na estado.

579
00:19:25,040 --> 00:19:26,330
>> Ngayon, ang mga ito ay mabuti.

580
00:19:26,330 --> 00:19:28,480
Pupunta ako upang ilipat sa,
apat at anim, mukhang maganda.

581
00:19:28,480 --> 00:19:29,110
Hindi problema.

582
00:19:29,110 --> 00:19:30,440
Anim walo, OK.

583
00:19:30,440 --> 00:19:31,860
Eight at isa, isa pang problema.

584
00:19:31,860 --> 00:19:34,750
Dahil kung ano ang totoo tungkol sa walong at isa?

585
00:19:34,750 --> 00:19:36,990
One dumating bago walo,
at kaya kung ano ang dapat naming gawin?

586
00:19:36,990 --> 00:19:38,090
Magpalitan ng mga dalawang.

587
00:19:38,090 --> 00:19:39,316
One walo.

588
00:19:39,316 --> 00:19:40,690
At ngayon, ako pagpunta sa panatilihin ang pagpunta.

589
00:19:40,690 --> 00:19:42,030
Pupunta ako sa panatilihin ang hinahanap nang mas maaga.

590
00:19:42,030 --> 00:19:42,840
At makita kung ano ang mangyayari.

591
00:19:42,840 --> 00:19:44,680
Eight at tatlong, ng
Siyempre, sa labas ng order.

592
00:19:44,680 --> 00:19:45,815
Ni swap Hayaan.

593
00:19:45,815 --> 00:19:46,940
Eight at pitong, siyempre.

594
00:19:46,940 --> 00:19:47,481
Mula sa order.

595
00:19:47,481 --> 00:19:48,280
Ni swap Hayaan.

596
00:19:48,280 --> 00:19:49,940
Eight at limang, siyempre, sabihin swap.

597
00:19:49,940 --> 00:19:50,560
Lahat tama.

598
00:19:50,560 --> 00:19:51,880
Listahan ay pinagsunod-sunod.

599
00:19:51,880 --> 00:19:53,060
yes?

600
00:19:53,060 --> 00:19:54,280
>> OK, malinaw naman hindi.

601
00:19:54,280 --> 00:19:55,860
Ngunit ito ay isang maliit na mas mahusay, tama?

602
00:19:55,860 --> 00:19:57,270
Dahil kung ano ang notice nangyari.

603
00:19:57,270 --> 00:20:01,749
Sa bawat oras na namin ginanap sa isang swap, isang mas maliit
number percolated uri ng na paraan,

604
00:20:01,749 --> 00:20:03,790
at ang isang mas malaking bilang
percolated ganitong paraan, o bibigyan namin ng

605
00:20:03,790 --> 00:20:06,880
simulan sinasabi bubbled sa
pakaliwa o bubbled sa kanan.

606
00:20:06,880 --> 00:20:10,080
>> Ngayon, ito ay hindi sapat, dahil
sa pinakamahusay na isang numero ng kapangyarihan

607
00:20:10,080 --> 00:20:11,990
Inilipat sa isang lugar
pasulong, o sa pinakamalala,

608
00:20:11,990 --> 00:20:13,880
ay maaaring magkaroon ng isang bilang
inilipat sa isang spot sa karagdagang.

609
00:20:13,880 --> 00:20:16,369
Kaya alam mo kung ano ang, uri na ito
ng medyo maayos na nagtrabaho sa ngayon.

610
00:20:16,369 --> 00:20:17,410
Hayaan lamang na subukan uli ako dito.

611
00:20:17,410 --> 00:20:18,880
Dalawang at apat na, ang mga ito ay OK.

612
00:20:18,880 --> 00:20:20,180
Apat at anim na, ang mga ito ay OK.

613
00:20:20,180 --> 00:20:21,790
Anim at isa, sa labas ng order.

614
00:20:21,790 --> 00:20:23,007
So magpalit ni kang dalawang ipaalam.

615
00:20:23,007 --> 00:20:25,840
At ngayon, mapapansin ang problema ni
simula upang makakuha ng isang maliit na mas mahusay na muli.

616
00:20:25,840 --> 00:20:27,006
Anim at tatlong, sa labas ng order.

617
00:20:27,006 --> 00:20:28,100
Swap ni mo dalawang.

618
00:20:28,100 --> 00:20:29,730
Anim at pitong, ikaw ay mabuti.

619
00:20:29,730 --> 00:20:32,230
Pitong at limang, siyempre, sa labas ng order.

620
00:20:32,230 --> 00:20:33,920
Seven at walong, sa order.

621
00:20:33,920 --> 00:20:36,470
At ngayon, maaaring kailangan ko upang
gawin ito ng ilang higit pang mga beses.

622
00:20:36,470 --> 00:20:39,830
At sa katunayan, sa tingin para sa inyong sarili
marahil kung gaano karaming beses maximally

623
00:20:39,830 --> 00:20:41,330
baka ako kailangang maglakad papunta at pabalik?

624
00:20:41,330 --> 00:20:42,390
>> Susubukan naming bumalik sa mga iyon.

625
00:20:42,390 --> 00:20:43,700
Kaya dalawa at apat na mga OK pa rin.

626
00:20:43,700 --> 00:20:44,940
Apat at isa, nope.

627
00:20:44,940 --> 00:20:45,747
Kaya, swap ipaalam.

628
00:20:45,747 --> 00:20:47,830
At muli, napansin biswal
isa ay uri ng bulubok

629
00:20:47,830 --> 00:20:49,163
sa kaliwa, kung saan ito ay dapat.

630
00:20:49,163 --> 00:20:50,010
Apat at tatlong swap.

631
00:20:50,010 --> 00:20:51,330
Apat anim.

632
00:20:51,330 --> 00:20:53,100
Anim at limang swap.

633
00:20:53,100 --> 00:20:53,959
Anim at pitong.

634
00:20:53,959 --> 00:20:55,000
Seven at walong ay mabuti.

635
00:20:55,000 --> 00:20:55,500
>> Good.

636
00:20:55,500 --> 00:20:58,460
Kahit na mas mahusay Kami ay nakakakuha.

637
00:20:58,460 --> 00:20:59,130
Kaya sabihin makita.

638
00:20:59,130 --> 00:21:00,940
Ngayon, kami ay may dalawa at isa.

639
00:21:00,940 --> 00:21:02,520
Siyempre, magpalit.

640
00:21:02,520 --> 00:21:07,520
Dalawang at tatlong, tatlo at apat, apat at
lima, anim at pito, pitong walo.

641
00:21:07,520 --> 00:21:08,020
Good.

642
00:21:08,020 --> 00:21:08,730
At alam mo kung ano?

643
00:21:08,730 --> 00:21:11,190
Dahil ginawa ko ng isang pagbabago doon,
hayaan mo akong gawin ang isa katinuan check.

644
00:21:11,190 --> 00:21:13,023
Hayaan akong pumunta sa lahat ng paraan
bumalik sa simula.

645
00:21:13,023 --> 00:21:13,680
SIGE.

646
00:21:13,680 --> 00:21:14,750
One, two-- yup, tingnan?

647
00:21:14,750 --> 00:21:15,870
Isang bagay ay mali.

648
00:21:15,870 --> 00:21:18,420
Tatlo, apat, lima, anim, pitong, walong.

649
00:21:18,420 --> 00:21:21,920
At sa mga huling pass, ay
ikaw ay komportable sa aking ngayon

650
00:21:21,920 --> 00:21:23,830
pagtubos ng ito ay pinagsunod-sunod?

651
00:21:23,830 --> 00:21:24,330
SIGE.

652
00:21:24,330 --> 00:21:25,880
Biswal na, na ang ganap na totoo.

653
00:21:25,880 --> 00:21:28,410
Ngunit sa pagtakbo, kung ano
nag ring mangyari lamang

654
00:21:28,410 --> 00:21:31,870
sa huling na pass na nagpapahintulot sa iyo
upang kumpirmahin na ang listahan na ito ay sa katunayan

655
00:21:31,870 --> 00:21:32,660
Inayos?

656
00:21:32,660 --> 00:21:34,477
>> Ano ang gagawin ko o hindi gawin ito huling pass?

657
00:21:34,477 --> 00:21:35,810
Madla: Walang pagbabago.

658
00:21:35,810 --> 00:21:36,120
David J. MALAN: Paumanhin?

659
00:21:36,120 --> 00:21:37,070
Madla: Walang pagbabago.

660
00:21:37,070 --> 00:21:38,653
David J. MALAN: Walang pagbabago.

661
00:21:38,653 --> 00:21:41,947
Kaya magiging bobo ko na
muli gawin na parehong algorithm

662
00:21:41,947 --> 00:21:43,780
kung ako ay hindi gumawa ng anumang
mga pagbabago sa unang pagkakataon.

663
00:21:43,780 --> 00:21:45,160
At ang estado ay hindi nagbago.

664
00:21:45,160 --> 00:21:47,576
Tiyak, hindi ako pagpunta sa gumawa
anumang mga pagbabago sa ikalawang pagkakataon.

665
00:21:47,576 --> 00:21:49,820
At ito, ito ay ligtas na ngayon
sabihin, listahan ay nakaayos.

666
00:21:49,820 --> 00:21:52,069
>> At sa katunayan, ito ay ngayon
isang bagay na ipapakita namin sa pangkalahatan

667
00:21:52,069 --> 00:21:56,900
call bubble sort, kung saan pairwise,
itama mo pagkakamali muli,

668
00:21:56,900 --> 00:22:00,210
at muli, at muli, at ikaw ay
panatilihin ang pagpunta papunta at pabalik,

669
00:22:00,210 --> 00:22:03,370
at pabalik-balik, hanggang sa ikaw ay
gumawa ng walang tulad swaps, at sa puntong

670
00:22:03,370 --> 00:22:07,089
maaari kang maging kumpyansa, oo, ako
tapos sa pag-aayos ng lahat ng mga pagkakamali.

671
00:22:07,089 --> 00:22:08,630
Ni-reset at subukan ang ibang diskarte.

672
00:22:08,630 --> 00:22:11,590
Kung ikaw guys maaaring bumalik sa
ang order na kayo ay isang sandali ang nakalipas,

673
00:22:11,590 --> 00:22:13,780
na mukhang ito.

674
00:22:13,780 --> 00:22:17,640
Ngayon, sabihin kumuha ng isang diskarte ng
kaunti pa tulad ng mga libro pagsusulit,

675
00:22:17,640 --> 00:22:21,122
kung saan kami ay patuloy na
pagpili sa titik ng alpabetong

676
00:22:21,122 --> 00:22:22,830
na uri ng namin pinaghahanap
upang harapin ang susunod.

677
00:22:22,830 --> 00:22:26,420
Siguro, ito ay isang mataas na sulat,
tulad ng A, o isang mababang sulat Z.

678
00:22:26,420 --> 00:22:28,170
>> Kaya lahat ay bumalik sa ayos na ito.

679
00:22:28,170 --> 00:22:29,800
At ngayon hayaan mo akong gawin ito.

680
00:22:29,800 --> 00:22:34,880
Tingnan natin kung alam ko ako Hayaan
walong numero dito.

681
00:22:34,880 --> 00:22:37,410
Pupunta ako sa sige at
sadyang piliin lamang

682
00:22:37,410 --> 00:22:38,520
ang pinakamaliit na elemento.

683
00:22:38,520 --> 00:22:38,760
Right?

684
00:22:38,760 --> 00:22:39,801
Ito ay tila masyadong intuitive.

685
00:22:39,801 --> 00:22:42,560
Bakit hindi ko mahanap ang pinakamaliit
element, ilagay ito kung saan ito ay kabilang,

686
00:22:42,560 --> 00:22:45,280
pagkatapos makuha ang susunod na pinakamaliit na elemento, ilagay
ito kung saan ito ay kabilang, at ulitin lamang.

687
00:22:45,280 --> 00:22:46,820
>> Dahil intuitively,
na dapat gumana masyadong.

688
00:22:46,820 --> 00:22:48,441
Kaya apat, na ang isang medyo maliit na bilang.

689
00:22:48,441 --> 00:22:49,940
Pupunta ako sa tandaan kung saan ito ay.

690
00:22:49,940 --> 00:22:50,523
Sandali lang.

691
00:22:50,523 --> 00:22:51,577
Dalawang ay mas maliit.

692
00:22:51,577 --> 00:22:53,910
Hayaan alalahanin mo ako ngayon kung saan ang dalawang
ay, at kalimutan ang tungkol sa apat.

693
00:22:53,910 --> 00:22:55,050
Susubukan naming haharapin ang mga iyon sa ibang pagkakataon.

694
00:22:55,050 --> 00:22:56,460
Anim na, hindi ako interesado.

695
00:22:56,460 --> 00:22:57,810
Eight, hindi ako interesado.

696
00:22:57,810 --> 00:22:59,780
Isa ang aking bagong maliit na bilang.

697
00:22:59,780 --> 00:23:01,470
Kaya ako pagpunta sa tandaan kung saan ang isa ay.

698
00:23:01,470 --> 00:23:02,534
Three, hindi interesado.

699
00:23:02,534 --> 00:23:03,450
Seven, hindi interesado.

700
00:23:03,450 --> 00:23:04,530
Limang, hindi interesado.

701
00:23:04,530 --> 00:23:07,390
>> Kaya walang lagas
ang yugto sa taong ito,

702
00:23:07,390 --> 00:23:09,890
Pupunta ako sa grab number one--
at kung ano ang muli ay ang pangalan mo?

703
00:23:09,890 --> 00:23:10,150
>> ANNAN: Annan.

704
00:23:10,150 --> 00:23:11,220
>> David J. MALAN: Annan.

705
00:23:11,220 --> 00:23:13,540
At kung kayo ay sumali sa akin sa
sa simula ng listahan,

706
00:23:13,540 --> 00:23:14,870
Maglagay mo kung saan ka nabibilang ipaalam.

707
00:23:14,870 --> 00:23:16,080
Unfortunately-- ano ang pangalan mo?

708
00:23:16,080 --> 00:23:16,650
>> STEFAN: Stefan.

709
00:23:16,650 --> 00:23:18,191
>> David J. MALAN: Stefan ay sa paraan.

710
00:23:18,191 --> 00:23:23,490
Kaya bago Stefan malulutas nito ang
Ang problema, ano ang dapat naming gawin?

711
00:23:23,490 --> 00:23:25,412
Ano ang gagawin namin sa Stefan?

712
00:23:25,412 --> 00:23:27,269
>> Madla: [hindi marinig].

713
00:23:27,269 --> 00:23:28,060
David J. MALAN: OK.

714
00:23:28,060 --> 00:23:28,850
Kaya maaari naming gawin iyon.

715
00:23:28,850 --> 00:23:31,730
Kami ay maaaring uri ng tumagal Stefan at ang kanyang
apat, at lamang ilagay ito sa isang variable

716
00:23:31,730 --> 00:23:33,530
at kumapit sa mga ito para sa
ilang mga halaga ng oras,

717
00:23:33,530 --> 00:23:35,220
sa gayon ang paggawa ng room para sa isang numero.

718
00:23:35,220 --> 00:23:36,280
At iyan ay hindi masama.

719
00:23:36,280 --> 00:23:39,270
Maaaring Mungkahi ko, bakit hindi
ilagay lang namin Stefan dito?

720
00:23:39,270 --> 00:23:41,610
Bakit maaaring lumalabag sa isang ito
ng mga ideya namin na nagsimula

721
00:23:41,610 --> 00:23:44,830
pakikipag-usap tungkol sa huling panahon, noong nakaraang linggo?

722
00:23:44,830 --> 00:23:45,330
Oo?

723
00:23:45,330 --> 00:23:45,740
>> Madla: [hindi marinig].

724
00:23:45,740 --> 00:23:46,860
>> David J. MALAN: Walang index para sa mga ito.

725
00:23:46,860 --> 00:23:49,735
Kung sa tingin mo ng mga ito, sa katunayan, bilang isang
array, ito ay tulad ng negatibong isa,

726
00:23:49,735 --> 00:23:52,900
kaya walang memory talaga
dito kung ito nga ay isang array,

727
00:23:52,900 --> 00:23:55,090
tulad ng ipinahayag namin noong nakaraang linggo sa panayam.

728
00:23:55,090 --> 00:23:56,250
Kaya hindi namin dapat gawin ito.

729
00:23:56,250 --> 00:23:57,340
Maaari naming iimbak ito sa isang variable.

730
00:23:57,340 --> 00:23:57,820
>> O alam mo kung ano?

731
00:23:57,820 --> 00:23:59,153
Narinig ko ang ibang tao iminumungkahi ito.

732
00:23:59,153 --> 00:24:01,020
Ano pa ang maaari naming gawin sa Stefan?

733
00:24:01,020 --> 00:24:03,770
Bakit hindi paalisin namin siya lamang at
inilagay siya sa kung saan bilang isa ay.

734
00:24:03,770 --> 00:24:05,170
Kaya kung nais mong pumunta doon.

735
00:24:05,170 --> 00:24:07,300
At sa katunayan, ito ay isang
pretty magandang solusyon.

736
00:24:07,300 --> 00:24:10,480
Ngayon sa isang banda, na ako ng uri
ng ginawa ang problema mas masahol pa.

737
00:24:10,480 --> 00:24:13,650
Apat na ngayon ang mas malayo
mula sa kung saan ito ay dapat.

738
00:24:13,650 --> 00:24:14,900
Ito ay dapat na ito papunta sa kalahati.

739
00:24:14,900 --> 00:24:16,100
>> Pero alam mo kung ano?

740
00:24:16,100 --> 00:24:17,630
Na maaaring naging masamang kapalaran.

741
00:24:17,630 --> 00:24:18,822
Siguro bilang walong ay dito.

742
00:24:18,822 --> 00:24:20,530
At ito, marahil gusto namin
nakuha masuwerteng,

743
00:24:20,530 --> 00:24:22,460
at itinulak walong mas malapit sa dulo.

744
00:24:22,460 --> 00:24:24,710
Kaya sa katapusan ng araw,
ito uri ng lahat out katamtaman.

745
00:24:24,710 --> 00:24:26,085
Hindi natin kailangan sa pag-aalaga tungkol sa apat.

746
00:24:26,085 --> 00:24:29,400
Lahat ng pag-aalaga ko tungkol sa ngayon ay
pagpili ng pinakamaliit na elemento.

747
00:24:29,400 --> 00:24:32,030
>> At ngayon, kung ano ako ng pagpunta sa
gawin ay kalimutan ang tungkol sa numero ng isa

748
00:24:32,030 --> 00:24:35,160
permanente, dahil alam ko ang
list sa likod ako ay inayos ngayon.

749
00:24:35,160 --> 00:24:36,720
Kaya ang aking list dati ay size walo.

750
00:24:36,720 --> 00:24:37,720
Ngayon, ito ay ang laki ng pito.

751
00:24:37,720 --> 00:24:40,340
Kaya ang aking mga problema ay nakakakuha ng
mas maliit, kahit na linear.

752
00:24:40,340 --> 00:24:43,022
Kaya ngayon, ako pagpunta upang piliin ang
kasalukuyang pinakamaliit na elemento, dalawa.

753
00:24:43,022 --> 00:24:46,520
Anim, walo, apat, tatlo, pitong, lima.

754
00:24:46,520 --> 00:24:47,770
Iyon ay ang pinakamaliit na elemento.

755
00:24:47,770 --> 00:24:49,416
Kaya kung ano ang ako pagpunta sa gawin with--
kung ano ang muli ay ang pangalan mo?

756
00:24:49,416 --> 00:24:49,760
>> JOSEPH: Joseph.

757
00:24:49,760 --> 00:24:50,085
>> David J. MALAN: Joseph?

758
00:24:50,085 --> 00:24:52,000
Kami ay pagpunta sa umalis Joseph sa lugar.

759
00:24:52,000 --> 00:24:54,842
Ngayon, ako pagpunta upang magpanggap
na ang mga guys are-- rin,

760
00:24:54,842 --> 00:24:56,550
Alam ko na ang mga ito ng dalawang
ay pinagsunod-sunod.

761
00:24:56,550 --> 00:24:58,424
Hayaan focus ngayon sa
naiwan ng listahan.

762
00:24:58,424 --> 00:25:00,080
Anim ay ang kasalukuyang pinakamaliit.

763
00:25:00,080 --> 00:25:01,190
Eight ay mas malaki.

764
00:25:01,190 --> 00:25:02,970
Apat na ngayon ang kasalukuyang pinakamaliit.

765
00:25:02,970 --> 00:25:04,762
Tatlong ngayon ay ang kasalukuyang pinakamaliit.

766
00:25:04,762 --> 00:25:07,720
At kaya ngayon, ako pagpunta upang piliin tatlo,
na is-- ano ang muli ang iyong pangalan?

767
00:25:07,720 --> 00:25:08,190
SERENA: Serena.

768
00:25:08,190 --> 00:25:10,620
David J. MALAN: Serena, kung magagawa mong
grab ang iyong numero at swap with--

769
00:25:10,620 --> 00:25:11,550
Kalsang: Kalsang.

770
00:25:11,550 --> 00:25:12,940
David J. MALAN: Kalsang.

771
00:25:12,940 --> 00:25:15,220
Lumapit sa likod, at hindi namin
pagpunta sa magpalitan ng mga dalawang.

772
00:25:15,220 --> 00:25:17,360
At ngayon, ni ilagay ito sa autopilot ipaalam.

773
00:25:17,360 --> 00:25:21,589
Pupunta ako sa pumunta at mag-iwan ito sa iyo guys
upang piliin ang susunod na maliit na mga elemento.

774
00:25:21,589 --> 00:25:22,380
Dun, dun, dun, dun.

775
00:25:22,380 --> 00:25:24,560
Numero ng apat, kung ano ang dapat mong gawin?

776
00:25:24,560 --> 00:25:26,261
Magaling.

777
00:25:26,261 --> 00:25:27,760
Ngayon, ako pagpunta sa gumawa ng isa pang pass.

778
00:25:27,760 --> 00:25:28,590
Dun, dun, dun, dun.

779
00:25:28,590 --> 00:25:31,465
Nakakakita ako ng limang ay ang susunod na pinakamaliit.

780
00:25:31,465 --> 00:25:32,840
Ngayon, ako pagpunta kumuha ng isa pang pass.

781
00:25:32,840 --> 00:25:33,631
Dun, dun, dun, dun.

782
00:25:33,631 --> 00:25:34,880
Anim ay ang pinakamaliit.

783
00:25:34,880 --> 00:25:35,520
Good.

784
00:25:35,520 --> 00:25:36,585
Pitong ay ang pinakamaliit.

785
00:25:36,585 --> 00:25:37,085
Walang pagbabago.

786
00:25:37,085 --> 00:25:38,630
Eight ay ang pinakamaliit.

787
00:25:38,630 --> 00:25:39,170
Tapos na.

788
00:25:39,170 --> 00:25:43,900
>> Kaya kung ano lang namin nagawa sa pamamagitan iteratively
pagpili ng isa element matapos ang iba pang

789
00:25:43,900 --> 00:25:47,230
ay ipatupad ang isang bagay na hindi namin
pagpunta upang gawing pormal bilang uri selection.

790
00:25:47,230 --> 00:25:49,120
At ito ay marahil kahit na
mas simple upang ipaliwanag,

791
00:25:49,120 --> 00:25:51,310
in na literal lahat mo
nais na gawin ay panatilihin lamang

792
00:25:51,310 --> 00:25:54,700
balik-balik sa listahan
pagpili, ang susunod na pinakamaliit na elemento,

793
00:25:54,700 --> 00:25:55,720
hanggang sa ikaw ay tapos na.

794
00:25:55,720 --> 00:25:58,650
>> Kaya ito ay kahit na mas simple, marahil
intuitively, kaysa sa nakaraang.

795
00:25:58,650 --> 00:26:00,020
Subukan natin ang huling ng isa.

796
00:26:00,020 --> 00:26:03,060
Kung ikaw guys ay maaaring i-reset ang inyong sarili
sa mga sumusunod na mga posisyon

797
00:26:03,060 --> 00:26:08,600
ng isang pangwakas na oras, tingnan natin kung hindi namin maaari
ngayon gawing pormal ang isa sa iba pang mga diskarte.

798
00:26:08,600 --> 00:26:12,857
Sa katunayan, ay isang tao
out there nais imungkahi

799
00:26:12,857 --> 00:26:14,440
kung paano pa namin maaaring pumunta tungkol sa paggawa nito?

800
00:26:14,440 --> 00:26:17,439
Walang paghuhugas ang buzzwords o pag-uuri
ng mga sagot na nai-kilala,

801
00:26:17,439 --> 00:26:19,689
intuitively lang, kung ano ang maaari naming gawin?

802
00:26:19,689 --> 00:26:21,635
>> Madla: [hindi marinig].

803
00:26:21,635 --> 00:26:22,510
David J. MALAN: Oo.

804
00:26:22,510 --> 00:26:24,620
Kaya may ilang mga mahusay na Swersey doon.

805
00:26:24,620 --> 00:26:28,020
Magandang mga bagay na tila sa mangyayari kaya sa ngayon
sa computer science kapag hinati namin

806
00:26:28,020 --> 00:26:30,832
at mapaglabanan ang problema ng paghahati
ito sa kalahati at kalahati at kalahati.

807
00:26:30,832 --> 00:26:32,540
At kaya nga, kami ay
maaaring simulan upang gawin iyon.

808
00:26:32,540 --> 00:26:35,754
At sa katunayan, iyon ay magiging, ipapakita namin
makita, isa sa aming pinakamahusay na solusyon pa.

809
00:26:35,754 --> 00:26:37,420
Ngunit sabihin ay bumalik sa na bago mahaba ipaalam.

810
00:26:37,420 --> 00:26:40,500
Sa katunayan, kami ay pagpunta sa gawin
na ang isang maliit na mamaya sa linggong ito.

811
00:26:40,500 --> 00:26:42,180
Ano pa ang maaari naming gawin upang malutas ito?

812
00:26:42,180 --> 00:26:44,647
Kaya lahat ng tao dito ay sa
tila random na order.

813
00:26:44,647 --> 00:26:45,230
Alam mo ba?

814
00:26:45,230 --> 00:26:48,320
Sa halip na bumalik-balik,
papunta at pabalik, papunta at pabalik

815
00:26:48,320 --> 00:26:50,624
sa bawat oras, ito nararamdaman tulad ng
Ako paggawa ng isang pulutong ng mga naglalakad.

816
00:26:50,624 --> 00:26:52,790
Bakit hindi simulan lang ako sa
sa simula ng listahan,

817
00:26:52,790 --> 00:26:54,960
at ilagay lamang sa apat na kung saan ito aari?

818
00:26:54,960 --> 00:26:59,680
Kaya hayaan mo akong ipalagay para sa sandaling iyon
aking listahan ay lamang ang unang elemento.

819
00:26:59,680 --> 00:27:04,937
Ay apat na pinagsunod-sunod sa panahon na ito sa oras,
kung ang lahat ng pag-aalaga ko tungkol dito sa lahat ng bagay?

820
00:27:04,937 --> 00:27:06,520
Ito ay uri ng trivially totoo, di ba?

821
00:27:06,520 --> 00:27:10,000
Tulad ng mga listahan na naglalaman ng isang numero, at
na apat na numero ay malinaw naman inayos.

822
00:27:10,000 --> 00:27:13,070
>> Kaya ipaalam magtadhana sa akin lamang
na listahan na ito ay pinagsunod-sunod.

823
00:27:13,070 --> 00:27:15,090
Ngunit ngayon ay mayroon akong mga natitira sa listahang ito.

824
00:27:15,090 --> 00:27:17,240
Kaya ngayon, nakatagpo ako ng dalawang.

825
00:27:17,240 --> 00:27:21,690
Saan ang dalawang malinaw naman
nabibilang na may paggalang sa apat?

826
00:27:21,690 --> 00:27:22,580
Bago apat.

827
00:27:22,580 --> 00:27:23,862
Kaya kung ano ang maaari kong gawin dito?

828
00:27:23,862 --> 00:27:24,820
Ano ulit ang pangalan mo?

829
00:27:24,820 --> 00:27:25,090
>> JOSEPH: Joseph.

830
00:27:25,090 --> 00:27:26,030
>> David J. MALAN: Joseph,
kung maaari mong hakbang likod

831
00:27:26,030 --> 00:27:27,790
para sa sandali lamang ito sa iyong numero.

832
00:27:27,790 --> 00:27:31,130
At ngayon kung ano ang dapat gawin dito Stefan?

833
00:27:31,130 --> 00:27:33,720
Shift ni Stefan sa paglipas dito.

834
00:27:33,720 --> 00:27:35,520
At ngayon, hayaan Joseph pumasok ka dito.

835
00:27:35,520 --> 00:27:39,660
At ngayon, hayaan mo akong i-claim na
lahat ng bagay dito ay pinagsunod-sunod.

836
00:27:39,660 --> 00:27:42,474
Kaya, katulad na resulta, ngunit isang
panimula iba't ibang mga diskarte.

837
00:27:42,474 --> 00:27:44,140
Hindi ko pa kahit na tumingin kung ano ang down doon.

838
00:27:44,140 --> 00:27:46,310
Katatapos ko lamang panatilihin ang pagkuha ng mga elemento
bilang mga ito ay ipinasa sa akin,

839
00:27:46,310 --> 00:27:47,240
at makikitungo sa kanila.

840
00:27:47,240 --> 00:27:48,330
>> Kaya ngayon, nakikita ko ang numero ng anim.

841
00:27:48,330 --> 00:27:51,110
Saan ang numero ng anim na nabibilang?

842
00:27:51,110 --> 00:27:53,250
Mayroon kaming dalawang, apat, anim.

843
00:27:53,250 --> 00:27:54,800
Eksakto kung saan siya ay sa ngayon.

844
00:27:54,800 --> 00:27:57,750
Kaya ng iwan na mag-isa ipaalam, at ngayon
paghahabol na ito sa bahagi ng listahan

845
00:27:57,750 --> 00:27:58,772
ay inayos ngayon.

846
00:27:58,772 --> 00:28:01,230
At ito, ang nararamdaman panimula
naiiba sa na lang ako

847
00:28:01,230 --> 00:28:05,230
paglipat sa pamamagitan ng listahan dito
linearly, at ako ay hindi kailanman pagdodoble likod.

848
00:28:05,230 --> 00:28:05,730
Oo.

849
00:28:05,730 --> 00:28:06,230
Lahat tama.

850
00:28:06,230 --> 00:28:08,190
Kaya walong, saan ka nabibilang?

851
00:28:08,190 --> 00:28:08,730
Dito.

852
00:28:08,730 --> 00:28:09,310
Perpekto.

853
00:28:09,310 --> 00:28:10,210
Kaya ngayon, isa.

854
00:28:10,210 --> 00:28:10,900
Naku.

855
00:28:10,900 --> 00:28:13,010
Ito nararamdaman tulad ng ito ay
magiging mahal.

856
00:28:13,010 --> 00:28:15,690
Ngayon, sa mga nakaraang algorithm,
Lamang swapped ko ang mga tao.

857
00:28:15,690 --> 00:28:18,648
Kaya maaari ko bang ilagay sa kanya lahat ng mga paraan sa
sa simula, ngunit pagkatapos ay inilipat Joseph.

858
00:28:18,648 --> 00:28:21,450
Ngunit kung ilipat ko Joseph, ngayon
kung ano ang nangyayari na mali?

859
00:28:21,450 --> 00:28:24,250
>> Ngayon, hindi ko na uri ng undone-- na ko
kinuha ng isang hakbang pasulong at pagkatapos ay

860
00:28:24,250 --> 00:28:26,300
isang hakbang sa likod, dahil ngayon
Joseph ay sa labas ng order.

861
00:28:26,300 --> 00:28:26,830
Kaya sabihin gawin ito.

862
00:28:26,830 --> 00:28:29,150
Kung maaari kang kumuha bilang isa
at hakbang pabalik para sa sandali lamang.

863
00:28:29,150 --> 00:28:30,490
Paano natin put-- ano
ay muli ang iyong pangalan?

864
00:28:30,490 --> 00:28:31,130
>> ANNAN: Annan.

865
00:28:31,130 --> 00:28:32,610
>> David J. MALAN: Annan sa lugar?

866
00:28:32,610 --> 00:28:36,091
Ano ang kailangang mangyari na may paggalang
sa dalawa, apat, anim, walo?

867
00:28:36,091 --> 00:28:37,570
Lahat sila ay kailangan sa paglilipat.

868
00:28:37,570 --> 00:28:42,590
Kaya kung walong nais na maglipat
una, pagkatapos ng anim na, pagkatapos ng apat na, pagkatapos ng dalawang.

869
00:28:42,590 --> 00:28:45,380
At pagkatapos Annan, kung gusto mo sa
nais na pumasok ka dito, mabuti.

870
00:28:45,380 --> 00:28:47,760
Ngunit dito, na namin lamang
uri ng mga bayad na isang presyo

871
00:28:47,760 --> 00:28:49,510
sa isang iba't ibang mga punto sa algorithm.

872
00:28:49,510 --> 00:28:52,550
Sapagkat huling oras na may seleksyon
uri, at kahit na bubble uri,

873
00:28:52,550 --> 00:28:54,700
Ako naglalakad papunta at
balik, balik,

874
00:28:54,700 --> 00:28:58,360
na kung saan ay tiyak na pagdagdag up
oras-matalino, at literal stepwise.

875
00:28:58,360 --> 00:29:00,660
>> Sort Insertion, sa unang
sulyap, kamukha ito

876
00:29:00,660 --> 00:29:05,150
sobrang mas matalinong, sa na lang ako
paggawa ng mabagal, incremental-unlad,

877
00:29:05,150 --> 00:29:07,120
ngunit hindi ako pagpunta ito papunta at pabalik.

878
00:29:07,120 --> 00:29:09,410
Ngunit kung ang isang tao ay sa katunayan
sa labas ng order, ang paunawa

879
00:29:09,410 --> 00:29:10,840
lahat ng mga trabaho ko lang ay nagkaroon na gawin.

880
00:29:10,840 --> 00:29:14,750
Nagkaroon na ako upang ilipat sa kalahati ng mga listahan
lamang na gumawa ng room para sa mga numero ng isa.

881
00:29:14,750 --> 00:29:16,790
Kaya ito ay ang parehong halaga
ng trabaho kaya malayo ito

882
00:29:16,790 --> 00:29:18,690
nararamdaman, lamang ng isang iba't ibang mga uri ng trabaho.

883
00:29:18,690 --> 00:29:19,370
>> Ituloy natin.

884
00:29:19,370 --> 00:29:22,657
Kaya ngayon ay alam namin na ang lahat
sa pagitan ng isa at walong ay nakaayos.

885
00:29:22,657 --> 00:29:23,740
Dito, ako ay may tatlong numero.

886
00:29:23,740 --> 00:29:25,864
Kung gusto mong i-pick up
numero ng tatlong, hakbang likod ng isa.

887
00:29:25,864 --> 00:29:28,260
At ano ang gagawin mo guys kailangan na gawin?

888
00:29:28,260 --> 00:29:28,760
Yep.

889
00:29:28,760 --> 00:29:33,070
Kaya na ang isa pang isa, dalawa, tatlong hakbang.

890
00:29:33,070 --> 00:29:36,010
Tatlong mga yunit ng oras na gastos lamang
sa akin, sa gayon ay tatlong ay maaari na ngayong magkasya.

891
00:29:36,010 --> 00:29:37,460
Sa wakas, pitong.

892
00:29:37,460 --> 00:29:39,730
>> Sabihin sige at mayroon
ikaw ay kumuha ng isang hakbang pabalik.

893
00:29:39,730 --> 00:29:42,780
Ito ay lamang ang pagpunta sa gastos sa amin
isang yunit ng oras, ngunit iyan ay OK.

894
00:29:42,780 --> 00:29:44,170
At ngayon, limang pupuntahan
maging isang maliit na mas mahal.

895
00:29:44,170 --> 00:29:45,340
Kung gusto mo sa hakbang pabalik.

896
00:29:45,340 --> 00:29:48,380
Kailangan namin upang ilipat walo,
at pitong, anim.

897
00:29:48,380 --> 00:29:50,749
At pagkatapos ang lahat ay inayos ngayon.

898
00:29:50,749 --> 00:29:52,290
Isang malaking kamay sa aming mga boluntaryo dito Kaya.

899
00:29:52,290 --> 00:29:53,554
Salamat sa iyo kaya magkano.

900
00:29:53,554 --> 00:29:56,220
>> [Palakpakan]

901
00:29:56,220 --> 00:29:56,860
>> Salamat sa lahat.

902
00:29:56,860 --> 00:29:57,520
Salamat sa lahat.

903
00:29:57,520 --> 00:30:02,940
Kaya tingnan natin ngayon kung paano lamang
magastos lahat ng iyon ay.

904
00:30:02,940 --> 00:30:06,210
Isaalang-alang natin marahil ang Ipaalam
pinakasimpleng ng mga, uri bubble.

905
00:30:06,210 --> 00:30:09,950
At sinasabi ko pinakasimpleng, dahil lamang
maaari mong malutas ito nang buong kasakiman sa pamamagitan lamang

906
00:30:09,950 --> 00:30:11,660
ayusin ang mga pairwise problema dito.

907
00:30:11,660 --> 00:30:13,720
Ayusin ang pairwise problema
dito, muli at muli

908
00:30:13,720 --> 00:30:17,680
at muli, paulit-ulit na bilang ng maraming
beses ng iyong aktwal na kailangan sa.

909
00:30:17,680 --> 00:30:21,050
>> Kaya ito ay lumiliko out na
may isang bubble sort, well,

910
00:30:21,050 --> 00:30:25,820
kung gaano karaming mga hakbang na kailangan kong gawin sa mga
ang unang pass ng algorithm na iyon?

911
00:30:25,820 --> 00:30:30,850
Baka ako take-- ni see-- isa ipaalam,
dalawa, tatlo, apat, lima, anim, pitong.

912
00:30:30,850 --> 00:30:32,190
At mayroong walong elemento dito.

913
00:30:32,190 --> 00:30:35,280
Kaya ito ay tulad n minus 1 na hakbang upang
makuha mula sa simula ng listahan

914
00:30:35,280 --> 00:30:36,380
sa dulo ng listahan.

915
00:30:36,380 --> 00:30:41,350
>> Ngunit sa pagpili ng uri, pagpapabalik na ako
piliing muli at muli ang mga elemento

916
00:30:41,350 --> 00:30:44,590
at muli na pinakamaliit,
Ako ng paglalagay ito sa lugar,

917
00:30:44,590 --> 00:30:46,616
ngunit pagkatapos ay hindi ako
naghahanap likod ako muli.

918
00:30:46,616 --> 00:30:49,490
Kaya tingin ko ito ay isang maliit na mas malinaw
pagkatapos na sa unang pagkakataon, maaari ko

919
00:30:49,490 --> 00:30:52,680
kailangang gawin ang lahat n minus 1 na hakbang
upang mahanap ang pinakamaliit na elemento.

920
00:30:52,680 --> 00:30:55,920
Pagkatapos ko bang ilagay ang mga ito sa lugar, at ako
paalisin ang sinumang ay dito dati.

921
00:30:55,920 --> 00:30:57,500
>> Ngunit pagkatapos ay hindi ko na kailangang
panatilihin ang pagtingin sa elementong ito,

922
00:30:57,500 --> 00:30:59,040
dahil alam ko ito ay
na ang pinakamaliit.

923
00:30:59,040 --> 00:31:01,581
Kaya ngayon, maaari kong tumingin sa loob lamang ng pitong
sangkap, at pagkatapos ng anim na mga sangkap,

924
00:31:01,581 --> 00:31:03,290
pagkatapos ng limang mga sangkap, at pagkatapos ng apat na mga sangkap.

925
00:31:03,290 --> 00:31:06,900
At kaya mathematically, kung n ay
ang bilang ng mga elemento o numero

926
00:31:06,900 --> 00:31:11,990
na namin na nagsimula sa, maaari mong isipin
na ito ay ang parehong bilang n minus 1,

927
00:31:11,990 --> 00:31:14,250
plus n minus 2 na hakbang,
plus n minus 3 hakbang na ito,

928
00:31:14,250 --> 00:31:16,780
plus n minus 4 na hakbang, ang lahat ng mga
paraan pababa sa isang hakbang lamang.

929
00:31:16,780 --> 00:31:18,160
At ako sa aking huling tao.

930
00:31:18,160 --> 00:31:20,650
>> At kung isipin mo na ang isang pulutong
ng stats ng mga libro o matematika libro

931
00:31:20,650 --> 00:31:24,730
magkaroon ng mga formula sa
Hardcover likod o sa harap ng mga ito,

932
00:31:24,730 --> 00:31:27,690
ito ay lumiliko out na ang seryeng ito
maaaring ipinahayag mas lamang

933
00:31:27,690 --> 00:31:28,857
bilang n beses n minus 1 sa higit sa 2.

934
00:31:28,857 --> 00:31:31,273
At ito ay multa kung hindi iyon
sa harapan ng iyong isip.

935
00:31:31,273 --> 00:31:32,420
Ngunit ito ay sa katunayan totoo.

936
00:31:32,420 --> 00:31:34,449
Iyan na lamang ng isang mas simpleng paraan ng pagsusulat ng mga ito.

937
00:31:34,449 --> 00:31:36,240
At pagkatapos ay kung sa tingin mo
bumalik sa mababang paaralan,

938
00:31:36,240 --> 00:31:38,698
kapag nagsimula ka lamang ng pagpaparami
out, ang mga bagay na ito ng mga kurso,

939
00:31:38,698 --> 00:31:41,820
ay lang n nakalapat minus n hinati sa 2.

940
00:31:41,820 --> 00:31:44,772
Lahat ng aking nagawa ay palawakin
ang expression doon.

941
00:31:44,772 --> 00:31:46,730
At ni sa pagsulat na muli ito upang ipaalam sa
isang maliit na naiiba.

942
00:31:46,730 --> 00:31:49,780
Iyan ay n squared hinati sa 2 minus n / 2.

943
00:31:49,780 --> 00:31:53,270
>> Kaya muli, ako lamang ang uri ng pag-aaplay
patakaran ng ilang arithmetic doon.

944
00:31:53,270 --> 00:31:57,140
Ngunit ngayon mapansin na ang mga pinakamalaking kataga
sa ganitong expression, kaya na magsalita,

945
00:31:57,140 --> 00:31:58,540
ay na n nakalapat.

946
00:31:58,540 --> 00:32:02,910
Kaya oo, ito ay n squared
hinati sa 2, minus n / 2.

947
00:32:02,910 --> 00:32:05,080
>> Ngunit sa pangkalahatan, kung ang n ay
magiging isang malaking halaga,

948
00:32:05,080 --> 00:32:08,740
Pupunta ako sa claim na n nakalapat
ay magiging ang nangingibabaw na kadahilanan.

949
00:32:08,740 --> 00:32:10,490
Lamang Ito ay pagpunta sa maging
isang mas malaking contributor

950
00:32:10,490 --> 00:32:12,877
sa bilang ng mga hakbang sa n / 2.

951
00:32:12,877 --> 00:32:13,960
Kaya kung ano ang ibig sabihin ako sa pamamagitan ng ito?

952
00:32:13,960 --> 00:32:16,795
Subukan ang isang simpleng halimbawa, kahit na
kahit na ang matematika ay makakakuha ng isang maliit na malaki.

953
00:32:16,795 --> 00:32:20,210
>> Kaya ipagpalagay namin ay 1 milyong mga tao
sa entablado, o 1 milyong mga bagay

954
00:32:20,210 --> 00:32:21,320
na gusto naming ayusin.

955
00:32:21,320 --> 00:32:23,730
Ni plug isang milyong Ipaalam
sa eksaktong na formula

956
00:32:23,730 --> 00:32:27,230
upang makita kung gaano karaming mga hakbang na aabutin pagiging
upang maipagsama-sama sa isang milyong mga elemento gamit sabihin,

957
00:32:27,230 --> 00:32:28,560
sort pagpili.

958
00:32:28,560 --> 00:32:30,760
>> Kaya gusto naming magkaroon ng parehong formula tulad ng dati.

959
00:32:30,760 --> 00:32:34,120
Gusto ko plug ng isang milyon, kaya na nakukuha ko
isang milyong squared hinati sa 2,

960
00:32:34,120 --> 00:32:35,990
minus isang milyon na hinati sa 2.

961
00:32:35,990 --> 00:32:40,180
Kung gagawin ko na math in advance
dito, mayroon kaming 500 bilyon

962
00:32:40,180 --> 00:32:47,460
minus 500,000, kung saan
ay nagbibigay sa amin 499,999,500,000,

963
00:32:47,460 --> 00:32:49,270
kung saan ay medyo darn malaki.

964
00:32:49,270 --> 00:32:54,370
>> Sa katunayan, kung ihahambing mo ngayon
499,000,000,000, 999 milyon,

965
00:32:54,370 --> 00:33:01,210
500,000 laban sa aming mga orihinal na halaga,
500 bilyong, ito ay kaya sumpain malapit.

966
00:33:01,210 --> 00:33:06,850
Right? n squared hinati sa 2 ay nagbibigay sa
us-- o sa halip, n squared hinati sa 2

967
00:33:06,850 --> 00:33:08,370
nagbigay sa amin ng 500 bilyon.

968
00:33:08,370 --> 00:33:13,510
Iyan ay medyo malapit darn
sa 499,999,500,000,

969
00:33:13,510 --> 00:33:17,970
na ang ibig sabihin ng pagbabawas off 500,000,
o sa mas pangkalahatang, pagbabawas off

970
00:33:17,970 --> 00:33:20,010
n nakalapat, hindi talagang isang malaking pakikitungo.

971
00:33:20,010 --> 00:33:22,490
N Ang nakalapat ang gumagawa ng mga
numero lumago talagang mabilis.

972
00:33:22,490 --> 00:33:25,790
>> Ngayon, ito ay mahalaga lamang insofar
bilang kami, bilang mga siyentipiko computer,

973
00:33:25,790 --> 00:33:29,350
ay karaniwang hindi pagpunta sa pag-aalaga kaya magkano
tungkol sa mga nuances ng mga formula

974
00:33:29,350 --> 00:33:31,400
at kung ano mismo ang
tumpak na mga sagot ay.

975
00:33:31,400 --> 00:33:33,390
Kami ay pag-aalaga na lang na, alam mo kung ano?

976
00:33:33,390 --> 00:33:37,810
Sa katapusan ng araw, ang formula na ito
ay sa order ng n nakalapat.

977
00:33:37,810 --> 00:33:39,350
>> Oo, kami ay naghahati sa pamamagitan ng 2 sa doon.

978
00:33:39,350 --> 00:33:41,360
Oo, kami ay pagbabawas off n minus 2.

979
00:33:41,360 --> 00:33:46,860
Ngunit sa pagtatapos ng araw, ang mga kataga
na talagang masakit sa amin at bayad sa amin

980
00:33:46,860 --> 00:33:48,995
isang pulutong ng mga hakbang ay na square term.

981
00:33:48,995 --> 00:33:51,370
At kaya kung ano ang isang computer scientist
ay pagpunta sa pangkalahatan ay gawin

982
00:33:51,370 --> 00:33:54,160
ay huwag pansinin ang lahat ng mga
mas maliit na mga tuntunin order,

983
00:33:54,160 --> 00:33:56,900
at tumingin lang sa isa na
nag-aambag sa mga pinaka sa mga gastos.

984
00:33:56,900 --> 00:34:00,530
>> At ito ay nice, dahil maaari naming
ngayong makipag-usap sa mas higit na panlahat

985
00:34:00,530 --> 00:34:02,470
tungkol sa mga algorithm, at maaaring ihambing ang mga ito.

986
00:34:02,470 --> 00:34:04,550
At ang katotohanan na ako
gamit na ito O ay sinadya.

987
00:34:04,550 --> 00:34:06,680
Kapag sinasabi ko sa pagkakasunud-sunod
ng, partikular na ako

988
00:34:06,680 --> 00:34:09,560
nagre-refer sa isang bagay
tinatawag na malaking O. At malaking O

989
00:34:09,560 --> 00:34:14,090
ay isang palatandaan na ang isang computer
ay gumagamit ng mga siyentipiko upang ilarawan

990
00:34:14,090 --> 00:34:16,710
isang itaas na nakatali sa isang bagay.

991
00:34:16,710 --> 00:34:21,150
>> Kaya kung sinasabi mo na ang isang algorithm
ay nasa malaking O ng n squared,

992
00:34:21,150 --> 00:34:23,380
bilang ipinanukalang ko lamang ng isang
ilang sandali ang nakalipas, ang ibig sabihin nito

993
00:34:23,380 --> 00:34:27,710
na sa mga tuntunin ng kanyang pagtakbo
oras o ang kanyang kahusayan,

994
00:34:27,710 --> 00:34:30,090
ito ay tumatagal sa pagkakasunud-sunod
ng n nakalapat na mga hakbang.

995
00:34:30,090 --> 00:34:31,420
Siguro higit pa, siguro ay mas mababa.

996
00:34:31,420 --> 00:34:33,435
Ngunit ito ay sa order ng n nakalapat.

997
00:34:33,435 --> 00:34:34,560
At iyan ang itaas na nakatali.

998
00:34:34,560 --> 00:34:36,530
Hindi na ito ay magiging
mas masakit kaysa sa na.

999
00:34:36,530 --> 00:34:40,800
Hindi ito ay magiging n nakakubo, o 2
sa n, o isang bagay na mas malaki.

1000
00:34:40,800 --> 00:34:43,800
Ito ay isang itaas na nakatali
sa kahit na ano na gastos ay.

1001
00:34:43,800 --> 00:34:46,150
Kaya ibinigay na, sabihin
isaalang-alang ang ilan sa mga halimbawa.

1002
00:34:46,150 --> 00:34:49,820
At ito ay lamang ng isang may hangganan listahan
ng napaka-pangkaraniwan ulit na tumatakbo

1003
00:34:49,820 --> 00:34:52,870
para sa mga algorithm na ay sinadya upang maging
nakapagpapakita ng ilang mga bagay na namin

1004
00:34:52,870 --> 00:34:53,600
nakita na.

1005
00:34:53,600 --> 00:34:58,060
>> Kaya halimbawa, sa kaso ng
pagpili ng uri, kung ano ako ng pagtubos dito

1006
00:34:58,060 --> 00:35:02,250
ay tumatakbo na ang uri ng pagpipilian
oras ay sa order ng n nakalapat.

1007
00:35:02,250 --> 00:35:06,260
Sa pinakamasama kaso, ako pagpunta sa may
isang buong grupo ng mga random na numero dito.

1008
00:35:06,260 --> 00:35:08,600
At tulad ng nakita natin mathematically,
kung ako panatilihin ang paglalakad

1009
00:35:08,600 --> 00:35:11,310
sa pamamagitan ng listahan, sa pamamagitan ng
list, ang pagpili sa susunod na pinakamaliit

1010
00:35:11,310 --> 00:35:14,410
muli at muli element, kung ako
talagang isulat ang lahat ng mga hakbang

1011
00:35:14,410 --> 00:35:18,750
Ako pagkuha bilang ipinanukalang ko formulaically
bago, ito ay sa order ng n squared

1012
00:35:18,750 --> 00:35:20,370
hakbang na aking iniinom.

1013
00:35:20,370 --> 00:35:24,520
>> At ito ay lumiliko out na ang bubble
uri-uriin at insertion sort

1014
00:35:24,520 --> 00:35:27,370
ay tulad ng mabagal na sa pinakamasama kaso.

1015
00:35:27,370 --> 00:35:32,040
Isaalang-alang, halimbawa, uri insertion,
sa huling algorithm namin dealt sa,

1016
00:35:32,040 --> 00:35:35,500
na kung saan ay nagkaroon sa amin tingnan ang element,
at pagkatapos ay ipasok ito kung saan ito kabilang.

1017
00:35:35,500 --> 00:35:38,720
At pagkatapos ay itinuturing namin ang susunod na sangkap,
at ipinasok na ito kung saan ito kabilang.

1018
00:35:38,720 --> 00:35:40,990
>> Kaya isaalang-alang ang pinakamahusay na posibleng sitwasyon.

1019
00:35:40,990 --> 00:35:45,590
Ipagpalagay aking volunteers ko ay pumila
literal na tulad nito, ang isa sa pamamagitan ng walong,

1020
00:35:45,590 --> 00:35:47,440
pinagsunod-sunod.

1021
00:35:47,440 --> 00:35:51,300
Gaano karaming mga hakbang ay uri insertion
pagpunta sa gawin upang ayusin walong tao,

1022
00:35:51,300 --> 00:35:55,640
kung dumating sila sa entablado
naghahanap tulad nito?

1023
00:35:55,640 --> 00:35:57,410
>> Eight mga tao na pinagsunod-sunod.

1024
00:35:57,410 --> 00:35:58,760
At gagamitin ko uuri.

1025
00:35:58,760 --> 00:36:02,180
Na huling ng algorithm.

1026
00:36:02,180 --> 00:36:03,640
Well, reenact ni tunay na mabilis ipaalam.

1027
00:36:03,640 --> 00:36:05,504
Kaya kung simulan ko dito, nakikita ko ang isa.

1028
00:36:05,504 --> 00:36:06,420
Saan ang isa ay pag-aari?

1029
00:36:06,420 --> 00:36:07,730
Ito ay nabibilang dito mismo.

1030
00:36:07,730 --> 00:36:08,330
Nakakakita ako ng dalawa.

1031
00:36:08,330 --> 00:36:09,660
Saan ang dalawang nabibilang?

1032
00:36:09,660 --> 00:36:10,260
Dito.

1033
00:36:10,260 --> 00:36:10,900
Nakakakita ako ng tatlo.

1034
00:36:10,900 --> 00:36:11,920
Saan ang tatlong nabibilang?

1035
00:36:11,920 --> 00:36:12,480
Dito.

1036
00:36:12,480 --> 00:36:13,100
>> Nakakakita ako ng apat.

1037
00:36:13,100 --> 00:36:13,600
Dito.

1038
00:36:13,600 --> 00:36:15,660
Five, anim, pitong, walong.

1039
00:36:15,660 --> 00:36:17,320
Walang dahilan upang ulitin ang aking sarili.

1040
00:36:17,320 --> 00:36:21,260
At kaya, kung gaano karaming mga hakbang
ay na sa mga tuntunin ng n?

1041
00:36:21,260 --> 00:36:23,870
Ito ay sa order ng n
hakbang na ito, i-right? n minus 1.

1042
00:36:23,870 --> 00:36:27,567
Ngunit kinuha ko ang isang guhit number
ng mga hakbang, at ngayon ako tapos na.

1043
00:36:27,567 --> 00:36:28,900
Kaya iyon ang pinakamahusay na kaso, bagaman.

1044
00:36:28,900 --> 00:36:29,983
Ano ang tungkol sa pinakamasama kaso?

1045
00:36:29,983 --> 00:36:32,730
Ano walong ay banda roon,
at pitong ay down doon,

1046
00:36:32,730 --> 00:36:35,840
at isa at dalawa ay sa paglipas dito, para
na ang listahan ay tunay na baligtad?

1047
00:36:35,840 --> 00:36:38,300
>> Well, kung ano ang mangyayari sa katunayan
kung ito ang number?

1048
00:36:38,300 --> 00:36:41,300
At kami na ang lamang ng isang pares ng mga halimbawa.

1049
00:36:41,300 --> 00:36:49,300
Paano kung, sa katunayan, ang bilang ng walong
ay dito, at ang mga number-- Oops.

1050
00:36:49,300 --> 00:36:52,660

1051
00:36:52,660 --> 00:36:56,430
Kaya kung ano kung, sa katunayan, ang bilang
walong ay ang lahat ng paraan sa paglipas dito,

1052
00:36:56,430 --> 00:36:57,790
at gumagamit ako ng uri pagpapasok?

1053
00:36:57,790 --> 00:36:58,290
>> SIGE.

1054
00:36:58,290 --> 00:37:00,280
Inaangkin ko sa sandaling ito ay sa lugar.

1055
00:37:00,280 --> 00:37:03,152
Ngunit ngayon, seven-- kung saan ay pitong pumunta?

1056
00:37:03,152 --> 00:37:04,360
Siyempre, ito ay pumunta sa paglipas dito.

1057
00:37:04,360 --> 00:37:06,760
Kaya ko bang ilipat ang walong higit sa isang lugar.

1058
00:37:06,760 --> 00:37:08,554
Ngayon, anim, kung saan ito pumunta?

1059
00:37:08,554 --> 00:37:09,220
Well, ang lahat ng karapatan.

1060
00:37:09,220 --> 00:37:13,150
Ngayon, mayroon akong upang ilipat walong higit sa
isang lugar, at pitong higit sa isang lugar,

1061
00:37:13,150 --> 00:37:14,440
at pagkatapos ay gumawa ng mapa ko pababa anim.

1062
00:37:14,440 --> 00:37:16,870
>> Kaya sa unang pagkakataon, cost ito
sa akin sa isang hakbang upang ayusin ang mga bagay-bagay,

1063
00:37:16,870 --> 00:37:18,570
pagkatapos ay ang halaga sa akin ang dalawang mga hakbang upang ayusin ang mga bagay.

1064
00:37:18,570 --> 00:37:20,370
Ilang hakbang ito
pagpunta sa gawin upang ayusin

1065
00:37:20,370 --> 00:37:22,720
bagay ilagay ang lima ay nasa tamang lugar?

1066
00:37:22,720 --> 00:37:23,340
Three.

1067
00:37:23,340 --> 00:37:29,520
Dahil ngayon ko bang
ilipat ang isa, dalawa, tatlo.

1068
00:37:29,520 --> 00:37:32,430
Ilang hakbang ito sa pagpunta sa tumagal
upang ilagay ang apat na nasa tamang lugar?

1069
00:37:32,430 --> 00:37:36,040
4 plus 5, plus 6, plus 7.

1070
00:37:36,040 --> 00:37:40,260
>> At kaya ito ay mathematically magkapareho sa
kung ano ang namin na inilarawan para sa pagpili-uuri.

1071
00:37:40,260 --> 00:37:42,130
Mayroon kaming mga seryeng ito
na lang ang pagtaas.

1072
00:37:42,130 --> 00:37:45,650
1 plus 2 plus 3 plus 4,
o pasalungat, 7 plus 6

1073
00:37:45,650 --> 00:37:52,610
plus 5 plus 4 nagdadagdag up para ngayong araw
mga layunin na sa order ng n nakalapat.

1074
00:37:52,610 --> 00:37:57,640
>> Kaya hayaan mo akong magtadhana masyadong na
bubble sort ay din sa n nakalapat.

1075
00:37:57,640 --> 00:38:01,340
Dahil sa uri bubble, ang bawat isa
oras na pumunta ko sa pamamagitan ng mga listahan,

1076
00:38:01,340 --> 00:38:03,100
Ako paglalaan ng humigit-kumulang kung gaano karaming mga hakbang na ito?

1077
00:38:03,100 --> 00:38:06,260
Sa bawat oras na ako ay literal
lakad mula doon sa doon?

1078
00:38:06,260 --> 00:38:07,960
Sa pahapyaw n hakbang.

1079
00:38:07,960 --> 00:38:12,650
Ngunit kung gaano karaming beses maaaring ako
kailangan upang pumunta sa pamamagitan ng listahan?

1080
00:38:12,650 --> 00:38:13,920
>> Well, halos n oras.

1081
00:38:13,920 --> 00:38:15,680
Siguro n minus 1, ngunit humigit-kumulang n ulit.

1082
00:38:15,680 --> 00:38:16,430
Well, kung bakit ay na?

1083
00:38:16,430 --> 00:38:19,560
Well, na may bubble sort, kung
namin magsimula sa bubble uri,

1084
00:38:19,560 --> 00:38:23,570
may listahan sa pinakamasama posibleng
sitwasyon, na muli ay ganap na

1085
00:38:23,570 --> 00:38:25,550
paurong, kung ano ang nangyayari sa mangyayari?

1086
00:38:25,550 --> 00:38:28,830
Pumunta ako sa pamamagitan ng listahan, at numero
nabibilang sa isa ang lahat ng paraan sa banda roon.

1087
00:38:28,830 --> 00:38:33,280
>> Ngunit sa bubble sort, gaano kalayo ang ginagawa ng isa
ilipat sa aking unang pass sa pamamagitan ng listahan?

1088
00:38:33,280 --> 00:38:36,620
Gaano karaming mga spot ay siya makakuha ng
mas malapit sa tamang lugar?

1089
00:38:36,620 --> 00:38:37,240
Isa lamang.

1090
00:38:37,240 --> 00:38:40,281
Kaya't kung ikaw uri ng dahilan sa pamamagitan na ito,
sa bawat oras sa pamamagitan ng algorithm na ito,

1091
00:38:40,281 --> 00:38:41,880
Pagkuha ng humigit-kumulang n hakbang na si David.

1092
00:38:41,880 --> 00:38:44,940
Ngunit kung gaano karaming mga pumasa
sa pamamagitan ng listahan ay ito

1093
00:38:44,940 --> 00:38:49,060
pagpunta sa gawin para sa isa sa bubble
sa kaliwa kung saan-aari?

1094
00:38:49,060 --> 00:38:51,840
>> Siya ay nakuha upang ilipat tulad,
n puwang sa ganitong paraan.

1095
00:38:51,840 --> 00:38:57,960
Kaya upang gawin lamang ang pagbubukod-bukod ng mga listahan,
Kailangan kong maglakad papunta at pabalik n ulit.

1096
00:38:57,960 --> 00:39:01,540
At sa bawat oras, ako
naghahanap sa n elemento.

1097
00:39:01,540 --> 00:39:05,410
Kaya gawin n bagay n beses sa
ang order ng n nakalapat.

1098
00:39:05,410 --> 00:39:07,220
>> Ngayon, kami ay makita sa ilang
ng shorts na

1099
00:39:07,220 --> 00:39:10,440
naka-embed sa susunod na problema CS50
set, isa pang diskarte sa mga ito,

1100
00:39:10,440 --> 00:39:13,490
ngunit sa ngayon, hayaan ang isaalang-alang lamang
ilang iba pang mga oras ng pagpapatakbo,

1101
00:39:13,490 --> 00:39:16,840
lalo na kung ang pag-uuri na mga tumagal
isang maliit na piraso ng oras sa lababo.

1102
00:39:16,840 --> 00:39:21,790
Ano ang isang algorithm na nakita namin na
na tumatagal sa order ng n hakbang?

1103
00:39:21,790 --> 00:39:27,560
>> Ano ang dapat gawin ng isang guhit number
ng mga hakbang na namin nakita kaya ngayon?

1104
00:39:27,560 --> 00:39:29,350
Ano yan?

1105
00:39:29,350 --> 00:39:30,480
Ang paghahanap na direktoryo ng telepono.

1106
00:39:30,480 --> 00:39:31,390
Ang unang algorithm.

1107
00:39:31,390 --> 00:39:31,560
Right?

1108
00:39:31,560 --> 00:39:33,650
Saan hindi namin linearly
naghahanap para sa Mike Smith?

1109
00:39:33,650 --> 00:39:34,150
Sa katunayan.

1110
00:39:34,150 --> 00:39:37,180
Mula week zero, kapag sinimulan ko
paggawa sa isang pahina sa isang oras,

1111
00:39:37,180 --> 00:39:40,095
at kahit na sinabi ko na ito ay uri
ng isang pakiramdam linear algorithm,

1112
00:39:40,095 --> 00:39:42,720
at nagkaroon kami na larawan sa
board na may tuwid pulang linya

1113
00:39:42,720 --> 00:39:44,678
at ang mga straight dilaw
line, ang mga iyon ay sa katunayan

1114
00:39:44,678 --> 00:39:46,810
algorithm na sa malaking O ng n.

1115
00:39:46,810 --> 00:39:50,680
>> Dahil upang mahanap Mike Smith sa isang telepono
aklat ng n pahina, sa pinakamasama kaso,

1116
00:39:50,680 --> 00:39:52,422
maaring tumagal ako n hakbang.

1117
00:39:52,422 --> 00:39:53,630
Paano ang tungkol sa pagkuha ng pagdalo?

1118
00:39:53,630 --> 00:39:55,790
Isa dalawa tatlo apat lima anim.

1119
00:39:55,790 --> 00:39:59,420
Ano ang oras ng paggana ng mga ito
algorithm para sa pagkuha ng pagdalo?

1120
00:39:59,420 --> 00:40:03,070
Big O ng n, dahil sa theory ko
kung ituro sa lahat ng tao sa kuwarto.

1121
00:40:03,070 --> 00:40:05,861
>> Ngayon bilang isang bukod, ano ang tungkol sa
iba pang mga optimization mula sa linggo zero?

1122
00:40:05,861 --> 00:40:08,117
Dalawa, apat, anim, walo, 10, 12.

1123
00:40:08,117 --> 00:40:10,200
Ang isang computer scientist gagawin
mapagtanto, maghintay ng isang minuto,

1124
00:40:10,200 --> 00:40:12,320
na sa order ng
n hinati sa dalawang hakbang.

1125
00:40:12,320 --> 00:40:12,820
Right?

1126
00:40:12,820 --> 00:40:14,444
Dahil ako ng paggawa ng dalawang tao sa isang pagkakataon.

1127
00:40:14,444 --> 00:40:17,015
Ngunit kami ay pagpunta upang huwag pansinin
mga mas mababang mga tuntunin order,

1128
00:40:17,015 --> 00:40:19,140
at kami ay lamang ng pagpunta sa
itapon ang hatiin sa pamamagitan ng 2,

1129
00:40:19,140 --> 00:40:21,830
at sabihin lamang, malaking O ng n
para na algorithm rin.

1130
00:40:21,830 --> 00:40:22,760
>> Ano ang tungkol sa isang ito?

1131
00:40:22,760 --> 00:40:26,170
Makikita laktawan kaming mahigit sa ilan sa mga ito, ngunit kung ano
ay isang algorithm na iyon ay mag-log ng n?

1132
00:40:26,170 --> 00:40:29,900
Na kinuha halos log n hakbang?

1133
00:40:29,900 --> 00:40:30,870
Ang hatiin at lupigin.

1134
00:40:30,870 --> 00:40:31,369
Mismong.

1135
00:40:31,369 --> 00:40:33,900
Tulad ng sa halimbawa sa aklat ng telepono sa
week zero at mas maaga sa araw,

1136
00:40:33,900 --> 00:40:36,191
kung saan hinati namin ang problema
at muli at muli.

1137
00:40:36,191 --> 00:40:39,070
Drew namin ito sa board sa week
zero bilang hubog berdeng linya,

1138
00:40:39,070 --> 00:40:41,460
at sinabi namin sa araw na iyon, ito ay
isang logarithmic algorithm.

1139
00:40:41,460 --> 00:40:44,970
>> At sa katunayan, ang bilang ng mga hakbang na ito
ang kinakailangan upang maisagawa ang hatiin at lupigin,

1140
00:40:44,970 --> 00:40:48,610
o binary paghahanap bilang magsisimula kami
pagtawag na ito, tulad ng sa aklat ng telepono,

1141
00:40:48,610 --> 00:40:50,680
ay sa pagkakasunud-sunod ng mga mag-log at mga hakbang.

1142
00:40:50,680 --> 00:40:52,470
At ito ay isang piraso ng isang isa kakaiba.

1143
00:40:52,470 --> 00:40:54,910
>> Ano ang tumatagal ng isang hakbang,
o mas partikular na

1144
00:40:54,910 --> 00:40:56,240
ang tapat na bilang ng mga hakbang na ito?

1145
00:40:56,240 --> 00:40:58,865
Siguro ay dalawang, marahil ito ay tatlo,
ngunit isang computer scientist na lang

1146
00:40:58,865 --> 00:41:01,423
Pinadadali ito bilang malaking O ng 1,
ilang mga tapat na bilang ng mga hakbang.

1147
00:41:01,423 --> 00:41:04,256
Ano ang isang bagay na maaari mong gawin na
tumatagal ng isang pare-pareho ang bilang ng mga hakbang na ito?

1148
00:41:04,256 --> 00:41:08,030

1149
00:41:08,030 --> 00:41:10,930
>> Ano ang oras ng paggana ng pumapalakpak?

1150
00:41:10,930 --> 00:41:11,920
Pare-pareho ang panahon.

1151
00:41:11,920 --> 00:41:12,420
Right?

1152
00:41:12,420 --> 00:41:15,490
Tulad ng, kung ano ang ang oras ng paggana ng
paggawa ng anumang bagay na tumatagal lamang ng isa

1153
00:41:15,490 --> 00:41:18,570
operasyon, tulad ng i-print F Hello World.

1154
00:41:18,570 --> 00:41:24,110
Iyon ay maaaring maging sinabi na pare-pareho ang oras,
maliban na lamang kung mas mababa sulok kaso may print F,

1155
00:41:24,110 --> 00:41:28,260
kung ano ang maaaring ang oras na tumatakbo
ng print F tunay na maging?

1156
00:41:28,260 --> 00:41:28,790
At bakit?

1157
00:41:28,790 --> 00:41:30,550
Anong n pagsukat sa kasong iyon?

1158
00:41:30,550 --> 00:41:32,251
>> Madla: [hindi marinig].

1159
00:41:32,251 --> 00:41:33,250
David J. MALAN: Eksakto.

1160
00:41:33,250 --> 00:41:34,900
Ang bilang ng mga character
gusto naming i-print.

1161
00:41:34,900 --> 00:41:36,191
Kaya napaka context-sensitive.

1162
00:41:36,191 --> 00:41:39,910
Ngayon, kami ay nagbibigay-diin sa isang pulutong sa
mga titik at numero dito sa board.

1163
00:41:39,910 --> 00:41:43,540
Ngunit maaari din itong maging
character sa isang aktwal na string.

1164
00:41:43,540 --> 00:41:46,420
Kaya ito ay lumiliko out may isa pang
Ang panukalang-batas na ay magsisimula sa pag-aalaga tungkol sa,

1165
00:41:46,420 --> 00:41:48,530
at iyon ang kabaligtaran
ng malaking O, kaya na magsalita.

1166
00:41:48,530 --> 00:41:50,120
>> Iyon ang wakas notation.

1167
00:41:50,120 --> 00:41:53,380
Sapagkat malaking O ay nangangahulugan kung ano ang, ang
itaas na nakatali sa iyong tumatakbo oras?

1168
00:41:53,380 --> 00:41:55,580
Maximally, kung gaano karaming oras
Maaaring ang isang bagay tumagal?

1169
00:41:55,580 --> 00:41:59,250
Omega-- paumanhin mapigil ito darating
up-- ay ang kabaligtaran ng iyon,

1170
00:41:59,250 --> 00:42:02,960
kung saan ito ay isang mas mababang nakatali sa
halaga ng oras ng isang bagay na maaaring gawin.

1171
00:42:02,960 --> 00:42:10,480
>> So. halimbawa, kung ano ang isang algorithm
na tumatagal laging n nakalapat hakbang?

1172
00:42:10,480 --> 00:42:15,600
Well, isa sa mga algorithm na namin nakita
ngayon, sa katunayan, ay maaaring maging pati na rin na iyon.

1173
00:42:15,600 --> 00:42:16,720
Selection sort.

1174
00:42:16,720 --> 00:42:18,270
Pinili uri ay medyo tanga.

1175
00:42:18,270 --> 00:42:21,760
Kahit na kung ang algorithm-- paumanhin, kahit na
kung ang array na pinagsunod-sunod,

1176
00:42:21,760 --> 00:42:24,150
pagpili-uuri ay pagpunta sa
panatilihin ang paglalakad sa pamamagitan ng listahan

1177
00:42:24,150 --> 00:42:28,907
upang tiyakin na ito ay ang pinakamaliit na
element at muli at muli.

1178
00:42:28,907 --> 00:42:31,740
At kahit na iyong mga kawani na tao sa
alam ng madla na, maghintay ng isang minuto,

1179
00:42:31,740 --> 00:42:33,948
ikaw ay nakapasa sa
pinakamaliit na elemento, ang computer

1180
00:42:33,948 --> 00:42:37,300
ay hindi alam na hanggang sa ito hitsura
lahat ng mga paraan sa pamamagitan ng mga listahan.

1181
00:42:37,300 --> 00:42:40,240
Katulad nito, ang isang mas mababang nakatali na
Maaari din ay dadalhin sa account

1182
00:42:40,240 --> 00:42:42,000
ito ay maaaring maging sa haba ng panahon.

1183
00:42:42,000 --> 00:42:48,260
>> Gaano karaming oras ang hihintayin upang
uri n elemento sa pinakamahusay na

1184
00:42:48,260 --> 00:42:52,420
kaso gamit ang isang bagay tulad ng bubble uri?

1185
00:42:52,420 --> 00:42:54,280
Ipagpalagay na ang iyong listahan ay pinagsunod-sunod.

1186
00:42:54,280 --> 00:42:56,696
Sabi namin tumatagal sa bubble sort
ang order ng n nakalapat na mga hakbang.

1187
00:42:56,696 --> 00:42:59,640
Ngunit ano kung na-pinagsunod-sunod?

1188
00:42:59,640 --> 00:43:02,310
Paano kung nauunawaan mo pagkatapos ng
isa pumasa sa pamamagitan ng array

1189
00:43:02,310 --> 00:43:03,540
na iyong ginawa walang swaps?

1190
00:43:03,540 --> 00:43:05,970
Kailangan mo bang panatilihin ang paggawa ng mas maraming passes?

1191
00:43:05,970 --> 00:43:06,470
>> Hindi.

1192
00:43:06,470 --> 00:43:10,340
Kaya ang isang mas mababang nakatali sa bubble sort
Maaaring maging sinabi na linear.

1193
00:43:10,340 --> 00:43:11,830
Omega ng n.

1194
00:43:11,830 --> 00:43:14,450
At maaari naming tumingin sa
iba sa mga ito pati na rin.

1195
00:43:14,450 --> 00:43:17,990
Kaya sabihin kumuha ng isang mabilis na pagtingin
sa loob lamang ng visualization dito

1196
00:43:17,990 --> 00:43:20,790
upang makita kung paano ang mga ito na makilala ang kanilang mga sarili.

1197
00:43:20,790 --> 00:43:24,592
Pupunta ako sa bumaba dito sa ito
pahina na magagamit sa website C50 ni,

1198
00:43:24,592 --> 00:43:27,550
ngunit ito ay isang sakit upang makakuha ng trabaho,
dahil ito ay gumagamit ng isang teknolohiya na tinatawag na

1199
00:43:27,550 --> 00:43:30,560
Applets Java, kung saan ay isang
higit sa lahat hindi suportadong mga araw,

1200
00:43:30,560 --> 00:43:32,730
hindi bababa sa pamamagitan ng Chrome at ilang iba.

1201
00:43:32,730 --> 00:43:37,070
>> At hayaan mo akong magpatuloy at bilis na ito
up at ipaliwanag kung ano ang nangyayari sa.

1202
00:43:37,070 --> 00:43:40,840
Ito ay isang pagpapakita ng bubble
uri, ang unang algorithm itinuturing namin.

1203
00:43:40,840 --> 00:43:43,950
At ito ay isang paggunita sa na ang bawat
sa mga bar ay kumakatawan sa isang numero.

1204
00:43:43,950 --> 00:43:45,710
Mas malaking bar,
ang mas malaki ang bilang.

1205
00:43:45,710 --> 00:43:47,520
Ang mas maliit na bar,
ang mas maliit na ang numero.

1206
00:43:47,520 --> 00:43:50,353
At kung ano ang maaari mong makita ang biswal, kahit
kahit na ito ay pagpunta napakabilis,

1207
00:43:50,353 --> 00:43:53,699
ay na ang mga pulang bar ay tulad ng sa akin,
paglalakad papunta at pabalik sa pag-aayos ng mga problema.

1208
00:43:53,699 --> 00:43:56,740
Maaari mong makita na ang mga mas malaking mga elemento
sa katunayan ay bumabalong sa kanan,

1209
00:43:56,740 --> 00:43:59,650
at ang mas maliit na mga elemento
ay bumabalong sa kaliwa.

1210
00:43:59,650 --> 00:44:01,870
And pababa dito, kung kami
talagang pagmasdan,

1211
00:44:01,870 --> 00:44:04,330
maaari naming aktwal na bilangin ang
bilang ng mga paghahambing at swaps

1212
00:44:04,330 --> 00:44:05,350
na na na ginawa.

1213
00:44:05,350 --> 00:44:07,360
>> Ngunit sa halip, tingnan natin hayaan
sa ikalawang algorithm

1214
00:44:07,360 --> 00:44:11,240
kami ay tumingin sa mas maaga sa aming
boluntaryo, pagpili-uuri.

1215
00:44:11,240 --> 00:44:13,500
Biswal, ito ay may
ibang-iba ng epekto.

1216
00:44:13,500 --> 00:44:16,820
Ngunit ito ay, muli, napaka-intuitive, sa
na panatilihin namin ang pagpili sa susunod na pinakamaliit

1217
00:44:16,820 --> 00:44:18,660
sangkap, at nakuha namin ang isang maliit na mapalad.

1218
00:44:18,660 --> 00:44:20,110
Na nadama panimula mas mabilis.

1219
00:44:20,110 --> 00:44:22,840
Ngunit kung namin tumakbo muli at muli ito
at muli may maraming ng input,

1220
00:44:22,840 --> 00:44:26,680
Gusto naming makita na ito ay sa katunayan
pa rin sa malaking O ng n squared.

1221
00:44:26,680 --> 00:44:29,920
>> Gawin ang isa huling isa Ipaalam
dito, uuri,

1222
00:44:29,920 --> 00:44:33,180
na kung saan ay ang ikatlong algorithm
kami ay tumingin sa, at pagpapabalik

1223
00:44:33,180 --> 00:44:36,700
na ang isang ito ang trato sa mga
mga elemento tulad ng ito ay nakatagpo ng mga ito,

1224
00:44:36,700 --> 00:44:39,290
ngunit pagkatapos ay ito marahil nagbabago
mga bagay na higit na gumawa ng room,

1225
00:44:39,290 --> 00:44:41,660
pagpasok elemento kung saan nabibilang sila.

1226
00:44:41,660 --> 00:44:45,330
>> At ito masyadong nagtatapos up pagbibigay ng
huling resulta. Ngayon ang lahat ng tatlong mga

1227
00:44:45,330 --> 00:44:46,490
nadama medyo mabilis.

1228
00:44:46,490 --> 00:44:48,740
At sa katunayan, ako ang bumangga sa kanila
sa isang medyo magandang clip.

1229
00:44:48,740 --> 00:44:52,510
Ngunit sa panimula, ang mga ito ang lahat ng
medyo kakila-kilabot, na maging matapat.

1230
00:44:52,510 --> 00:44:56,960
Lahat ng mga algorithm kaya sa ngayon
na tumakbo sa malaking O ng n squared

1231
00:44:56,960 --> 00:44:59,270
kumuha pa ng kaunting
ng panahon upang tumakbo sa dulo.

1232
00:44:59,270 --> 00:45:01,920
>> At sa katunayan, maaari naming makita
at pakiramdam na ito bilang wakas

1233
00:45:01,920 --> 00:45:04,090
kung pull up ko ito ikatlong at huling demo.

1234
00:45:04,090 --> 00:45:05,840
Ito ay isa pang
visualization na pupuntahan

1235
00:45:05,840 --> 00:45:08,500
upang ipakita ang bubble sort sa kaliwa,
sort pagpipilian sa gitna,

1236
00:45:08,500 --> 00:45:13,410
at isang bagay, tulad ng isa sa aming mga
kamay iaangat mas maaga iminungkahi,

1237
00:45:13,410 --> 00:45:15,020
sumanib uri sa kanan.

1238
00:45:15,020 --> 00:45:16,937
A hatiin at lupigin
diskarte sa kanan.

1239
00:45:16,937 --> 00:45:19,520
At na, sa katunayan, kung ano ang hindi namin
pagpunta sa tumingin sa sa Miyerkules.

1240
00:45:19,520 --> 00:45:21,990
Ngunit oras na ito na tumakbo sa parallel ipaalam.

1241
00:45:21,990 --> 00:45:26,765
Ito ay humigit-kumulang ang parehong bilang ng mga
mga elemento, ang lahat ng tumatakbo sa parehong oras.

1242
00:45:26,765 --> 00:45:30,940

1243
00:45:30,940 --> 00:45:34,440
Bubble uri vs seleksyon
sort vs pagsasama-uuri.

1244
00:45:34,440 --> 00:45:36,760
>> Ngayon, ang lahat ng mga ito ay tumatakbo
sa teorya at sa parehong oras.

1245
00:45:36,760 --> 00:45:39,830
Ang CPU ay tumatakbo sa
sa parehong bilis, ngunit ikaw

1246
00:45:39,830 --> 00:45:44,014
Maaari pakiramdam kung paano panganganak na ito ay
masyadong mabilis ang pagpunta sa maging,

1247
00:45:44,014 --> 00:45:45,930
at lamang kung gaano kabilis kapag
mag-iniksyon kami ng kaunting week

1248
00:45:45,930 --> 00:45:49,330
algorithms zero ni maaari
pabilisin namin ang mga bagay up.

1249
00:45:49,330 --> 00:45:51,760
>> At ni ihambing ngayon hayaan
ang mga ito sa isa sa huling form.

1250
00:45:51,760 --> 00:45:55,710
Pupunta ako sa sige
sa website CS50, kung saan

1251
00:45:55,710 --> 00:45:59,020
taglay namin ang pangwakas na link para sa araw na ito,
kung saan ang isang tao sa internet

1252
00:45:59,020 --> 00:46:03,960
mabait magkasama sa isang video na
kinukuha kung ano ang iba't ibang mga pag-uuri

1253
00:46:03,960 --> 00:46:07,510
algorithms tunog tulad ng.

1254
00:46:07,510 --> 00:46:09,577
Ito ay uri insertion.

1255
00:46:09,577 --> 00:46:12,072
>> [Beep]

1256
00:46:12,072 --> 00:46:13,070

1257
00:46:13,070 --> 00:46:16,850
>> Kung saan ka nag-aaplay ng isang dalas
batay sa taas ng bar bar.

1258
00:46:16,850 --> 00:46:19,826
Ito ang bubble sort.

1259
00:46:19,826 --> 00:46:21,822
>> [Bingkong beep]

1260
00:46:21,822 --> 00:46:33,299

1261
00:46:33,299 --> 00:46:45,774
>> Pagdating up sa susunod is-- darating
up susunod is-- pagpili ng uri,

1262
00:46:45,774 --> 00:46:48,820
kung saan muli, kami ay pagpili
sa susunod na pinakamaliit na sangkap,

1263
00:46:48,820 --> 00:46:51,820
at maaari naming makita ang mga ito lumalaki
mula kaliwa papuntang kanan.

1264
00:46:51,820 --> 00:47:01,120

1265
00:47:01,120 --> 00:47:04,000
>> Pagsamahin ang mga uri, ang aming winner kaya ngayon ngayon.

1266
00:47:04,000 --> 00:47:09,659

1267
00:47:09,659 --> 00:47:12,450
Pansinin kung paano ito ay naghahati bagay
sa [hindi marinig] kalahati at tirahan.

1268
00:47:12,450 --> 00:47:17,510

1269
00:47:17,510 --> 00:47:21,660
Gnome uri, na kung saan mayroon kaming hindi
usapan tungkol sa, at lumilikha ng biswal

1270
00:47:21,660 --> 00:47:24,450
at audally isang piraso ng isang
iba't-ibang hugis at tunog.

1271
00:47:24,450 --> 00:47:27,060

1272
00:47:27,060 --> 00:47:30,160
Pagpunta papunta at pabalik,
paglilinis ng mga bagay up.

1273
00:47:30,160 --> 00:47:32,230
Suriin din ang heapsort
sa website na ito tao.

1274
00:47:32,230 --> 00:47:36,100

1275
00:47:36,100 --> 00:47:36,810
>> At na ito.

1276
00:47:36,810 --> 00:47:38,210
Kami ay makita mo ang susunod na oras.

1277
00:47:38,210 --> 00:47:42,647

1278
00:47:42,647 --> 00:47:48,334
>> [Whooshing AND MUSIC]

1279
00:47:48,334 --> 00:50:24,839