1
00:00:00,000 --> 00:00:11,100
>> [Nagpe-play ng musika]

2
00:00:11,100 --> 00:00:11,490
>> David J. MALAN: Lahat ng karapatan.

3
00:00:11,490 --> 00:00:12,170
Kaya maligayang pagdating pabalik.

4
00:00:12,170 --> 00:00:15,180
Ito ay CS50, at ang ay
ang katapusan ng linggo tatlong.

5
00:00:15,180 --> 00:00:17,770
>> Kaya isipin ang sa nakalipas na ilang linggo,
kami gumagastos pa ng kaunting

6
00:00:17,770 --> 00:00:20,820
oras sa C, sa programming, sa syntax.

7
00:00:20,820 --> 00:00:24,680
At ito ay lubos na normal, kung hindi mo pa rin
struggling na may Problema Set 2, na maging

8
00:00:24,680 --> 00:00:25,950
banging iyong ulo laban sa mga pader.

9
00:00:25,950 --> 00:00:28,310
Ito ay misteriyoso-mukhang error na mensahe
at mga bug sa iyo na

10
00:00:28,310 --> 00:00:29,220
Hindi maaaring medyo Chase down.

11
00:00:29,220 --> 00:00:32,310
Dahil, magpahinga panatag, na sa loob lamang ng
ilang linggo 'oras makakakita ka tumingin pabalik sa

12
00:00:32,310 --> 00:00:35,930
mga bagay tulad ng Caesar, at [? V-genair,?]
siguro ay maging lamat, at

13
00:00:35,930 --> 00:00:40,050
Napagtanto lang gaano kalayo mo na dumating
sa isang maikling panahon.

14
00:00:40,050 --> 00:00:43,670
Kaya kung iyon ang anumang aliw,
hang sa doon sa ngayon.

15
00:00:43,670 --> 00:00:46,610
>> Ngayon, bagaman, magsisimula kami sa transition
sa mga bagay na mas mataas na antas.

16
00:00:46,610 --> 00:00:49,820
At simulan namin upang mang-ahas na
ka guys malaman kung paano i-program, o sa

17
00:00:49,820 --> 00:00:52,090
hindi bababa ang Beginnings ng
kaginhawahan na antas.

18
00:00:52,090 --> 00:00:56,520
At magsisimula kami upang isaalang-alang kung paano aming makakaya
pumunta tungkol sa pagdisenyo ng mga programa nang higit pa

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

20
00:00:57,440 --> 00:01:01,090
Paano namin pumunta tungkol sa pag-optimize ang
kahusayan ng aming mga algorithm, at

21
00:01:01,090 --> 00:01:03,110
pangkalahatan paglutas nang higit pa
kagiliw-giliw na mga problema.

22
00:01:03,110 --> 00:01:06,850
At nagsisimula na kumuha para sa ipinagkaloob na,
kung gusto naming, maaari naming code up anumang

23
00:01:06,850 --> 00:01:08,350
ng mga halimbawa sa kami ay may sa isip.

24
00:01:08,350 --> 00:01:11,430
Kaya ngayon, hindi kami pindutin ang keyboard
para sa anumang paraan ng code.

25
00:01:11,430 --> 00:01:15,150
Ito ay mas mataas na antas, at
sa huli, tungkol sa problema-tuos.

26
00:01:15,150 --> 00:01:20,490
>> Kaya upang makakuha ng sa puntong iyon, hayaan mo akong magpanukala
na ang mga sumusunod na pitong

27
00:01:20,490 --> 00:01:24,290
parihaba para kumatawan sa pitong pintuan, sa likod ng
na kung saan ay ang maramihang mga

28
00:01:24,290 --> 00:01:26,340
mga numero, bukod sa kung saan ay ang numero 50.

29
00:01:26,340 --> 00:01:30,470
Hayaan akong proyekto na ito sa ito
screen dito pati na rin.

30
00:01:30,470 --> 00:01:36,770
At ipanukala na kailangan namin ng isang volunteer sa
makatulong sa akin mahanap ang isang numero sa harap ng

31
00:01:36,770 --> 00:01:38,140
ang internet dito upang makita.

32
00:01:38,140 --> 00:01:40,755
Halika sa up, nakahubad.

33
00:01:40,755 --> 00:01:43,050
Ayos lang.

34
00:01:43,050 --> 00:01:43,930
Ano ang inyong pangalan?

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

36
00:01:44,850 --> 00:01:45,170
>> David J. MALAN: Paumanhin?

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

38
00:01:45,860 --> 00:01:46,390
>> David J. MALAN: Jennifer.

39
00:01:46,390 --> 00:01:46,980
Ang lahat ng mga karapatan, Jennifer.

40
00:01:46,980 --> 00:01:47,630
Masaya akong makilala kayo.

41
00:01:47,630 --> 00:01:48,370
Halika sa up.

42
00:01:48,370 --> 00:01:52,430
Kaya ang mga narito ang pitong pintuan, at kung ano
Gusto ko ng mong gawin para sa amin dito,

43
00:01:52,430 --> 00:01:56,560
sa harap ng lahat ng iyong mga kamag-aral,
ay hanapin sa amin ang numero, 50.

44
00:01:56,560 --> 00:02:00,860
Upang mahanap ang isang numero, maaari mong pagsilip sa likod
alinman sa mga pinto sa pamamagitan ng simpleng pag-tap

45
00:02:00,860 --> 00:02:03,030
sa isa sa mga pinto, at ito
ibubunyag nito bilang.

46
00:02:03,030 --> 00:02:06,080
At sabihin makita kung gaano ka kabilis
ay makakahanap sa amin ang numero, 50.

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

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

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

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

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

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

53
00:02:16,530 --> 00:02:17,350
Maayos na Natapos.

54
00:02:17,350 --> 00:02:18,040
Ayos lang.

55
00:02:18,040 --> 00:02:19,906
Yugto ng papuri para sa Jennifer.

56
00:02:19,906 --> 00:02:21,530
>> [Palakpakan]

57
00:02:21,530 --> 00:02:22,320
>> Ayos lang.

58
00:02:22,320 --> 00:02:25,254
Kaya kung ano ang iyong diskarte para sa
paghahanap ng mga numero, 50?

59
00:02:25,254 --> 00:02:27,222
>> Jennifer: Um, naisip ko na baka kung -

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

61
00:02:27,714 --> 00:02:28,206
>> David J. MALAN: Oh.

62
00:02:28,206 --> 00:02:29,630
Bigyan ito ng isang segundo.

63
00:02:29,630 --> 00:02:32,420
Kaya ay ang iyong diskarte para sa
paghahanap ng mga numero, 50?

64
00:02:32,420 --> 00:02:34,760
>> Jennifer: Kaya ko lang magsisimula sa
simula upang makita kung ano ang unang numero

65
00:02:34,760 --> 00:02:38,590
noon, at pagkatapos ay naisip ko na, siguro kung
sila ay pinagsunod-sunod, kukunin ko na lang panatilihing

66
00:02:38,590 --> 00:02:39,970
pagtapik sa mas mataas na up?

67
00:02:39,970 --> 00:02:40,140
>> David J. MALAN: OK.

68
00:02:40,140 --> 00:02:42,910
At tila namin upang Nakakita
na maging ang kaso.

69
00:02:42,910 --> 00:02:45,670
Bagaman, sabihin mag-alis ng balat pabalik ang mga layer
lamang ng isang maliit na bit, at nais mong pumunta

70
00:02:45,670 --> 00:02:47,640
Magpatuloy at ilantad ang iba pang mga pinto
maaaring napili mo?

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

72
00:02:50,400 --> 00:02:51,712
>> Jennifer: Oh, mahal.

73
00:02:51,712 --> 00:02:53,128
>> David J. MALAN: Ah.

74
00:02:53,128 --> 00:02:54,280
>> Jennifer: So Nakakuha ako masuwerteng.

75
00:02:54,280 --> 00:02:55,270
>> David J. MALAN: Kaya ba kayong masuwerteng.

76
00:02:55,270 --> 00:02:55,710
Ayos lang.

77
00:02:55,710 --> 00:02:56,795
Kaya hindi masama.

78
00:02:56,795 --> 00:02:58,750
Ngunit iyon lamang ang isang kawili-wiling
pananaw, tama?

79
00:02:58,750 --> 00:03:01,870
Kung hindi tunay, at ginawa mo makuha,
sa katunayan, isang bit masuwerteng doon.

80
00:03:01,870 --> 00:03:05,350
Ngunit kung ikaw ay ipinapalagay na ang mga numero ay
pinagsunod-sunod, maaari kang maging mas tumpak

81
00:03:05,350 --> 00:03:08,750
bilang sa kung paano naiimpluwensyahan na
ang iyong pag-uugali?

82
00:03:08,750 --> 00:03:11,715
>> Jennifer: Kaya kung sila ay pinagsunod-sunod, ako
Naisip siguro pinakamaliit na pinakamalaking.

83
00:03:11,715 --> 00:03:11,970
>> David J. MALAN: OK.

84
00:03:11,970 --> 00:03:15,260
>> Jennifer: O kung ito napunta sa pagiging
talaga malaki, pagkatapos ay pinakamalaking sa pinakamaliit.

85
00:03:15,260 --> 00:03:15,540
>> David J. MALAN: OK.

86
00:03:15,540 --> 00:03:18,170
Kaya pinakamalaking sa pinakamaliit, o
pinakamaliit na pinakamalaking.

87
00:03:18,170 --> 00:03:21,990
Ngunit ipaalam sa akin imungkahi, ipagpalagay na mayroon kang
nakuha kapus-palad, at ipagpalagay na sila

88
00:03:21,990 --> 00:03:26,840
ay hindi, sa katunayan, pinagsunod-sunod, kung gaano karaming ng
mga pinto ay maaaring nagkaroon ka na pagsilip

89
00:03:26,840 --> 00:03:28,590
sa likod na sa pinakamasama kaso?

90
00:03:28,590 --> 00:03:29,860
>> Jennifer: Ang lahat ng mga ito.

91
00:03:29,860 --> 00:03:30,420
>> David J. MALAN: Ang lahat ng mga ito.

92
00:03:30,420 --> 00:03:31,740
Kaya sabihin ng tuntuning panlahat na bilang n.

93
00:03:31,740 --> 00:03:34,790
May mangyayari sa maging 7, ngunit sabihin pa
sa pangkalahatan ay sinasabi doon ni n mga pinto sa

94
00:03:34,790 --> 00:03:35,650
screen dito.

95
00:03:35,650 --> 00:03:40,110
Kaya sa ang pinakamasama kaso, magkakaroon ka ng
upang tumingin sa likod ng 7 mga pinto, o pintuan n.

96
00:03:40,110 --> 00:03:44,140
At kaya ito ay talagang, ito ay isang bit ng
swerte ngayon, ngunit ito ay talagang isang linear

97
00:03:44,140 --> 00:03:46,440
algorithm ng uri, kahit na na-
ay mga uri ng laktaw sa paligid.

98
00:03:46,440 --> 00:03:47,080
Ay patas na?

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

100
00:03:47,500 --> 00:03:50,000
>> David J. MALAN: Well, hayaan mo akong makita kung ang iyong
diskarte sa pagbabago kung ilipat ko sa amin sa

101
00:03:50,000 --> 00:03:52,190
ang aming ikalawang halimbawa dito sa
7 iba't ibang mga pinto.

102
00:03:52,190 --> 00:03:55,240
Parehong numero, ngunit ito
oras na sila ay pinagsunod-sunod.

103
00:03:55,240 --> 00:03:58,350
Ano ang iyong diskarte dito pagpunta sa maging,
sinusubukan upang ilagay ang out sa iyong isip kung ano

104
00:03:58,350 --> 00:03:59,310
ang iba pang mga numero ay -

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

106
00:03:59,930 --> 00:04:02,290
>> David J. MALAN: - mas maaga?

107
00:04:02,290 --> 00:04:03,180
>> Jennifer: Sabihin simulan
sa unang isa.

108
00:04:03,180 --> 00:04:03,540
>> David J. MALAN: Lahat ng karapatan.

109
00:04:03,540 --> 00:04:05,190
Magsimula sa ang unang isa.

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

111
00:04:05,960 --> 00:04:08,810
Ngayon saan ka pupunta upang pumunta, at bakit?

112
00:04:08,810 --> 00:04:10,040
>> Jennifer: 4 ay talagang maliit.

113
00:04:10,040 --> 00:04:12,500
Kaya kung ang mga ito ay pag-uuri siguro pinakamaliliit
sa pinakamalaking, dapat ito

114
00:04:12,500 --> 00:04:13,290
maging dalawang beses na, at -.

115
00:04:13,290 --> 00:04:13,670
>> David J. MALAN: OK.

116
00:04:13,670 --> 00:04:15,990
Tayo'y makita, na sa palagay mo?

117
00:04:15,990 --> 00:04:19,050
>> Jennifer: Subukan ang huli.

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

119
00:04:19,500 --> 00:04:20,880
>> David J. MALAN: Bihirang mabuti tapos na.

120
00:04:20,880 --> 00:04:21,860
Ayos lang.

121
00:04:21,860 --> 00:04:23,010
>> [Palakpakan]

122
00:04:23,010 --> 00:04:24,310
>> David J. MALAN: OK.

123
00:04:24,310 --> 00:04:26,790
Kaya talaga ginagawa mo ito
horribly, dahil ikaw ay

124
00:04:26,790 --> 00:04:27,700
ginagawa ito nang mahusay.

125
00:04:27,700 --> 00:04:31,150
Na nag-iiwan sa amin magawang
gumawa ng ilang mga puntos.

126
00:04:31,150 --> 00:04:32,565
So sabihin subukan upang ibalik dito.

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

128
00:04:34,560 --> 00:04:35,980
>> David J. MALAN: Bihirang na rin
tapos na, gayunman.

129
00:04:35,980 --> 00:04:39,060
Kaya Sinimulan mo sa simula,
Nakita mo na ito ay 4 na, pagkatapos mong

130
00:04:39,060 --> 00:04:40,240
inilipat na sa dulo.

131
00:04:40,240 --> 00:04:42,320
Ngunit ipagpalagay na hindi mo makakuha ng masuwerteng
doon, at ipagpalagay 50

132
00:04:42,320 --> 00:04:42,890
ay sa ibang lugar.

133
00:04:42,890 --> 00:04:46,190
Ano ang iyong third step na naging?

134
00:04:46,190 --> 00:04:47,680
>> Jennifer: Bumalik sa simula.

135
00:04:47,680 --> 00:04:48,320
>> David J. MALAN: Bumalik
sa simula.

136
00:04:48,320 --> 00:04:51,320
OK, kaya gusto mo na hinawakan
ito pinto, na kung saan ay 8.

137
00:04:51,320 --> 00:04:51,660
Ayos lang.

138
00:04:51,660 --> 00:04:52,650
Kaya hindi iyon 50.

139
00:04:52,650 --> 00:04:55,380
Saan mo na tumingin sa tabi?

140
00:04:55,380 --> 00:04:56,720
>> Jennifer: Kung ako ay hindi
malaman nila pinagsunod-sunod.

141
00:04:56,720 --> 00:04:57,005
>> David J. MALAN: Tama.

142
00:04:57,005 --> 00:04:58,490
Well, kung ginawa mo alam
sila ay pinagsunod-sunod -

143
00:04:58,490 --> 00:04:58,700
>> Jennifer: Oh, alam, oo.

144
00:04:58,700 --> 00:05:00,910
>> David J. MALAN: - ngunit ikaw ay hindi
alam kung saan 50 noon pa?

145
00:05:00,910 --> 00:05:01,785
>> Jennifer: lamang panatilihin ang pagpunta.

146
00:05:01,785 --> 00:05:02,130
>> David J. MALAN: Lahat ng karapatan.

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

148
00:05:02,520 --> 00:05:03,800
Panatilihin ang pagpunta.

149
00:05:03,800 --> 00:05:05,270
OK, na maaari kong magamit.

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

151
00:05:05,610 --> 00:05:07,210
>> David J. MALAN: Ngayon, kung hindi ka lang
pagpunta sa panatilihin ang pagpunta, kung ano ang iyong

152
00:05:07,210 --> 00:05:09,680
algorithm devolving back in.

153
00:05:09,680 --> 00:05:10,740
>> Jennifer: Ang linear -.

154
00:05:10,740 --> 00:05:11,820
>> David J. MALAN: Ito ay uri ng linear.

155
00:05:11,820 --> 00:05:13,480
Ngunit ipaalam sa akin imungkahi, sabihin
ako ilagay sa puwesto.

156
00:05:13,480 --> 00:05:14,900
Hayaan akong i-refresh ang pahina.

157
00:05:14,900 --> 00:05:17,120
parehong numero, parehong pag-aayos,
parehong mga pinto.

158
00:05:17,120 --> 00:05:21,350
Ngunit sa tingin bumalik sa na unang araw sa
kapag klase namin torus isang telepono libro sa

159
00:05:21,350 --> 00:05:25,480
kalahati, uri ng, at kung ano ang noon ay
ang aming diskarte doon?

160
00:05:25,480 --> 00:05:26,450
>> Jennifer: Magsimula sa gitna.

161
00:05:26,450 --> 00:05:26,690
>> David J. MALAN: OK.

162
00:05:26,690 --> 00:05:27,610
Kaya magsisimula sa gitna.

163
00:05:27,610 --> 00:05:28,790
Kaya sabihin sige at gayahin na.

164
00:05:28,790 --> 00:05:30,720
Magsimula sa gitna ng
ibinubunyag na pinto.

165
00:05:30,720 --> 00:05:31,660
Kaya ang bilang 16.

166
00:05:31,660 --> 00:05:35,290
Kaya kung ano ang gusto ng malakas na tao nagawa na,
sino torus ang phone book sa kalahati,

167
00:05:35,290 --> 00:05:38,450
upang makakuha ng sa susunod na hula?

168
00:05:38,450 --> 00:05:39,400
>> Jennifer: Pumunta sa kalahati.

169
00:05:39,400 --> 00:05:41,700
>> David J. MALAN: At bakit sa kanan?

170
00:05:41,700 --> 00:05:43,900
>> Jennifer: Kung sila ay mga uri ng mga pinakamaliliit
sa pinakamalaking, pagkatapos ay 50 ay dapat na

171
00:05:43,900 --> 00:05:44,720
na sa dulo.

172
00:05:44,720 --> 00:05:44,920
>> David J. MALAN: Mahusay.

173
00:05:44,920 --> 00:05:45,390
Lubos makatwirang.

174
00:05:45,390 --> 00:05:48,380
Kaya tulad ng isang libro ng telepono, kang pumunta sa
karapatan bilang kabaligtaran sa kaliwa, ngunit dito

175
00:05:48,380 --> 00:05:49,500
ay ang susi takeaway.

176
00:05:49,500 --> 00:05:53,930
Ikaw ngayon ay maaaring itapon, o pilasin,
kalahati ng ang problemang ito, iiwan sa iyo hindi

177
00:05:53,930 --> 00:05:55,970
may 7 mga pinto, ngunit talagang may lamang 3.

178
00:05:55,970 --> 00:05:57,870
Alin ang halos kalahati ng
laki ng problema.

179
00:05:57,870 --> 00:05:58,350
Ayos lang.

180
00:05:58,350 --> 00:06:01,890
Kaya ngayon kung ano ang mayroon ka
tapos pagkatapos pumunta ka tama?

181
00:06:01,890 --> 00:06:05,870
>> Jennifer: So 16 pa rin ang medyo maliit,
kung ihahambing sa 50, kaya siguro kailangan kong subukan,

182
00:06:05,870 --> 00:06:06,700
tulad ng, ang isang ito.

183
00:06:06,700 --> 00:06:07,890
>> David J. MALAN: Lahat ng karapatan.

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

185
00:06:08,720 --> 00:06:10,830
Ang lahat ng mga karapatan, kaya ngayon kung ano ang iyong
likas na hilig na nagsasabi sa iyo?

186
00:06:10,830 --> 00:06:12,100
>> Jennifer: Maaari ko bang itapon
ito at pagkatapos lamang -

187
00:06:12,100 --> 00:06:12,360
>> David J. MALAN: OK.

188
00:06:12,360 --> 00:06:14,212
Mahusay, maaari mong ibasura
sa kaliwang kalahati doon.

189
00:06:14,212 --> 00:06:14,890
>> Jennifer: - pumili ng isang ito.

190
00:06:14,890 --> 00:06:15,530
>> David J. MALAN: At sa kanan.

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

192
00:06:15,760 --> 00:06:17,820
>> David J. MALAN: Kaya kahit mahirap
upang makita ang di kaya, kapag mayroon lamang

193
00:06:17,820 --> 00:06:21,320
7 mga pinto, isipin ang tungkol, ngayon,
ang pagkakapare-pareho ng mga

194
00:06:21,320 --> 00:06:22,620
algorithm mo lamang inilapat.

195
00:06:22,620 --> 00:06:24,510
Sa nakaraang mga kaso, ng ginawa mo
makakuha ng masuwerteng, na noon ay mahusay.

196
00:06:24,510 --> 00:06:26,540
Pero ginawa mo gamitin ang isang hyuristiko,
Gusto ko sabihin.

197
00:06:26,540 --> 00:06:29,150
Ikaw ginamit uri ng iyong instincts, at
pag-alam ito pinagsunod-sunod, kung ito ay medyo

198
00:06:29,150 --> 00:06:31,600
maliit sa simula, malinaw naman, na namin
Nakakuha upang pumunta nang higit pa sa kanan.

199
00:06:31,600 --> 00:06:34,990
Ngunit sa ilang mga kahulugan, nakukuha mo masuwerteng,
dahil marahil ito ay ang numero 100,

200
00:06:34,990 --> 00:06:36,220
at siguro 50 noon pa sa gitna.

201
00:06:36,220 --> 00:06:37,910
Siguro 50 ay kahit na sa paglipas dito.

202
00:06:37,910 --> 00:06:40,960
>> Ngunit ano ang ginawa mo ng kaunti naiiba
oras na ito noon, ginawa mo ang parehong bagay

203
00:06:40,960 --> 00:06:42,150
muli at muli.

204
00:06:42,150 --> 00:06:45,310
At Gusto ko magtaltalan na kung ano ang iyong lamang
ay, kahit na naimpluwensyahan ng mga telepono

205
00:06:45,310 --> 00:06:48,100
aklat halimbawa, ay isang bagay magkano
higit pang mga algorithmic, at magkano

206
00:06:48,100 --> 00:06:49,930
mas espesyal cased.

207
00:06:49,930 --> 00:06:51,620
Karamihan mas mababa katutubo.

208
00:06:51,620 --> 00:06:57,160
Kaya sa katapusan ng araw, paano gagawin
ilarawan mo ang husay ng

209
00:06:57,160 --> 00:07:00,530
unang algorithm, kung saan ka nagpunta
pakaliwa sa kanan, kumpara sa

210
00:07:00,530 --> 00:07:03,430
pangalawang algorithm dito?

211
00:07:03,430 --> 00:07:06,460
>> Jennifer: ang isa na ito ay dapat, tulad ng, siguro
maghati ng oras, o kahit na higit pa, oo.

212
00:07:06,460 --> 00:07:07,320
>> David J. MALAN: OK, marahil kahit na higit pa.

213
00:07:07,320 --> 00:07:10,150
Sabihin itulak ng kaunti mahirap sa na.

214
00:07:10,150 --> 00:07:13,030
Ano talaga, kung patuloy namin ito
logic, kami siguradong halved ang

215
00:07:13,030 --> 00:07:15,830
tumatakbo ang oras na ito na may pangalawang algorithm
sa pamamagitan ng itsa kalahati ng

216
00:07:15,830 --> 00:07:18,470
mga numero, ngunit kung ano ang ginagawa namin sa susunod
pag-ulit, kapag Jennifer nagsiwalat

217
00:07:18,470 --> 00:07:20,615
ang pangalawang numero?

218
00:07:20,615 --> 00:07:22,830
>> Halved namin ang mga numero ng mga pinto muli.

219
00:07:22,830 --> 00:07:25,270
At pagkatapos ay kung ano ang ginagawa namin matapos na, kung ang
mayroong higit pang mga pinto upang i-play na may?

220
00:07:25,270 --> 00:07:27,520
Gusto naming maghati sa kanila, at muli,
at muli, at muli.

221
00:07:27,520 --> 00:07:30,420
At ito ay katulad lamang ng sa iyo ang lahat ng mga guys
nakatayo hanggang sa unang linggo ng

222
00:07:30,420 --> 00:07:33,000
klase, kalahati ng sa iyo sitting down, kalahati
ng pag-upo ka pababa, kalahati ng sa iyo

223
00:07:33,000 --> 00:07:35,440
sitting down, hanggang sa kaisa-isa isa
kaluluwa ay nakatayo.

224
00:07:35,440 --> 00:07:39,050
At sinabi namin na ang oras ng paggana ng
na, ang bilang ng mga hakbang na ito ay kinuha

225
00:07:39,050 --> 00:07:40,430
sa pagkakasunud-sunod ng kung ano?

226
00:07:40,430 --> 00:07:41,230
>> Tagapagsalita 1: [hindi marinig]

227
00:07:41,230 --> 00:07:43,970
>> David J. MALAN: So log base 2 ng n,
o lamang nang higit pa lamang, mag-log ng n.

228
00:07:43,970 --> 00:07:45,060
Kaya isang bagay logarithmic.

229
00:07:45,060 --> 00:07:48,380
At ang graph ay hindi isang tuwid na linya
na Naging mas masahol at mas masahol pa, ito ay

230
00:07:48,380 --> 00:07:52,490
ito kawili-wiling curve na hindi
makakuha kaya masamang sa paglipas ng panahon.

231
00:07:52,490 --> 00:07:53,910
Kaya sabihin kumapit sa ideyang ito.

232
00:07:53,910 --> 00:07:54,690
Sabihin salamat Jennifer.

233
00:07:54,690 --> 00:07:56,150
Salamat magkano kaya para sa darating up.

234
00:07:56,150 --> 00:07:57,400
At, isa seg.

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

236
00:08:00,170 --> 00:08:02,925
Walang desk lamp ngayon, ngunit hindi namin
kailangang CS50 bola stress.

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

238
00:08:03,420 --> 00:08:04,410
>> David J. MALAN: Ang lahat ng karapatan, dito.

239
00:08:04,410 --> 00:08:06,545
Salamat sa iyo para sa incurring
ang pagkapagod up dito.

240
00:08:06,545 --> 00:08:07,350
Ayos lang.

241
00:08:07,350 --> 00:08:10,620
Kaya sabihin makita kung maaari naming hindi na ngayon
gawing pormal ito nang kaunti pa.

242
00:08:10,620 --> 00:08:14,820
Kaya muli, ano pa lang namin ginawa noon ay
mahalagang parehong bagay tulad ng ginawa namin

243
00:08:14,820 --> 00:08:16,660
na sa unang linggo.

244
00:08:16,660 --> 00:08:23,780
Ngunit sa halip na sa katapusan sa pamamagitan lamang ng isang linear
algorithm, na aming itinatanghal

245
00:08:23,780 --> 00:08:27,210
dati ito bilang tuwid na linya,
kung saan, kung inilalagay namin ang isa pang pinto sa

246
00:08:27,210 --> 00:08:29,610
ang screen, at pagkatapos ay Jennifer gagawin
nagkaroon upang tumingin, potensyal,

247
00:08:29,610 --> 00:08:30,600
sa likod ng isa pang pinto.

248
00:08:30,600 --> 00:08:33,490
Kung inilalagay namin ang dalawang higit pang mga pinto, baka siya ay may
upang tumingin sa likod ng dalawang higit pang mga pinto.

249
00:08:33,490 --> 00:08:35,990
>> At kaya, nagkaroon ito linear
relasyon sa pagitan ng mga sukat ng

250
00:08:35,990 --> 00:08:39,059
problema sa, sabihin nating, ang x-axis, at
ang halaga ng oras na aabutin upang

251
00:08:39,059 --> 00:08:40,440
lumutas sa y.

252
00:08:40,440 --> 00:08:43,330
Ngunit ang larawan ko ay alluding sa
mas maaga ay ang berdeng linya.

253
00:08:43,330 --> 00:08:45,970
Green kusa, dahil
ito lamang nadama mas mahusay.

254
00:08:45,970 --> 00:08:49,790
Sa teorya, ang algorithm, kapag ginawa namin ito
sa aklat ng telepono, kapag ginawa namin ito

255
00:08:49,790 --> 00:08:52,420
sa iyo guys pagbibilang ng bawat isa, at
sa pangalawang pagkakataon, kapag Jennifer lamang

256
00:08:52,420 --> 00:08:55,250
ginawa ito up dito, ito ay pag-uuri
sa panimula ng mas mahusay.

257
00:08:55,250 --> 00:08:57,180
Dahil ito ay hindi lamang dalawang beses nang mas mabilis.

258
00:08:57,180 --> 00:08:58,870
Ito ay hindi kahit na apat na beses na mas mabilis.

259
00:08:58,870 --> 00:09:03,290
Iyon ay ganap na nakasalalay sa kung ano ang
laki ng input ay, bilang sa kung gaano karaming

260
00:09:03,290 --> 00:09:05,220
hakbang ito kinuha sa huli.

261
00:09:05,220 --> 00:09:08,040
>> At kaya ito simpleng ideya na namin ang lahat ng kinuha
para sa ipinagkaloob sa aklat ng telepono,

262
00:09:08,040 --> 00:09:10,200
Maaari katulad mailapat
sa isang bagay na katulad nito.

263
00:09:10,200 --> 00:09:12,380
At ito ay maaaring maging mas casually
na kilala bilang, pati na kapangyarihan sa iyo

264
00:09:12,380 --> 00:09:13,940
isipin, hatiin at lupigin.

265
00:09:13,940 --> 00:09:16,390
Hindi hindi tulad ng kung ano ang ginawa namin, siyempre,
may mga phone book.

266
00:09:16,390 --> 00:09:18,300
>> Ngunit ang pseudocode, isipin ang, ay ito.

267
00:09:18,300 --> 00:09:21,800
Kaya hindi namin gawin ito muli, ngunit isipin ang
na unang linggo, ang lahat ng sa amin nakatayo up

268
00:09:21,800 --> 00:09:25,140
at pagkatapos ay kalahati ng umupo ka down, kalahati ng
umupo ka pababa, kalahati ng umupo ka pababa.

269
00:09:25,140 --> 00:09:29,280
Iyon algorithm ay ipinatupad sa isang
bit ng isang paraan pagdaraya, sa na, ito

270
00:09:29,280 --> 00:09:32,870
ay hindi lamang isa sa akin pagbibilang,
sa panimula, mas mahusay.

271
00:09:32,870 --> 00:09:35,830
Sa kasong iyon, ako ay pagdaragdag
isang pangalawang mapagkukunan.

272
00:09:35,830 --> 00:09:39,470
Pagsunud-sunurin ng, ang maramihang mga CPUs, maraming talino,
maraming matalinong tao sa

273
00:09:39,470 --> 00:09:42,740
room ay pagtulong sa akin makakuha ng isang bagay mula sa
linear sa isang bagay

274
00:09:42,740 --> 00:09:45,190
logarithmic, mula sa isang bagay
pula sa isang bagay na berde.

275
00:09:45,190 --> 00:09:48,650
>> Ngunit sa kasong ito, Jennifer nag-iisa maaari
sa panimula mapabuti ang oras ng

276
00:09:48,650 --> 00:09:52,370
pagganap ng kanyang mga unang algorithm sa pamamagitan ng,
muli, pag-iisip lamang ng kaunti mas mahirap.

277
00:09:52,370 --> 00:09:56,650
At ngayon, pagdating ng panahon upang ipatupad
mga bagay na ito, ang pag-uunawa

278
00:09:56,650 --> 00:10:00,670
kung ano ang mga linya ng code na maaari mong isulat ang naturang
na maaari mong ulitin muli ang mga ito, at

279
00:10:00,670 --> 00:10:03,350
muli, at muli, isang uri ng
sa isang looping fashion.

280
00:10:03,350 --> 00:10:06,370
Dahil hindi ka pagpunta sa may
luxury, tulad ng ginawa Jennifer nang una, upang

281
00:10:06,370 --> 00:10:10,460
lamang magkaroon ang maramihang mga ifs at sabihing,
Hmm, kung ang unang numero ay 4,

282
00:10:10,460 --> 00:10:11,800
hayaan mo akong tumalon lahat ng mga paraan sa dulo.

283
00:10:11,800 --> 00:10:14,180
Ooh, kung ang numero na ay masyadong malaki,
hayaan mo akong ilipat mang bumalik

284
00:10:14,180 --> 00:10:15,220
sa pangalawang elemento.

285
00:10:15,220 --> 00:10:18,210
Makikita mo ang na ito ay pagpunta sa maging ng maraming
mas mahirap upang gawing pormal kung ano ang aming mga kawani na tao

286
00:10:18,210 --> 00:10:21,270
mang-ahas bilang napaka-makatwirang
heuristics, ngunit computer ng isang ay lamang

287
00:10:21,270 --> 00:10:23,260
pagpunta sa gawin kung ano sabihin mo ito upang gawin.

288
00:10:23,260 --> 00:10:25,280
>> Ngayon na ito ay may napaka-interesante
implikasyon.

289
00:10:25,280 --> 00:10:29,950
Ang graph na ito ay isang uri ng sinadya upang pagsunud-sunurin ng
mapuspos biswal, ngunit paunawa, kung saan

290
00:10:29,950 --> 00:10:32,230
ay ang tuwid na linya sa graph na ito?

291
00:10:32,230 --> 00:10:35,330
Saan ang linear graph
na tinatawag naming n?

292
00:10:35,330 --> 00:10:37,580
Well, ito ay isang uri ng patungo sa ibaba
ng ang larawang ito, tama?

293
00:10:37,580 --> 00:10:40,500
Kaya lahat kami ay tapos na namin ang uri ng
naka-zoom out sa x-axis at ang

294
00:10:40,500 --> 00:10:44,780
y-axis upang subukan upang makakuha ng ideya ng kung ano ang
iba pang mga uri ng mga curves hitsura.

295
00:10:44,780 --> 00:10:47,760
>> At ang mga pagtutukoy ng mathematical
expression ngayon ay hindi mahalaga kaya

296
00:10:47,760 --> 00:10:52,440
magkano, ngunit napansin na mayroong ng maraming
algorithm na malayo mas masahol pa kaysa sa

297
00:10:52,440 --> 00:10:53,470
isang bagay na linear.

298
00:10:53,470 --> 00:10:55,410
Sa katunayan, n nakakubo medyo mukhang masama.

299
00:10:55,410 --> 00:10:58,400
2 sa n mukhang medyo masama.
n squared medyo mukhang masama.

300
00:10:58,400 --> 00:11:01,630
At kami makita kung ano ang ilan sa mga
ay maaaring maging sa katotohanan ngayon.

301
00:11:01,630 --> 00:11:05,430
At log n ay hindi pakiramdam bilang masama, ngunit
mas mahusay kaysa sa n ay log base 2 ng n.

302
00:11:05,430 --> 00:11:08,080
Pero alam mo, mas naging kahit na
higit pang mga kamangha-manghang kung Jennifer, o kung kami,

303
00:11:08,080 --> 00:11:12,910
na unang linggo, ay makabuo ng mga
isang bagay na pag-log ng log ng n.

304
00:11:12,910 --> 00:11:15,880
>> Kaya sa ibang salita, may kabuuan na ito
hanay ng mga posibleng solusyon sa mga

305
00:11:15,880 --> 00:11:18,570
problema, ngunit kahit na dito, notice
kung ano ang nangyayari sa mangyari.

306
00:11:18,570 --> 00:11:22,910
Kapag ako mag-zoom out, kung alin sa mga curves
ay pagpunta sa patunayan na maging ganap

307
00:11:22,910 --> 00:11:26,630
pinakamasama ng ang mga nasa screen ngayon?

308
00:11:26,630 --> 00:11:28,680
Kaya n nakakubo mukhang maganda
masama sa sandaling ito.

309
00:11:28,680 --> 00:11:32,470
Ngunit kung kami mag-zoom out at makita ang higit pa sa mga
x at y-axis, kung sino ang pagpunta sa

310
00:11:32,470 --> 00:11:34,550
mangibabaw sa huli?

311
00:11:34,550 --> 00:11:37,120
Kaya ito talaga lumiliko out na 2 sa
n, at maaari mong malaman ito out lamang sa pamamagitan ng

312
00:11:37,120 --> 00:11:39,990
i-plug sa ilang nagiging malaki
numero, at makikita mo na ang 2 sa

313
00:11:39,990 --> 00:11:42,070
n, sa katunayan, ay nakakakuha ng mas malaki mas mabilis.

314
00:11:42,070 --> 00:11:45,530
Kung kami talaga mag-zoom out, isang 2 sa
n algorithm talagang sucks.

315
00:11:45,530 --> 00:11:48,170
Ibig kong sabihin na ito ay pagpunta sa tumagal
pa ng kaunting oras para sa

316
00:11:48,170 --> 00:11:49,460
computer upang magbati sa pamamagitan ng.

317
00:11:49,460 --> 00:11:52,500
>> Ngunit makikita mo sa paglipas ng panahon, lalo na
may hinaharap na mga hanay ng problema at kahit na

318
00:11:52,500 --> 00:11:55,600
huling proyekto, ay ang iyong data
hanay ay makakakuha ng malaki, ang lahat ng karapatan?

319
00:11:55,600 --> 00:11:58,300
Kahit na sa unang bersyon ng Facebook,
bilang ang bilang ng mga kaibigan, at ang

320
00:11:58,300 --> 00:12:01,840
bilang ng mga nakarehistrong user Naging malaking,
Maaari mong pagsunud-sunurin ng telepono ito sa at

321
00:12:01,840 --> 00:12:05,530
ipatupad ang isang bagay na may linear paghahanap,
o isang napaka-simpleng pag-uuri

322
00:12:05,530 --> 00:12:07,030
algorithm, bilang namin makita ngayon.

323
00:12:07,030 --> 00:12:09,280
Mayroon kang upang simulan ang pag-iisip mas mahirap
at mahirap tungkol sa mga problemang ito.

324
00:12:09,280 --> 00:12:12,070
At ang mga uri ng mga problema sa mga lugar tulad ng
Facebook, at Google, at Microsoft,

325
00:12:12,070 --> 00:12:16,350
at iba pa gumagana sa ay eksaktong mga
uri ng malaking data uri ng mga katanungan

326
00:12:16,350 --> 00:12:18,530
nagiging mga araw na ito.

327
00:12:18,530 --> 00:12:18,900
>> Ayos lang.

328
00:12:18,900 --> 00:12:23,800
Kaya Jennifer ng tagumpay sa na pangalawang
algorithm, lantaran, siya ay ginawa amazingly

329
00:12:23,800 --> 00:12:26,110
na rin sa unang pagkakataon, ngunit sabihin
isulat ito bilang swerte kaya na namin

330
00:12:26,110 --> 00:12:27,000
maaaring gumawa ng puntong ito.

331
00:12:27,000 --> 00:12:30,970
Sa pangalawang kaso, siya ay isang magagamit
algorithm na paulit-ulit na muli at

332
00:12:30,970 --> 00:12:34,670
muli, ngunit siya ay kinuha para sa ipinagkaloob ng
ilang mga palagay na namin pinapayagan

333
00:12:34,670 --> 00:12:39,370
kanya, ngunit siya ay pinagsamantalahan ang ilang detalye ang
pangalawang pagkakataon na hindi niya kinailangang mga

334
00:12:39,370 --> 00:12:39,840
unang pagkakataon.

335
00:12:39,840 --> 00:12:41,800
Aling ay kung ano?

336
00:12:41,800 --> 00:12:43,050
>> Iyon ang listahan ay pinagsunod-sunod.

337
00:12:43,050 --> 00:12:46,350
Kaya sa lalong madaling ang listahan ay pinagsunod-sunod, namin
i-claim na Jennifer nagawang gawin

338
00:12:46,350 --> 00:12:47,480
sa panimula mas mahusay.

339
00:12:47,480 --> 00:12:51,450
7 mga pinto, oo, ay hindi na kawili-wili,
ngunit ipagpalagay na ito kami ay 7,000,000 pintuan.

340
00:12:51,450 --> 00:12:54,080
Log ng n ay siguradong pagpunta
upang isagawa magkano, magkano

341
00:12:54,080 --> 00:12:55,610
mas mabilis sa katagalan.

342
00:12:55,610 --> 00:12:58,880
Subalit siya ay nagkaroon na magkaroon ng
pintuan pinagsunod-sunod para sa kanya.

343
00:12:58,880 --> 00:13:02,320
Ngayon, ako kinuha ang kalayaan ng paggawa na
nang maaga sa computer screen

344
00:13:02,320 --> 00:13:05,160
dito, ngunit ipagpalagay na Jennifer
nagkaroon na gawin na kanyang sarili?

345
00:13:05,160 --> 00:13:10,120
Ipagpalagay na ang mga pinto na pinag-uusapan
kinakatawan ng data sa isang database, o

346
00:13:10,120 --> 00:13:14,260
kaibigan nakarehistro para sa Facebook, o
anumang web page sa internet na

347
00:13:14,260 --> 00:13:16,880
iba't-ibang mga website ay maaaring kailangan
sa index ng paghahanap o sa ibabaw.

348
00:13:16,880 --> 00:13:20,940
>> Ipagpalagay na ikaw lamang ay nagkaroon ng isang raw data
itakda at ito ay iniwan sa iyo, o sa

349
00:13:20,940 --> 00:13:23,010
Jennifer na gawin na pag-uuri?

350
00:13:23,010 --> 00:13:26,950
Iyon, sa halip, ay nangangailangan na sagutin namin
ang pinag-uusapan, well, kung magkano ang oras

351
00:13:26,950 --> 00:13:31,080
sana ay kinuha Jennifer, o kahit sa akin,
upang pagbukud-bukurin ang mga numero nang maaga kaya

352
00:13:31,080 --> 00:13:32,680
na siya ay maaaring samantalahin ng mga iyon?

353
00:13:32,680 --> 00:13:32,880
I-right?

354
00:13:32,880 --> 00:13:36,620
Dahil ang implikasyon, siyempre, ay
kung ito ay tumatagal ng lubos sa akin ng isang habang upang pagsunud-sunurin

355
00:13:36,620 --> 00:13:40,800
ang mga numero, na ano ba ang nagmamalasakit ka na
Maaari makahanap ng isang numero tulad ng 50 kaya mabilis,

356
00:13:40,800 --> 00:13:44,850
bilang sa Jennifer ng kaso, kung kami ng higit pa
mapuspos ng halaga ng kabuuang oras

357
00:13:44,850 --> 00:13:46,920
ito kinuha sa pamamagitan ng pagbubukod-bukod ng mga bagay nang maaga?

358
00:13:46,920 --> 00:13:49,320
>> Kaya sabihin makita kung hindi namin magagawa ang
pintura ang larawan dito.

359
00:13:49,320 --> 00:13:51,370
Mayroon akong isang buong bungkos pa ng stress
bola, kung na tumutulong sa

360
00:13:51,370 --> 00:13:52,270
basagin ang yelo dito.

361
00:13:52,270 --> 00:13:55,690
At kung hindi mo nais tututol, namin
kailangan pitong volunteer -

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

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

364
00:13:57,240 --> 00:13:59,250
Kaya hindi namin kailangang gumastos
sa desk lamp, tila.

365
00:13:59,250 --> 00:13:59,690
Ayos lang.

366
00:13:59,690 --> 00:14:01,530
Kaya kung paano tungkol sa iyo dalawa sa harap.

367
00:14:01,530 --> 00:14:04,160
Paano tungkol sa iyo dalawang guys sa likod.

368
00:14:04,160 --> 00:14:04,870
Kaya iyon ang apat.

369
00:14:04,870 --> 00:14:09,890
Paano tungkol sa iyo sa harap
lima, anim at pito.

370
00:14:09,890 --> 00:14:10,320
I-right doon.

371
00:14:10,320 --> 00:14:13,260
Ang iyong kaibigan ay pagturo out ka,
kaya mo makuha ang premyo.

372
00:14:13,260 --> 00:14:13,700
>> Ayos lang.

373
00:14:13,700 --> 00:14:14,410
Halika sa up.

374
00:14:14,410 --> 00:14:17,120
At bakit hindi na mayroon kami sa iyo
guys dumating sa paglipas dito.

375
00:14:17,120 --> 00:14:18,960
Pupunta ako sa magbibigay sa iyo ng bawat isang numero.

376
00:14:18,960 --> 00:14:22,150
At sige at mag-ayos inyong sarili
identically sa kung ano ang

377
00:14:22,150 --> 00:14:25,180
itinatanghal sa screen.

378
00:14:25,180 --> 00:14:26,530
>> [INTERPOSING tinig]

379
00:14:26,530 --> 00:14:28,160
>> David J. MALAN: Oop, paumanhin.

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

381
00:14:30,210 --> 00:14:32,180
Ayos lang.

382
00:14:32,180 --> 00:14:32,750
Well, dito namin pumunta.

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

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

385
00:14:35,136 --> 00:14:37,770
Ang isa, dalawa, tatlo, apat,
lima, anim, pitong.

386
00:14:37,770 --> 00:14:39,410
Oh, ito ay hindi akma.

387
00:14:39,410 --> 00:14:41,210
>> Tagapagsalita 2: kukunin ko na lang makakuha ng -.

388
00:14:41,210 --> 00:14:41,900
>> David J. MALAN: Magandang deal.

389
00:14:41,900 --> 00:14:43,130
Ayos lang.

390
00:14:43,130 --> 00:14:44,611
Salamat sa iyong pakikilahok.

391
00:14:44,611 --> 00:14:47,200
>> [Palakpakan]

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

393
00:14:48,580 --> 00:14:48,860
Ayos lang.

394
00:14:48,860 --> 00:14:51,970
Kaya mayroon kaming apat, dalawa, anim,
isa, tatlo, pitong, lima.

395
00:14:51,970 --> 00:14:56,010
Maperpekto kaya kami ay may pitong mga boluntaryo
sino dito ay pantay-pantay sa lapad sa

396
00:14:56,010 --> 00:14:57,430
array na aming paglalaro
may mga mas maaga.

397
00:14:57,430 --> 00:14:59,470
At ako pinili mo para sa pitong mga dahilan
na magiging lamang

398
00:14:59,470 --> 00:15:00,840
maginhawa sa ilang sandali.

399
00:15:00,840 --> 00:15:04,400
At ako pagpunta sa imungkahi unang na
namin ang uri-uriin ang mga pitong mga boluntaryo.

400
00:15:04,400 --> 00:15:06,786
Kung gusto mo, una,
upang kamustahin bagaman.

401
00:15:06,786 --> 00:15:08,970
Dahil ito ay magiging isang
nakahihiya ilang minuto.

402
00:15:08,970 --> 00:15:10,370
Ipakilala inyong sarili.

403
00:15:10,370 --> 00:15:10,980
>> Grace: Hi, Ako Grace.

404
00:15:10,980 --> 00:15:14,190
Ako ay isang sopomor sa Leverett House.

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

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

407
00:15:15,620 --> 00:15:16,920
Ako ay isang primer anyo sa Weld.

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

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

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

411
00:15:21,040 --> 00:15:22,300
Ako ay isang junior sa Cabot.

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

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

414
00:15:25,980 --> 00:15:29,090
Ako ay isang primer anyo sa Matthews.

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

416
00:15:29,550 --> 00:15:32,816
Ako ay isang primer anyo sa Greenough.

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

418
00:15:33,700 --> 00:15:37,360
Ako ay isang primer anyo sa Grays.

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

420
00:15:37,990 --> 00:15:40,313
Ako ay isang sopomor sa Leverett.

421
00:15:40,313 --> 00:15:41,300
>> David J. MALAN: Mahusay.

422
00:15:41,300 --> 00:15:41,850
Ayos lang.

423
00:15:41,850 --> 00:15:44,190
Well, salamat sa lahat ng aming
boluntaryo dito kaya sa ngayon.

424
00:15:44,190 --> 00:15:47,110
At ang mga hamon sa kamay ngayon ay pagpunta
upang maging upang ayusin ng mga guys, ngunit pagkatapos ay

425
00:15:47,110 --> 00:15:50,250
kami ay pagpunta sa mag-isip ng kaunti
mahirap tungkol sa kung paano mahusay na namin talaga

426
00:15:50,250 --> 00:15:51,110
pinagsunod-sunod ang mga ito.

427
00:15:51,110 --> 00:15:52,580
Kaya sabihin muna subukan ito.

428
00:15:52,580 --> 00:15:55,970
Ka guys ay maaaring makita ng bawat isa mga numero
lamang sa pamamagitan ng paglalagay sa paligid ang mga sulok.

429
00:15:55,970 --> 00:15:59,380
Sige at tumagal ng ilang segundo, at
sort inyong sarili mula sa pinakamaliliit sa

430
00:15:59,380 --> 00:16:01,240
ang natitira upang pinakamalaking sa kanan.

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

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

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

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

435
00:16:08,030 --> 00:16:09,370
Iyon ay talagang darn mabilis.

436
00:16:09,370 --> 00:16:14,040
Ngayon isang tao dito, kung ano ang algorithm ang
na mga guys inilapat?

437
00:16:14,040 --> 00:16:14,900
>> Tagapagsalita 1: bababa sa pinakadakilang.

438
00:16:14,900 --> 00:16:15,000
>> David J. MALAN: OK.

439
00:16:15,000 --> 00:16:18,070
Hindi bababa sa pinakadakilang talaga-uri-uriin ng
layunin, ngunit hindi ako sigurado na

440
00:16:18,070 --> 00:16:18,890
talaga isang algorithm.

441
00:16:18,890 --> 00:16:21,810
Hindi bababa sa pinakamahusay na hindi sabihin
sa akin mga step-by-hakbang kung ano ang gagawin.

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

443
00:16:22,833 --> 00:16:24,083
>> Tagapagsalita 1: [hindi marinig]

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

445
00:16:26,010 --> 00:16:26,280
>> David J. MALAN: OK.

446
00:16:26,280 --> 00:16:28,920
Kaya kung makikita mo ang isang tao na mas maliit sa
ang iyong numero, pagkatapos ay lumipat sa

447
00:16:28,920 --> 00:16:29,680
ang karapatan ng mga ito.

448
00:16:29,680 --> 00:16:32,800
Kaya na ngayon sa pagkuha ng mas makahulugan,
higit na katulad ng isang algorithm, dahil ikaw

449
00:16:32,800 --> 00:16:35,410
Maaaring sabihin, kung ito, pagkatapos na.

450
00:16:35,410 --> 00:16:37,050
Kaya kami ay may ilang mga uri ng
bumuo ng mga kondisyon.

451
00:16:37,050 --> 00:16:39,700
At ang mga guys tila upang gawin iyon ng ilang
beses, dahil ang ilan sa iyo inilipat ng kaunti

452
00:16:39,700 --> 00:16:40,420
ng isang distansya.

453
00:16:40,420 --> 00:16:43,410
Kaya nagkaroon siguro ng ilang mga uri ng
looping nagaganap sa kanilang mga isip.

454
00:16:43,410 --> 00:16:44,610
>> Ngunit sabihin subukan upang gawing pormal na.

455
00:16:44,610 --> 00:16:47,540
Kung ka guys ay maaaring i-reset pabalik
sa pag-aayos na ito.

456
00:16:47,540 --> 00:16:50,650
Tayo'y makita kung hindi namin maaaring gawing pormal ang isang
bit, at pagkatapos ay tanungin ang tanong, lamang

457
00:16:50,650 --> 00:16:51,580
kung paano mahusay na ito?

458
00:16:51,580 --> 00:16:54,220
Siyempre, kapag ginagawa namin ito nang mas mabagal,
ito ay pagpunta sa pakiramdam bilang mabuting ng

459
00:16:54,220 --> 00:16:57,210
isang algorithm, ngunit sabihin makita kung ang aming makakaya
ilagay ang aming mga daliri sa ang tumpak na mga hakbang.

460
00:16:57,210 --> 00:16:58,670
>> Kaya kang dalawang guys ay apat at dalawang.

461
00:16:58,670 --> 00:17:01,020
O kaya mo tama o mali ang pagkakasunod-sunod?

462
00:17:01,020 --> 00:17:01,900
Malinaw na hindi tama.

463
00:17:01,900 --> 00:17:02,710
Kaya namin swapped.

464
00:17:02,710 --> 00:17:05,170
Ngayon ako pagpunta sa magtabi
dito at sabihing, 05:56.

465
00:17:05,170 --> 00:17:06,240
Sigurado ka tama o mali?

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

467
00:17:06,599 --> 00:17:07,180
>> David J. MALAN: Tama.

468
00:17:07,180 --> 00:17:08,300
Anim at isa?

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

470
00:17:08,609 --> 00:17:09,630
Pagpalitin.

471
00:17:09,630 --> 00:17:10,490
Kaya iyon ang dalawang swaps.

472
00:17:10,490 --> 00:17:11,710
Anim na at tatlong?

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

474
00:17:11,980 --> 00:17:13,000
Pagpalitin.

475
00:17:13,000 --> 00:17:13,930
Anim at pito?

476
00:17:13,930 --> 00:17:14,630
Mukhang magandang.

477
00:17:14,630 --> 00:17:15,396
Pitong at limang?

478
00:17:15,396 --> 00:17:16,150
>> Tanikala: [hindi marinig]

479
00:17:16,150 --> 00:17:17,089
>> David J. MALAN: OK, swap.

480
00:17:17,089 --> 00:17:19,770
At pinagsunod-sunod.

481
00:17:19,770 --> 00:17:19,980
Ayos lang.

482
00:17:19,980 --> 00:17:21,440
Kaya malinaw naman hindi, tama?

483
00:17:21,440 --> 00:17:22,470
Kaya doon ay mas pagpunta sa.

484
00:17:22,470 --> 00:17:24,920
Ngunit, sa katunayan, ang mga guys, kahit na
lamang nang katutubo.

485
00:17:24,920 --> 00:17:25,450
iningatan gumagalaw.

486
00:17:25,450 --> 00:17:27,710
Hindi nila lamang tumigil, sa sandaling sila
naitama isa problema.

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

488
00:17:27,839 --> 00:17:29,390
Sa katunayan, pupuntahan ko mayroon
upang gawin ang parehong bagay.

489
00:17:29,390 --> 00:17:32,720
Pupunta ako sa may upang ayusin ng rewind pabalik
sa simula ng ang problemang ito,

490
00:17:32,720 --> 00:17:35,630
o simula ng array na ito ng
mga tao, sabihin simulan ang pagtawag sa kanila.

491
00:17:35,630 --> 00:17:38,366
>> At ngayon kung ano ang dapat ang aking mga algorithm
sa ikalawang pass maging?

492
00:17:38,366 --> 00:17:39,220
>> Tagapagsalita 1: Parehong bagay.

493
00:17:39,220 --> 00:17:39,940
>> David J. MALAN: Parehong bagay.

494
00:17:39,940 --> 00:17:41,460
At ito, ako simula upang gustuhin, tama?

495
00:17:41,460 --> 00:17:44,720
Sa lalong madaling maaari mong mahanap ang iyong sarili paggawa
ang parehong bagay muli at muli, na

496
00:17:44,720 --> 00:17:47,890
pagiging higit na katulad ng isang algorithm,
at mas pantao likas na hilig.

497
00:17:47,890 --> 00:17:48,680
>> Kaya ngayon, dito namin pumunta muli.

498
00:17:48,680 --> 00:17:49,870
Dalawang at apat?

499
00:17:49,870 --> 00:17:50,220
Hindi.

500
00:17:50,220 --> 00:17:51,050
Apat at isa?

501
00:17:51,050 --> 00:17:53,380
Ah, nagkaroon nga ng ilang
gumana pa rin na ma-tapos na.

502
00:17:53,380 --> 00:17:53,620
Para at tatlong?

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

504
00:17:54,572 --> 00:17:56,000
Apat at anim?

505
00:17:56,000 --> 00:17:58,380
Anim at limang?

506
00:17:58,380 --> 00:17:59,470
Anim at pito?

507
00:17:59,470 --> 00:18:00,970
OK, ngayon, tapos na.

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

509
00:18:01,550 --> 00:18:02,710
Mayroon akong upang bumalik.

510
00:18:02,710 --> 00:18:05,130
>> Kaya ngayon, muli, ginagawa namin ito
ang kaunti pa sadya.

511
00:18:05,130 --> 00:18:08,700
At ngayon, mayroong isa lamang sa utak
e-execute ito algorithm.

512
00:18:08,700 --> 00:18:10,290
One CPU, kung kalooban mo.

513
00:18:10,290 --> 00:18:13,090
At lantaran, na ang tanging mapagkukunan
kami ay pagpunta sa may access sa.

514
00:18:13,090 --> 00:18:16,280
At sabay-sabay kami bumalik sa isang keyboard
at magkaroon ng isang bagay tulad ng C sa aming

515
00:18:16,280 --> 00:18:19,600
pagtatapon, tanging sumusulat kami ng isang programa
na maaaring gawin ang isang bagay sa isang pagkakataon.

516
00:18:19,600 --> 00:18:22,900
Sapagkat, ang mga guys ng ilang sandali ang nakalipas, namin
magagamit ang kanilang kolektibong brainpower

517
00:18:22,900 --> 00:18:24,180
tulad mo guys ginawa sa linggo zero.

518
00:18:24,180 --> 00:18:24,980
Kaya sabihin panatilihin ang paggawa na ito.

519
00:18:24,980 --> 00:18:26,260
>> Dalawang at isa.

520
00:18:26,260 --> 00:18:26,945
Dalawa at tatlong.

521
00:18:26,945 --> 00:18:27,460
Tatlong at apat.

522
00:18:27,460 --> 00:18:28,310
Apat at lima.

523
00:18:28,310 --> 00:18:28,620
Limang at anim.

524
00:18:28,620 --> 00:18:30,510
Anim at pito.

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

526
00:18:31,880 --> 00:18:34,560
Kaya ako, ngunit hayaan mo akong maglaro
satanas ng tagapagtaguyod.

527
00:18:34,560 --> 00:18:37,950
Gagawin ko, ang uri ng mga computer na kung sino lamang
ginawa ng pass sa pamamagitan ng hanay ng mga

528
00:18:37,950 --> 00:18:40,225
mga tao, alam na ako tapos?

529
00:18:40,225 --> 00:18:40,670
>> Tagapagsalita 1: Hindi.

530
00:18:40,670 --> 00:18:41,050
>> David J. MALAN: Kaya bakit?

531
00:18:41,050 --> 00:18:46,900
Ano ang gusto kong gawin upang
pagtibayin tiyak na ako ay tapos na?

532
00:18:46,900 --> 00:18:48,230
Malamang isa pang pass.

533
00:18:48,230 --> 00:18:48,430
I-right?

534
00:18:48,430 --> 00:18:51,760
Dahil ang lahat ng mga kakilala ko na mula sa nakaraang
pass ay na naitama ko isang pagkakamali.

535
00:18:51,760 --> 00:18:53,920
At na paraan, siguro mayroong
pa rin ng isa pang pagkakamali

536
00:18:53,920 --> 00:18:54,840
na kailangan ko upang itama.

537
00:18:54,840 --> 00:18:58,680
Kaya ko lamang maging sigurado sa pamamagitan ng rewinding, at
pagkatapos ng pagsusuri, 01:59, at dalawang

538
00:18:58,680 --> 00:19:00,940
tatlo, tatlo at apat, apat at limang,
limang at anim, anim at pito.

539
00:19:00,940 --> 00:19:02,510
OK, ngayon ko ginawang walang trabaho.

540
00:19:02,510 --> 00:19:05,990
>> Maaari ba akong tiyak na tandaan na ang ginawa kong walang
gumana sa isang bagay tulad ng isang variable,

541
00:19:05,990 --> 00:19:06,975
gusto ang isang int.

542
00:19:06,975 --> 00:19:12,490
Tumawag ito swaps, at kung swaps ay 0 beses ko
makarating dito, at ito nagsimula sa 0, pagkatapos ay

543
00:19:12,490 --> 00:19:15,520
Gusto ko lang maging bobo upang panatilihing pagpunta
pabalik-balik, muling suriin, at

544
00:19:15,520 --> 00:19:16,450
muli, at muli, tama?

545
00:19:16,450 --> 00:19:18,450
Dahil hindi ka makaalis sa ilang mga
uri ng walang-katapusang loop.

546
00:19:18,450 --> 00:19:21,250
Kaya sa lalong madaling mayroong 0 swaps,
Maaari naming i-claim na ito

547
00:19:21,250 --> 00:19:23,810
algorithm ay talagang kumpleto.

548
00:19:23,810 --> 00:19:25,400
>> Ngayon, sabihin maglagay ng pangalan sa mga ito.

549
00:19:25,400 --> 00:19:28,930
Ang algorithm na ipanukala ko pa lang namin
ipinatupad ay isang bagay na tinatawag na bubble

550
00:19:28,930 --> 00:19:32,800
-uri-uriin, na kilala bilang tulad sa kamalayan na
ang mga numero na mas malaki uri ng

551
00:19:32,800 --> 00:19:37,990
bubble kanilang mga paraan up sa tuktok, o hanggang
sa dulo ng hanay ng mga numero.

552
00:19:37,990 --> 00:19:40,270
Ngunit paano mahusay noon ay algorithm na ito?

553
00:19:40,270 --> 00:19:44,600
Gaano karaming mga hakbang na ito ang nakuha ko pisikal na kailangang
magtagal, halimbawa, upang ayusin ang mga

554
00:19:44,600 --> 00:19:45,850
pitong kawani na tao?

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

556
00:19:48,560 --> 00:19:49,550
>> Apat sa limang?

557
00:19:49,550 --> 00:19:51,420
OK, masyadong maraming ay sa huli
pagpunta sa maging ang kasagutan.

558
00:19:51,420 --> 00:19:54,960
Ngunit kahit na pagkatapos, ang tiyak na bilang
Hindi kaya kawili-wiling.

559
00:19:54,960 --> 00:19:56,670
Sabihin ng tuntuning panlahat ito bilang n.

560
00:19:56,670 --> 00:20:00,520
Kaya kung ako ay n mga tao dito, at sila
ay, uri ng, sa random na pagkakasunod-sunod sa

561
00:20:00,520 --> 00:20:02,180
simula, sa orihinal na order.

562
00:20:02,180 --> 00:20:04,910
Well, kung gaano karaming mga hakbang na ito ay mayroon akong
gumawa sa unang pass?

563
00:20:04,910 --> 00:20:09,810
Iyon ay isa, dalawa, tatlo, apat, lima,
anim, at ang mga ito ay pitong mga tao, kaya

564
00:20:09,810 --> 00:20:13,670
na pitong, anim -, kaya na n
minus isa hakbang sa unang pagkakataon.

565
00:20:13,670 --> 00:20:16,280
>> Ngayon, kung gaano karaming mga hakbang na ito ay mayroon akong
gumawa kapag rewound ko?

566
00:20:16,280 --> 00:20:19,310
Well, maaari namin talagang i-double na kung
namin talagang gusto, ngunit sa ngayon, ako

567
00:20:19,310 --> 00:20:22,300
lamang ng pagpunta sa sabihin, ang lahat ng karapatan,
isa pa n minus 1.

568
00:20:22,300 --> 00:20:25,240
Kaya ang minus n 1 ay pagpunta upang makakuha ng
nakakainis upang subaybayan, kaya sabihin

569
00:20:25,240 --> 00:20:26,400
lamang paglilikom bahagyang.

570
00:20:26,400 --> 00:20:27,770
Kaya 2n hakbang.

571
00:20:27,770 --> 00:20:29,310
Kaya 14 mga hakbang, bigyan o kumuha.

572
00:20:29,310 --> 00:20:31,930
>> Gaano karaming beses ang nakuha ko tumagal
isang hakbang sa susunod na pagkakataon?

573
00:20:31,930 --> 00:20:33,740
Well, ito ay 3n.

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

575
00:20:34,510 --> 00:20:37,920
At ngayon, sa pinakamasama kaso, para sa
Halimbawa, kung gaano karaming beses Gusto ko mayroon

576
00:20:37,920 --> 00:20:41,730
nawala na pabalik-balik, pabalik-balik,
e-execute ito algorithm, pagpapalit

577
00:20:41,730 --> 00:20:44,620
mga tao sa bawat pass, halos?

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

579
00:20:47,720 --> 00:20:50,010
Talaga Ito ay n squared, tama?

580
00:20:50,010 --> 00:20:53,000
>> Dahil sa ang pinakamasama kaso, maaari mong uri
ng isipin ang tungkol ito intuitively,

581
00:20:53,000 --> 00:20:54,800
kahit na maaaring tumagal ng kaunti
kaunting oras upang malugi in

582
00:20:54,800 --> 00:20:57,590
Sa pinakamasama kaso, ano ang gagawin mga
pitong tao ang mukhang, sa

583
00:20:57,590 --> 00:21:00,230
mga tuntunin ng pag-aayos
ng kanilang mga numero?

584
00:21:00,230 --> 00:21:01,460
Ganap na paurong, tama?

585
00:21:01,460 --> 00:21:02,815
At lamang upang gayahin na,
ano ang iyong pangalan muli?

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

587
00:21:03,360 --> 00:21:03,640
>> David J. MALAN: Mike?

588
00:21:03,640 --> 00:21:08,100
OK, Mike, maaari ka lamang sumali sa akin sa paglipas ng
dito lamang para sa isang segundo?

589
00:21:08,100 --> 00:21:08,880
Talaga, hindi.

590
00:21:08,880 --> 00:21:10,150
Paumanhin Mike, sabihin rewind.

591
00:21:10,150 --> 00:21:10,910
Ano ang inyong pangalan muli?

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

593
00:21:11,180 --> 00:21:11,640
>> David J. MALAN: Neil.

594
00:21:11,640 --> 00:21:13,750
OK, Neil, pumunta ka sa
sa akin, kung hindi tututol kayo.

595
00:21:13,750 --> 00:21:17,150
Kaya ako ng pagpunta sa imungkahi, para lamang sa
simple, na Neil ay nasa kanyang

596
00:21:17,150 --> 00:21:18,510
pinakamasama posibleng sitwasyon.

597
00:21:18,510 --> 00:21:20,720
Ngunit isipin ang kung paano naipatupad ko
ang aking mga algorithm.

598
00:21:20,720 --> 00:21:24,530
Ako paghahambing, paghahambing, paghahambing,
paghahambing, paghahambing, oh.

599
00:21:24,530 --> 00:21:26,640
Ngayon ang mga guys ay out
ng order, kaya ko aayusin.

600
00:21:26,640 --> 00:21:27,980
Kaya mo guys swap.

601
00:21:27,980 --> 00:21:31,630
Subalit isaalang-alang ngayon, kung magkano ang higit na malayo
Neil ay may upang pumunta?

602
00:21:31,630 --> 00:21:32,690
Halos Ito ay n.

603
00:21:32,690 --> 00:21:33,570
Alam mo, ito ay hindi talaga n.

604
00:21:33,570 --> 00:21:36,040
Ito ay tulad, n minus 1, ngunit ako nakakakuha
nayayamot pagpapanatiling track ng kaunti

605
00:21:36,040 --> 00:21:37,550
numero, kaya sabihin lang tawagan n ito.

606
00:21:37,550 --> 00:21:42,860
>> Kaya kung Neil gumagalaw isang hakbang maximally bawat
oras, at upang ilipat Neil isang hakbang,

607
00:21:42,860 --> 00:21:46,580
Mayroon akong upang gumawa ito talagang nakakapagod pass
pabalik-balik, ito ay tinatayang

608
00:21:46,580 --> 00:21:52,080
ginagawa ito, n hakbang na ito, sa kabuuan ng n beses,
dahil ito ay pagpunta sa tumagal sa akin

609
00:21:52,080 --> 00:21:55,820
na maraming mga hakbang na ito upang makakuha ng lahat ng Neil
ang daan sa kung saan siya nabibilang.

610
00:21:55,820 --> 00:21:58,620
Hayaang mag-isa ang iba kung ikaw guys
lahat ay di-nakaayos pati na rin.

611
00:21:58,620 --> 00:22:01,100
>> Kaya sabihin tumawag bubble sort n squared.

612
00:22:01,100 --> 00:22:04,860
Ang oras ng paggana ng algorithm na ito, ang
pagganap ng algorithm, ang

613
00:22:04,860 --> 00:22:07,120
kahusayan ng algorithm na ito,
tayo lamang ilarawan nang higit pa

614
00:22:07,120 --> 00:22:08,800
sa pangkalahatan bilang n nakalapat.

615
00:22:08,800 --> 00:22:11,650
Alin ang magaling, dahil maaari kong gawin ang
parehong halimbawa na may walong mga tao, siyam

616
00:22:11,650 --> 00:22:15,450
mga tao, isang milyong mga tao, at na
sagot ay hindi pagpunta upang baguhin.

617
00:22:15,450 --> 00:22:18,870
>> Kaya't kung ikaw guys ay hindi tututol, sabihin
i-reset mo sa kung saan ka magsimula.

618
00:22:18,870 --> 00:22:22,510
At sabihin subukan ang dalawang iba pang mga approach na at
makita kung hindi namin maaaring gawin sa panimula

619
00:22:22,510 --> 00:22:23,820
mas mahusay kaysa sa na ito.

620
00:22:23,820 --> 00:22:27,130
Kaya oras na ito, pupuntahan ko ipanukala
isang uri ng iba't ibang mga algorithm.

621
00:22:27,130 --> 00:22:29,950
Iyon ay napaka-matalino sa atin huling oras,
at ka guys ay karapatan na mayroon ang

622
00:22:29,950 --> 00:22:32,470
karapatan instincts lamang ng uri
pagpapalit ng pairwise.

623
00:22:32,470 --> 00:22:36,500
Ngunit kung ako talagang gusto lapitan ito
lamang, at ang aking layunin ay upang ilipat

624
00:22:36,500 --> 00:22:39,800
lahat ng maliit na mga numero ng paraang ito, at
itulak ang lahat ng mga malaking mga numero na

625
00:22:39,800 --> 00:22:43,030
paraan, bakit hindi ko na lang gawin iyon sa
pinaka-walang muwang paraan posible at makita kung ako

626
00:22:43,030 --> 00:22:45,730
maaaring gawin mas mahusay kaysa sa kung ano ay isang
medyo complex algorithm?

627
00:22:45,730 --> 00:22:46,620
>> Kaya natin makita.

628
00:22:46,620 --> 00:22:48,940
Apat ay isang medyo maliit na bilang, kaya ako
pagpunta sa umalis ka doon sandali.

629
00:22:48,940 --> 00:22:50,610
Ooh, dalawang numero ay mas mahusay.

630
00:22:50,610 --> 00:22:52,230
Kaya maaari mo lamang humakband
para sa isang sandali?

631
00:22:52,230 --> 00:22:55,670
Ito ang aking kasalukuyang pinakamaliit na numerong
kandidato, at pupuntahan ko matandaan

632
00:22:55,670 --> 00:22:57,000
na may, gusto, sa isang variable.

633
00:22:57,000 --> 00:22:57,930
Ngunit ako pagpunta sa panatilihin ang pagsuri.

634
00:22:57,930 --> 00:22:59,890
Mayroon bang isang tao na ang
numero ay mas maliit?

635
00:22:59,890 --> 00:23:00,460
Anim, hindi.

636
00:23:00,460 --> 00:23:01,390
Oh, mayroong Neil muli.

637
00:23:01,390 --> 00:23:04,050
>> Kaya ako ng pagpunta sa itulak ka pabalik
uri ng conceptually.

638
00:23:04,050 --> 00:23:05,120
Neil ay darating pasulong.

639
00:23:05,120 --> 00:23:08,440
At ngayon, ang mga variable na gumagamit ako sa
subaybayan kung sino ang may mga pinakamaliliit

640
00:23:08,440 --> 00:23:11,390
numero ay na-update upang maglaman ng
Neil ng lokasyon.

641
00:23:11,390 --> 00:23:12,110
Well, sabihin makita.

642
00:23:12,110 --> 00:23:13,960
Tatlong, pitong, lima.

643
00:23:13,960 --> 00:23:15,590
OK, alam ko Neil ay ang pinakamaliit na.

644
00:23:15,590 --> 00:23:18,110
Ano ang pinakasimpleng bagay
para sa akin upang gawin ngayon?

645
00:23:18,110 --> 00:23:21,410
Hindi ako pagpunta sa sayangin ang aking oras sa pamamagitan lamang
bulubok Neil isa puwesto sa kaliwa.

646
00:23:21,410 --> 00:23:25,350
Bakit hindi ko lang ilagay Neil kung saan siya
Nabibilang, na siyempre saan?

647
00:23:25,350 --> 00:23:26,160
>> Ang lahat ng mga paraan sa simula.

648
00:23:26,160 --> 00:23:27,720
Kaya Neil, sumama kayo sa akin.

649
00:23:27,720 --> 00:23:28,910
At kung ano ang iyong pangalan muli?

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

651
00:23:29,310 --> 00:23:29,710
>> David J. MALAN: Grace.

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

653
00:23:29,920 --> 00:23:32,490
So Grace, sa kasamaang-palad, ikaw ay
uri ng sa paraan.

654
00:23:32,490 --> 00:23:34,290
Kaya paano namin malutas ang problemang ito?

655
00:23:34,290 --> 00:23:34,490
I-right?

656
00:23:34,490 --> 00:23:37,500
Kung ito ay isang array, mayroong
lamang pitong mga lokasyon.

657
00:23:37,500 --> 00:23:40,830
Isipin ang na, may Rob, usapan natin ang tungkol sa
deklarasyon ng edad, at lamang namin ay nagkaroon ng isang

658
00:23:40,830 --> 00:23:41,740
may hangganan bilang ng edad?

659
00:23:41,740 --> 00:23:42,535
Parehong ideya dito.

660
00:23:42,535 --> 00:23:44,300
Kami lamang magkaroon ng isang tiyak na bilang ng mga ints.

661
00:23:44,300 --> 00:23:47,590
Grace ay uri ng sa aming
paraan, kaya paano namin ayusin?

662
00:23:47,590 --> 00:23:49,555
>> Ang pinakamadaling paraan ay tulad,
Grace, paumanhin.

663
00:23:49,555 --> 00:23:51,870
Ikaw ay pagpunta sa may upang pumunta sa ibabaw
doon upang maaari naming gumawa ng room.

664
00:23:51,870 --> 00:23:55,290
Ngayon, kung sa tingin mo tungkol sa mga ito, siguro
lang namin ginawa ang problema mas masahol pa.

665
00:23:55,290 --> 00:23:58,510
At siguro ginawa namin, dahil kung ano
Grace ay nasa tamang lugar?

666
00:23:58,510 --> 00:24:01,730
Ngunit alam namin siya hindi, dahil
kung hindi man, gusto siya naging

667
00:24:01,730 --> 00:24:03,980
nakatayo forward sa halip ng
Neil sa oras na ito, tama?

668
00:24:03,980 --> 00:24:05,550
Kami ay naka-check ang kanyang numero out.

669
00:24:05,550 --> 00:24:05,770
>> Ayos lang.

670
00:24:05,770 --> 00:24:09,110
Kaya ngayon, Neil ay nasa tamang lugar, at
Ang maaari kong gawin ang isang bahagyang pag-optimize.

671
00:24:09,110 --> 00:24:11,740
Para sa susunod na minuto, pupuntahan ko huwag pansinin
Neil lahat ng sama-sama, sa gayon ay hindi

672
00:24:11,740 --> 00:24:15,280
mag-aaksaya ng kanyang oras, o aksidenteng
swap sa kanya sa maling lugar.

673
00:24:15,280 --> 00:24:17,805
Kaya ngayon, paano ko mahanap ang susunod na
elemento na pinakamaliit?

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

675
00:24:18,480 --> 00:24:20,225
Iyan ay isang medyo magandang numero, kung
Gusto mo sa hakbang pasulong at

676
00:24:20,225 --> 00:24:21,100
Kukunin ko tandaan mo.

677
00:24:21,100 --> 00:24:21,980
Anim, walang mabuti.

678
00:24:21,980 --> 00:24:24,820
Apat, tatlo, pitong, lima, walang mabuti.

679
00:24:24,820 --> 00:24:26,800
Kaya hayaan mo akong ilipat sa iyo upang
ang iyong mga tamang lugar.

680
00:24:26,800 --> 00:24:28,470
At kami Naging masuwerteng oras na ito.

681
00:24:28,470 --> 00:24:31,350
>> Ngayon, pupuntahan ko na balewalain ang mga
dalawang guys, at ngayon ay gawin ang isa pa

682
00:24:31,350 --> 00:24:32,260
dumaan na ito.

683
00:24:32,260 --> 00:24:33,490
Anim na, na ang isang medyo maliit na bilang.

684
00:24:33,490 --> 00:24:34,300
Halika sa pasulong.

685
00:24:34,300 --> 00:24:35,220
Oh, paumanhin.

686
00:24:35,220 --> 00:24:37,640
Grace ng numero ay mas mahusay,
kaya hakbang sa forward.

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

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

689
00:24:39,120 --> 00:24:39,950
Bumalik muli.

690
00:24:39,950 --> 00:24:41,550
Numero ng tatlong ay mas mahusay.

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

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

693
00:24:42,720 --> 00:24:43,550
At ngayon kung ano ang iyong pangalan muli?

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

695
00:24:44,000 --> 00:24:44,420
>> David J. MALAN: Jason.

696
00:24:44,420 --> 00:24:47,050
Kaya Jason na ngayon ang pinakamaliit na
elemento aking napili.

697
00:24:47,050 --> 00:24:49,160
Kung saan siya ay pagpunta sa pumunta?

698
00:24:49,160 --> 00:24:50,380
Kaya kung saan ay anim.

699
00:24:50,380 --> 00:24:51,210
At ang iyong pangalan ay muli?

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

701
00:24:51,710 --> 00:24:52,340
>> David J. MALAN: Gabe.

702
00:24:52,340 --> 00:24:53,220
Gabe ay sa paraan.

703
00:24:53,220 --> 00:24:54,640
Ano ang pinakamadaling bagay na gawin?

704
00:24:54,640 --> 00:24:58,390
Pagpalitin ang dalawang guys at magpatuloy.

705
00:24:58,390 --> 00:24:59,020
Kaya ngayon sabihin makita.

706
00:24:59,020 --> 00:25:00,170
Sino ang pinakamaliit?

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

708
00:25:01,030 --> 00:25:01,990
Hayaan akong lamang uri ng impostor.

709
00:25:01,990 --> 00:25:03,090
Limang ay pagpunta sa maging sa pinakamaliliit na.

710
00:25:03,090 --> 00:25:05,220
Tingin ko susunod, kung, gusto mo sa hakbang
pasulong, ano ang dapat kong gawin sa mga

711
00:25:05,220 --> 00:25:06,820
mga guys, may Gabe?

712
00:25:06,820 --> 00:25:08,450
Pagpalitin muli.

713
00:25:08,450 --> 00:25:10,740
Kaya ngayon, pa rin bahagyang out ng order.

714
00:25:10,740 --> 00:25:14,140
May nakita akong Gabe upang maging sa pinakamaliliit na, kaya
Ako magpa-pop out sa kanya, ilipat mo guys sa ibabaw.

715
00:25:14,140 --> 00:25:15,190
At tapos na.

716
00:25:15,190 --> 00:25:17,200
>> Kaya sagot ay pareho.

717
00:25:17,200 --> 00:25:18,600
Ang katapusan ng resulta ay pareho.

718
00:25:18,600 --> 00:25:22,730
Alin sa mga ito ang dalawang mga algorithm
ang mas mainam?

719
00:25:22,730 --> 00:25:23,500
Ang ikalawang isa, Narinig ko.

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

721
00:25:24,252 --> 00:25:25,900
>> Tagapagsalita 3: Ito ay n hakbang [hindi marinig].

722
00:25:25,900 --> 00:25:27,600
>> David J. MALAN: Ito'y n hakbang sa karamihan.

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

724
00:25:28,490 --> 00:25:30,610
Kaya ito ay bagaman?

725
00:25:30,610 --> 00:25:33,630
Kaya kung paano ang nakuha ko mahanap ang
pinakamaliliit na elemento?

726
00:25:33,630 --> 00:25:37,060
Gaano karaming mga hakbang na ito ay mayroon akong gumawa
ang mahanap ang pinakamaliit na elemento?

727
00:25:37,060 --> 00:25:39,220
Ako ay isang tumingin sa lahat ng paraan
sa dulo, tama?

728
00:25:39,220 --> 00:25:41,530
Dahil sa na ang pinakamasama kaso, kung ano
kung Neil ay higit sa dito?

729
00:25:41,530 --> 00:25:45,700
Kaya lamang ang paghahanap ng mga na ang pinakamaliit na elemento
tumatagal sa akin n hakbang na ito, o minus n 1.

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

731
00:25:46,100 --> 00:25:46,980
Kaya ayusin Neil.

732
00:25:46,980 --> 00:25:48,740
Tandaan na, isang minuto o kaya ang nakalipas.

733
00:25:48,740 --> 00:25:51,680
>> Ngunit kung paano ang nakuha ko mahanap ang susunod na
pinakamaliliit na elemento?

734
00:25:51,680 --> 00:25:54,830
Ito'y n minus 1, o minus n 2 talaga,
mula sa bilang ng mga hakbang na ito.

735
00:25:54,830 --> 00:25:55,440
Kaya OK.

736
00:25:55,440 --> 00:25:57,390
Kaya ako nag-n minus 2.

737
00:25:57,390 --> 00:25:57,600
Ayos lang.

738
00:25:57,600 --> 00:25:59,130
Kaya na pakiramdam ng isang maliit na mas mahusay.

739
00:25:59,130 --> 00:25:59,730
Ayos lang.

740
00:25:59,730 --> 00:26:03,270
Gaano karaming mga hakbang sa susunod na oras
upang mahanap ang numero ng tatlong?

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

742
00:26:04,420 --> 00:26:07,670
Kaya ito ay mababawasan, isa mas kaunti
hakbang sa bawat pag-ulit.

743
00:26:07,670 --> 00:26:08,740
Kaya ito ay mas mahusay na pakiramdam, tama?

744
00:26:08,740 --> 00:26:13,450
Kung ang huling beses na iyon ay halos n beses n,
oras na ito ito ay n minus 1, plus n minus

745
00:26:13,450 --> 00:26:16,500
2, plus n minus 3, plus n
minus 4, tuldok, tuldok, tuldok.

746
00:26:16,500 --> 00:26:18,750
Ngunit kung isipin ang mo mula sa iyong mga mataas na paaralan
aklat-aralin, ang maliit na manlilinlang

747
00:26:18,750 --> 00:26:24,380
sheet sa likod na may mga formula, kung
ikaw magdagdag ng hanggang na ito serye ng mga numero,

748
00:26:24,380 --> 00:26:31,280
ano ay ang kabuuang bilang ng mga hakbang
pagpunta upang maging na tumagal ako dito?

749
00:26:31,280 --> 00:26:36,580
>> Ito ay isa sa mga iyon, i, n minus
1, n beses, na hinati sa 2.

750
00:26:36,580 --> 00:26:39,040
Kaya hayaan mo akong makita kung maaari kong hilahin
ito up para lamang ng ilang sandali.

751
00:26:39,040 --> 00:26:42,230
At muli, ako uri ng ilang mga rounding
mga numero lamang upang panatilihin ang aming mga buhay simple,

752
00:26:42,230 --> 00:26:47,830
ngunit bilang ko maalala muli, ito ay isang bagay tulad ng kung
Gagawin ko n minus 1 bagay, pagkatapos n minus

753
00:26:47,830 --> 00:26:53,570
2, pagkatapos n minus 3, ito ay humigit-kumulang
isang bagay na tulad nito sa paglipas ng 2, at kung ako

754
00:26:53,570 --> 00:26:55,510
multiply ito out, na
talaga n square.

755
00:26:55,510 --> 00:26:58,940
Na hindi pakiramdam masyadong mabuti.
n minus n sa 2.

756
00:26:58,940 --> 00:27:00,350
>> Ngunit narito ang bagay.

757
00:27:00,350 --> 00:27:03,720
Sa computer science, kapag ang mga problema
simulan upang makakuha ng kawili-wiling ay kapag n

758
00:27:03,720 --> 00:27:04,700
ay makakakuha ng talagang malaki.

759
00:27:04,700 --> 00:27:08,110
At kapag n nakakakuha talaga malaki, kung alin sa
ang mga halagang ito ay pagpunta sa mangibabaw ang lahat ng

760
00:27:08,110 --> 00:27:09,750
ng iba?

761
00:27:09,750 --> 00:27:10,990
Ito ay uri ng mga n squared, tama?

762
00:27:10,990 --> 00:27:13,340
Oo, sa pamamagitan ng paghati 2 ay medyo mabuti.

763
00:27:13,340 --> 00:27:16,740
Ngunit kung ikaw ay pakikipag-usap tungkol sa bilyon-bilyong
ng mga piraso ng data, o trillions ng

764
00:27:16,740 --> 00:27:18,700
mga piraso ng data, OK, kaya
ikaw ay dalawang beses nang mas mabilis.

765
00:27:18,700 --> 00:27:22,440
Ngunit sino ba talagang nagmamalasakit kung malaki na numero,
kung factor na ito ay kung ano ang nakukuha ng

766
00:27:22,440 --> 00:27:23,040
mas malaki at mas malaki.

767
00:27:23,040 --> 00:27:25,990
At tiyak, ito ay ginagawang higit pa sa
isang pagkakaiba kaysa ito tao.

768
00:27:25,990 --> 00:27:29,120
Kaya kahit na na guys ay tama, ang
pangalawang algorithm, aming tawagan ito

769
00:27:29,120 --> 00:27:32,970
pagpili ng uri, ay, sa tunay na mundo, isang
bit mas mabilis na potensyal na, dahil ako ay

770
00:27:32,970 --> 00:27:35,360
pagkuha ng mas kaunting at mas kaunting
hakbang sa bawat oras.

771
00:27:35,360 --> 00:27:37,340
>> Ito ay hindi tunay na sa panimula mas mabilis.

772
00:27:37,340 --> 00:27:41,430
Dahil kung namin talagang i-play ito out para sa
malaking halaga ng n, sa dulo ng

773
00:27:41,430 --> 00:27:44,750
ang araw, para malaki sapat n, pa rin ito
pagpunta sa pakiramdam medyo mabagal.

774
00:27:44,750 --> 00:27:46,770
Well, hayaan mo akong kumuha ng isa
huling pass sa na.

775
00:27:46,770 --> 00:27:48,920
Iyon ay kung ano ang gusto kong tumawag
pagpili-uri.

776
00:27:48,920 --> 00:27:51,040
Maaari mong i-reset ang guys inyong sarili
isa huling oras?

777
00:27:51,040 --> 00:27:53,550
At sa huling pagkakataon, pupuntahan ko
upang ipanukala ang isang bagay

778
00:27:53,550 --> 00:27:54,970
tinatawag na pagpapasok sort.

779
00:27:54,970 --> 00:27:57,470
Insertion sort pagiging, conceptually,
medyo naiiba.

780
00:27:57,470 --> 00:28:00,980
>> Kaysa sa pagpunta papunta at pabalik at
pagpili sa pinakamaliliit na elemento, ako

781
00:28:00,980 --> 00:28:05,030
lamang ng pagpunta sa makitungo sa bawat isa sa mga
guys bilang ko makaharap ang mga ito, at ipasok

782
00:28:05,030 --> 00:28:06,850
ang mga ito sa kanilang wastong lugar.

783
00:28:06,850 --> 00:28:10,160
Kaya lang ako sa pagpunta sa magsimula sa Grace,
at nakikita ko na siya bilang apat.

784
00:28:10,160 --> 00:28:11,720
Saan kinukuha bilang apat nabibilang?

785
00:28:11,720 --> 00:28:14,940
Hindi ko pa sinimulan ng pagbubukod-bukod ng anumang bagay,
kaya Grace ay nakakakuha upang manatili doon.

786
00:28:14,940 --> 00:28:18,355
At ngayon ako pagpunta sa i-claim, kung magagawa mong
kumuha ng isang hakbang sa iyong mga karapatan, ito

787
00:28:18,355 --> 00:28:21,650
aking listahan pinagsunod-sunod, ito ay ang aking
unsorted natitirang listahan.

788
00:28:21,650 --> 00:28:23,260
Kaya ngayon ako pagpunta sa magpatuloy sa tabi,
at kung ano ang iyong pangalan muli?

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

790
00:28:23,700 --> 00:28:24,150
>> David J. MALAN: Branson.

791
00:28:24,150 --> 00:28:25,375
Kaya Branson ay dalawang numero.

792
00:28:25,375 --> 00:28:27,490
Kaya ako ng pagpunta sa magdadala sa iyo
out para sa isang sandali.

793
00:28:27,490 --> 00:28:30,940
At ngayon, saan ka nabibilang
sa array na ito?

794
00:28:30,940 --> 00:28:32,360
Kaya sa kanan ng Grace.

795
00:28:32,360 --> 00:28:35,670
Kaya muli, kami uri ng paggawa
Grace gawin ng maraming trabaho dito.

796
00:28:35,670 --> 00:28:37,290
Saan namin ilalagay mo?

797
00:28:37,290 --> 00:28:40,120
Kaya kami ay pagpunta sa slide ka sa
pakaliwa, at ipasok Branson doon.

798
00:28:40,120 --> 00:28:41,680
Ngunit ngayon inaangkin ko na
ka guys ay tapos na.

799
00:28:41,680 --> 00:28:43,240
Ngunit notice, hindi ko ginagamit ng dagdag na espasyo.

800
00:28:43,240 --> 00:28:45,130
Ito ay pa rin ang 2 elemento
dito, 5 paglipas dito.

801
00:28:45,130 --> 00:28:47,910
Kabuuang sukat ng array ay 7, kaya ako
hindi Pandaraya, ang lahat ng karapatan?

802
00:28:47,910 --> 00:28:51,950
>> Kaya ngayon mayroon kami, may Gabe dito, ang
anim na numero, kung saan ka nabibilang?

803
00:28:51,950 --> 00:28:52,650
Nakakuha ka masuwerteng muli.

804
00:28:52,650 --> 00:28:53,820
Kaya mo makakuha upang manatili doon.

805
00:28:53,820 --> 00:28:57,210
Lang tumagal ng bahagyang hakbang sa kanan
lamang upang gumawa ng malinaw na kayo ay pinagsunod-sunod.

806
00:28:57,210 --> 00:29:00,520
At ngayon, mayroon kaming Neil muli, numero
isa, saan ka pumunta?

807
00:29:00,520 --> 00:29:03,540
At ngayon ay kung saan magsisimula kaming upang makita na
algorithm na ito, bagaman sa unang

808
00:29:03,540 --> 00:29:05,950
sulyap, palagay ng medyo matalino, panoorin
kung ano ang tungkol sa nangyari.

809
00:29:05,950 --> 00:29:07,370
Kung maaari mong humakbang pasulong.

810
00:29:07,370 --> 00:29:09,260
>> Saan nagpupunta ang mga nais naming ilagay Neil?

811
00:29:09,260 --> 00:29:11,830
Kaya malinaw naman dito, kaya paano
huwag naming kumuha Neil doon?

812
00:29:11,830 --> 00:29:12,970
Tayo'y gawin ito hakbang-hakbang.

813
00:29:12,970 --> 00:29:15,620
Gabe, kung saan kailangan mong pumunta?

814
00:29:15,620 --> 00:29:19,590
Yep, kaya tumagal ng isang malaking hakbang,
o dalawang half-hakbang na ito upang gumawa ng mga

815
00:29:19,590 --> 00:29:20,820
isang hakbang sa paglipas ng doon.

816
00:29:20,820 --> 00:29:21,750
Grace, kung saan ka pumunta?

817
00:29:21,750 --> 00:29:22,510
Magandang.

818
00:29:22,510 --> 00:29:23,500
Kaya isa pang hakbang.

819
00:29:23,500 --> 00:29:24,960
At sa wakas, Branson?

820
00:29:24,960 --> 00:29:25,460
Isa pang hakbang.

821
00:29:25,460 --> 00:29:27,190
At ngayon maaari naming ilagay Neil sa lugar.

822
00:29:27,190 --> 00:29:28,440
>> Kaya ngayon, patuloy na ito logic.

823
00:29:28,440 --> 00:29:32,420
Kahit na hindi kami paglilipat Neil
sa ibabaw, at sa paglipas ng, at mahigit sa, upang ilagay sa kanya

824
00:29:32,420 --> 00:29:36,420
kung saan siya napupunta, sa pinakamasama kaso, ang
susunod na bilang maaari naming makatagpo ng dati

825
00:29:36,420 --> 00:29:42,220
maging ang bilang, sabihin nating, nagkaroon ng isang numero
zero, pagkatapos kami ay pagpunta sa shift ang lahat ng

826
00:29:42,220 --> 00:29:42,730
mga guys.

827
00:29:42,730 --> 00:29:44,950
Ipagpalagay na may isang numero, mga negatibong
isa, pagkatapos kami ay may sa shift

828
00:29:44,950 --> 00:29:46,080
lahat ng mga guys.

829
00:29:46,080 --> 00:29:48,500
Kaya kami ay talagang lamang uri ng flipping
ang problema sa paligid, tulad na kami ay

830
00:29:48,500 --> 00:29:52,620
paglilipat ng mga gastos mula sa
pagpili proseso kaya ang pagpapasok

831
00:29:52,620 --> 00:29:56,930
proseso, tulad mo na guys lang nagkaroon
upang ilipat ang halos n minus isang bagay

832
00:29:56,930 --> 00:29:57,940
bilang ng mga hakbang.

833
00:29:57,940 --> 00:30:01,200
At na bilang ng mga hakbang ay lamang ng pagpunta
upang madagdagan ang bilang piliin ko pa numero,

834
00:30:01,200 --> 00:30:04,730
kung mayroon akong upang panatilihin shoving mo guys
pabalik, at bumalik, at likod.

835
00:30:04,730 --> 00:30:08,320
>> Kaya ang malungkot bagay ay ngayon ang lahat ng mga
algorithm ay n squared.

836
00:30:08,320 --> 00:30:10,570
Sabihin sige at salamat sa mga
guys, at isalarawan ang mga ito ng kaunti

837
00:30:10,570 --> 00:30:11,090
magkaiba.

838
00:30:11,090 --> 00:30:12,312
Tunay na magaling.

839
00:30:12,312 --> 00:30:14,120
>> [Palakpakan]

840
00:30:14,120 --> 00:30:15,030
>> Ayos lang.

841
00:30:15,030 --> 00:30:16,280
May pumunta ka.

842
00:30:16,280 --> 00:30:18,390

843
00:30:18,390 --> 00:30:18,470
Salamat sa -

844
00:30:18,470 --> 00:30:19,190
>> Branson: [hindi marinig] panatilihin ang mga numero.

845
00:30:19,190 --> 00:30:21,990
>> David J. MALAN: Hindi, maaari kang
panatilihin ang mga numero ng pati na rin.

846
00:30:21,990 --> 00:30:23,440
Ayos lang.

847
00:30:23,440 --> 00:30:24,100
Maayos na Natapos.

848
00:30:24,100 --> 00:30:25,300
Ayos lang.

849
00:30:25,300 --> 00:30:30,510
Kaya sabihin makita kung hindi namin ngayon ay maaaring sabihin sa maikling pangungusap
mas mabilis, at mas biswal,

850
00:30:30,510 --> 00:30:33,410
eksakto kung ano ang nangyari lamang
dito tulad ng sumusunod.

851
00:30:33,410 --> 00:30:36,510

852
00:30:36,510 --> 00:30:38,770
Pupunta ako sa sige
at makuha ang Firefox.

853
00:30:38,770 --> 00:30:41,310
Ili-link namin ito demonstration
sa website ng kurso ni.

854
00:30:41,310 --> 00:30:43,870
Java ay isang bit nakakainis upang nagtatrabaho
sa ilang mga browser mga araw na ito.

855
00:30:43,870 --> 00:30:46,760
Kaya't kung ikaw ay may-play ito sa bahay,
Napagtanto maaaring kailanganin mong gamitin ang Firefox

856
00:30:46,760 --> 00:30:47,990
upang makakuha ng mga ito gumagana.

857
00:30:47,990 --> 00:30:50,440
At kung ano ako ng pagpunta sa gawin sa mga ito
demonstration ay ang sumusunod.

858
00:30:50,440 --> 00:30:54,875
>> Sa ibaba, mayroon akong isang buong grupo ng mga
menu ng mga pagpipilian, kabilang ang isang panimula at isang

859
00:30:54,875 --> 00:30:55,840
itigil na pindutan.

860
00:30:55,840 --> 00:30:59,450
Gayundin, bilang isang tabi, tila na maging isang
bug sa mga programang ito, kung saan mo

861
00:30:59,450 --> 00:31:03,720
Hindi maaaring aktwal na makita ang panimula o itigil
pindutan maliban kung hawak mo ang Command o Alt

862
00:31:03,720 --> 00:31:06,560
plus at mag-zoom in, na pausisa
Ipinapakita sa iyo ng higit pang mga pindutan.

863
00:31:06,560 --> 00:31:09,090
Kaya lamang Para sa Iyong Impormasyon kung i-play mo
may mga ito sa bahay.

864
00:31:09,090 --> 00:31:12,870
Ngayon ako pagpunta sa i-click ang Start sa loob lamang ng
sandali, pagkatapos ng pagtukoy ng isang pagka-antala ng,

865
00:31:12,870 --> 00:31:16,810
gaya, 200 millisecond dito, lamang
upang maaari naming makita kung ano ang mangyayari.

866
00:31:16,810 --> 00:31:20,180
>> Kaya inaangkin ko na ito ay isang visualization
sa mga unang algorithm

867
00:31:20,180 --> 00:31:23,730
mga guys ginawa, bubble sort, kung saan
kami swapped mga tao pares-matalino.

868
00:31:23,730 --> 00:31:27,490
Ang key na pananaw upang ito visualization
ay ang taas ng mga bar

869
00:31:27,490 --> 00:31:30,510
Kinakatawan ang laki ng mga numero.

870
00:31:30,510 --> 00:31:32,210
Kaya ang taller ang bar, ang
Mas malaking numero.

871
00:31:32,210 --> 00:31:33,680
Mas maikli ang bar, mas maliit sa bilang.

872
00:31:33,680 --> 00:31:38,630
At kung napansin mo, kami ay pagpunta sa pamamagitan ng
ang unang pag-ulit ng mga algorithm na ito,

873
00:31:38,630 --> 00:31:42,620
pagpapalit malaki at maliit na mga numero, upang
ang maliit na bilang ang mauna at

874
00:31:42,620 --> 00:31:44,280
ang malaking bilang napupunta sa kanan.

875
00:31:44,280 --> 00:31:48,770
>> At sa lalong madaling makuha namin ang dulo ng array
ng maraming higit pa kaysa sa mga numero ng pitong, kami ay

876
00:31:48,770 --> 00:31:49,900
pagpunta upang bumalik sa simula.

877
00:31:49,900 --> 00:31:51,140
At umasa na ito.

878
00:31:51,140 --> 00:31:54,860
Sa malayong kaliwa, maliit na tao ang nangyayari
upang magpalitan sa gilid, at ito

879
00:31:54,860 --> 00:31:56,010
umuulit proseso.

880
00:31:56,010 --> 00:31:59,450
Ngayon visualization ito ay makakakuha ng mabilis
pagbubutas, kaya ipaalam sa akin sige at itigil

881
00:31:59,450 --> 00:32:04,170
ito, baguhin ang mga pagkaantala sa isang bagay magkano
mas mabilis lang upang makakuha ng ngayon, masubukan

882
00:32:04,170 --> 00:32:05,060
algorithm na ito.

883
00:32:05,060 --> 00:32:07,840
>> Kaya kahit na ko na sped up ito, ito ay
tulad ng pag-upgrade ang aking processor, pagbili

884
00:32:07,840 --> 00:32:08,580
isang bagong computer.

885
00:32:08,580 --> 00:32:12,980
Hindi ko pa sa panimula nagbago ng aking
algorithm, ngunit maaari mo talagang makakita ng higit pang

886
00:32:12,980 --> 00:32:16,800
malinaw kaysa sa mga kawani na tao, na ang malaki
mga numero ay bulubok up sa tuktok,

887
00:32:16,800 --> 00:32:20,900
at ang maliit na mga numero ay bulubok
pababa sa ilalim.

888
00:32:20,900 --> 00:32:22,390
At ngayon bagay na ito dito pinagsunod-sunod.

889
00:32:22,390 --> 00:32:25,260
At bilang isang bukod, sa mga parisukat, mayroong
ilan lang Bookkeeping doon sa

890
00:32:25,260 --> 00:32:28,010
makatulong sa iyo na bilangin kung gaano karaming mga paghahambing,
o kung gaano karaming mga mayroon swaps

891
00:32:28,010 --> 00:32:28,950
talaga ang nagawa.

892
00:32:28,950 --> 00:32:30,750
>> Well, sabihin subukan ang isa sa
ang iba pa naming nakita.

893
00:32:30,750 --> 00:32:37,116
Hayaan akong mag-click sa bubble sort dito, at
hayaan mo akong pumili, at ang buong web page

894
00:32:37,116 --> 00:32:38,936
ay isang maliit na maraming surot.

895
00:32:38,936 --> 00:32:41,155
Sabihin tanggapin ang mga panganib
at patakbuhin itong muli.

896
00:32:41,155 --> 00:32:44,560

897
00:32:44,560 --> 00:32:45,030
Nagkaroon kami pumunta.

898
00:32:45,030 --> 00:32:47,180
Kaya natin gawin seleksyon-uri.

899
00:32:47,180 --> 00:32:49,140
Hindi ko alam kung bakit ang menu
Lumilitaw banda roon.

900
00:32:49,140 --> 00:32:54,070
Tayo'y mag-zoom in upang maayos na
bug, baguhin ito sa 50.

901
00:32:54,070 --> 00:32:56,020
Ah, sabihin talagang gawin
na mas mabilis.

902
00:32:56,020 --> 00:32:59,160
Limang millisecond o kaya, at Start.

903
00:32:59,160 --> 00:33:00,470
>> Kaya ito ay seleksyon-uri.

904
00:33:00,470 --> 00:33:03,070
Kaya muli, isipin ang tungkol sa kung ano ang aming
ginawa gamit ang mga kawani na tao up dito.

905
00:33:03,070 --> 00:33:08,490
Nagpunta kami sa pamamagitan ng array at napili
ang pinakamaliit na elemento muli,

906
00:33:08,490 --> 00:33:09,250
at muli, at muli.

907
00:33:09,250 --> 00:33:11,110
Ngayon i-claim ko na noon ay pa rin medyo masama.

908
00:33:11,110 --> 00:33:15,010
Pa rin Ito ay n squared, bigyan o kumuha,
ngunit ito ay, sa tunay na mundo, isang bit

909
00:33:15,010 --> 00:33:18,280
mas mabilis, dahil nga ako ay pagkuha
bahagyang mas kaunting mga hakbang na ito sa bawat oras.

910
00:33:18,280 --> 00:33:19,800
Ngunit lamang ang pinag-uusapan natin kung ano?

911
00:33:19,800 --> 00:33:21,830
Siguro 40 o kaya bar dito?

912
00:33:21,830 --> 00:33:23,200
Hindi pinag-uusapan natin 40,000,000.

913
00:33:23,200 --> 00:33:27,430
Kaya ito ay hindi talagang i-clear sa akin na
ay sa katunayan ng isang makabuluhang pakinabang.

914
00:33:27,430 --> 00:33:32,530
>> Hayaan akong ngayon bumalik at baguhin sa aming
ikatlong algorithm, na kung saan ay piliin

915
00:33:32,530 --> 00:33:33,180
pagpapasok ng pag-uuri.

916
00:33:33,180 --> 00:33:36,380
At ngayon talaga dahil maraming surot ang
menu talagang hindi dapat pababa doon.

917
00:33:36,380 --> 00:33:40,840
Kaya ngayon kami mag-scroll back up dito
at simulan ang algorithm.

918
00:33:40,840 --> 00:33:43,270
Sigaw, magsimula at huminto.

919
00:33:43,270 --> 00:33:47,160
Kaya ito isang uri ng mga may kaakit-akit pattern
upang ito, kung saan hindi namin muli

920
00:33:47,160 --> 00:33:50,240
pagpapasok ng mga tao, o sa
kasong ito, ang mga bar sa

921
00:33:50,240 --> 00:33:52,620
kanilang mga naaangkop na lokasyon.

922
00:33:52,620 --> 00:33:55,430
At nang tapos na ito bago
Ako naka-paligid.

923
00:33:55,430 --> 00:33:58,940
Ngunit ang isang ito, masyadong, sa teorya,
ay pa rin n squared.

924
00:33:58,940 --> 00:34:01,430
>> Kaya sabihin makita kung hindi namin sabihin sa maikling pangungusap
ang mga tulad ng mga sumusunod.

925
00:34:01,430 --> 00:34:04,750
Pupuntahan ko sige lang at bigyan
amin ang uri ng isang pangkaraniwang paraan ng pakikipag-usap

926
00:34:04,750 --> 00:34:08,489
tungkol sa mga bagay na ito, hayaan mo akong ipakilala
lamang ng kaunti ng pagtatanda dito.

927
00:34:08,489 --> 00:34:12,480
Ikaw ay tungkol sa upang makita ang isang bagay na tinatawag na malaki
O, sapagkat ito ay literal isang malaking

928
00:34:12,480 --> 00:34:16,320
O. At ito ay isang paraan na ang isang computer
siyentipiko o isang dalubhasa sa matematika kahit na gumagamit ng

929
00:34:16,320 --> 00:34:19,230
upang ilarawan ang oras
ng ilang mga algorithm.

930
00:34:19,230 --> 00:34:21,400
Ilang hakbang na ang ibig talagang tumagal?

931
00:34:21,400 --> 00:34:25,080
>> Ngayon Pupunta ako sa sarili ko mapahiya sa
ang aking sulat-kamay dito sa loob lamang ng ilang sandali.

932
00:34:25,080 --> 00:34:29,020
Ngunit ipaalam sa akin sige at sabihin na
ito ang magiging malaking O paglipas dito.

933
00:34:29,020 --> 00:34:33,610
At hayaan mo akong ipakilala ang isa pang
simbolo, isang kabisera wakas.

934
00:34:33,610 --> 00:34:37,080
Omega ay magiging mga tapat,
talaga, ng malaking O. Sapagkat malaki O

935
00:34:37,080 --> 00:34:40,790
ibig sabihin, sa pinakamasama kaso, kung magkano ang oras
algorithm ay maaaring tumagal ng ilang mga, sa

936
00:34:40,790 --> 00:34:43,480
mga tuntunin ng n, wakas ay pagpunta sa
maging gaano karaming oras maaari itong

937
00:34:43,480 --> 00:34:45,409
kumuha sa ang pinakamahusay na kaso.

938
00:34:45,409 --> 00:34:48,090
At kami makita kung ano ang ibig sabihin namin sa pamamagitan ng
pinakamahusay na kaso sa loob lamang ng ilang sandali.

939
00:34:48,090 --> 00:34:49,940
>> Kaya natin simulan ang isang bagay na simple.

940
00:34:49,940 --> 00:34:54,719
Hayaan akong magsimula sa isang linear paghahanap.

941
00:34:54,719 --> 00:34:55,679
Kaya hindi pag-uuri.

942
00:34:55,679 --> 00:34:58,000
Susubukan naming itawag sa linear paghahanap.

943
00:34:58,000 --> 00:35:01,140
At ngayon, gumawa ng isang maliit na
talahanayan out ng ito.

944
00:35:01,140 --> 00:35:06,600
At ngayon, sa kaso ng mga linear na paghahanap,
sa pinakamasama kaso, kung ilang mga hakbang ay

945
00:35:06,600 --> 00:35:11,770
ito pagpunta sa tumagal sa akin upang makahanap ng isang
bilang ng mga arbitrary choice?

946
00:35:11,770 --> 00:35:14,540
At mayroong n kabuuang mga mga pinto
o n kabuuang numero.

947
00:35:14,540 --> 00:35:15,940
Pinakamahina ang kaso.

948
00:35:15,940 --> 00:35:18,800
Gaano karaming mga hakbang na ito ako pagpunta upang magkaroon ng upang
gawin upang mahanap ang numero ng 50 sa isang array

949
00:35:18,800 --> 00:35:20,830
ng n mga pinto?

950
00:35:20,830 --> 00:35:21,410
At kung bakit?

951
00:35:21,410 --> 00:35:23,680
Dahil maaari itong maging ang lahat ng mga
paraan sa ibabaw papunta sa dulo.

952
00:35:23,680 --> 00:35:27,120
Kaya halos tulad Jennifer nakatagpo, ang
numero 50 ay ang lahat ng mga paraan sa paglipas, kaya in

953
00:35:27,120 --> 00:35:30,760
ang pinakamasama kaso linear na sa paghahanap
ay malaki mga O ng n, makakakita namin sasabihin.

954
00:35:30,760 --> 00:35:33,430
>> Paano ang tungkol sa mga pinakamahusay na kaso,
kung makakuha ka talagang mapalad?

955
00:35:33,430 --> 00:35:36,200
Lamang Ito ay pagpunta sa tumagal ng isang hakbang,
o isang pare-pareho ang bilang ng mga hakbang.

956
00:35:36,200 --> 00:35:37,830
Kaya namin ilarawan na bilang 1.

957
00:35:37,830 --> 00:35:39,010
So na ito ay medyo magandang.

958
00:35:39,010 --> 00:35:41,210
Ngayon ano kung namin ginawang isang bagay
i binary paghahanap?

959
00:35:41,210 --> 00:35:43,860

960
00:35:43,860 --> 00:35:47,846
Kaya binary paghahanap, sa pinakamalala
kaso, kinuha kung magkano ang oras?

961
00:35:47,846 --> 00:35:49,250
>> [INTERPOSING tinig]

962
00:35:49,250 --> 00:35:51,310
>> David J. MALAN: Kaya talaga, ako
narinig ito sa isang lugar na ilang.

963
00:35:51,310 --> 00:35:56,390
Kaya talaga ito ay mag-log n, bigyan o kumuha,
dahil bilang hinati namin ang listahan sa kalahati

964
00:35:56,390 --> 00:36:00,730
muli, at muli, at muli, nagpapaumanhin kami magagawang
upang mahanap, sa huli, ang halaga,

965
00:36:00,730 --> 00:36:04,750
kung ito doon, pero may catch a.

966
00:36:04,750 --> 00:36:08,590
Ano ang palagay na kami ay may sa
mang-ahas para sa binary paghahanap?

967
00:36:08,590 --> 00:36:09,700
Mayroon na pinagsunod-sunod.

968
00:36:09,700 --> 00:36:12,770
Hindi Ito ay naka pinagbukud-bukod, maaari mong hatiin ang bagay na
sa kalahati muli at muli, at ikaw

969
00:36:12,770 --> 00:36:15,490
Maaari pumunta sa kaliwa, at maaari kang pumunta karapatan, at
Maaari kang pumunta kaliwa at kanan, ngunit ikaw ay

970
00:36:15,490 --> 00:36:18,070
hindi pagpunta upang mahanap ang mga elemento kung
listahan ay hindi pinagsunod-sunod, dahil

971
00:36:18,070 --> 00:36:18,790
baka makaligtaan ito.

972
00:36:18,790 --> 00:36:22,120
Sapagkat ang iyong mga hyuristiko, para pagpunta kaliwa
o pakanan ay ng pagpunta sa mai-flawed kung ito ay

973
00:36:22,120 --> 00:36:23,420
sa katunayan hindi pinagsunod-sunod.

974
00:36:23,420 --> 00:36:26,110
Kaya mayroong isang uri ng isang nakatagong gastos
sa paggamit ng isang bagay na katulad nito.

975
00:36:26,110 --> 00:36:29,250
>> Ngayon, sabihin pumunta sa aming pag-uuri
algorithm hindi naghahanap -

976
00:36:29,250 --> 00:36:31,140
oh, talaga natin pumunta sa blangko.

977
00:36:31,140 --> 00:36:33,190
Binary paghahanap sa pinakamahusay na kaso?

978
00:36:33,190 --> 00:36:36,290
Ito ay din 1 kung ito lamang ang mangyayari sa maging
sa pinakadulo gitna ng array, o

979
00:36:36,290 --> 00:36:37,810
sa gitna ng aklat telepono.

980
00:36:37,810 --> 00:36:39,710
Ngayon ipaalam sa ni gawin bubble-uri-uriin.

981
00:36:39,710 --> 00:36:42,570
Kaya muli, na namin ngayon ng pagpasok ng
uri, hindi ang mga paghahanap.

982
00:36:42,570 --> 00:36:47,220
>> Sa pinakamasama kaso, kung gaano karaming mga hakbang na kami
claim na bubble sort pupuntahan tumagal?

983
00:36:47,220 --> 00:36:48,410
n nakalapat.

984
00:36:48,410 --> 00:36:49,200
Kaya pupuntahan ko upang gumuhit na.

985
00:36:49,200 --> 00:36:51,710
Ooh, ang aking sulat-kamay hitsura kahit na mas masahol pa
kapag ito ay inaasahang na malaki.

986
00:36:51,710 --> 00:36:52,510
Ayos lang.

987
00:36:52,510 --> 00:36:53,570
Kaya na n squared.

988
00:36:53,570 --> 00:36:59,460
At sa pinakamahusay na kaso ng bubble sort,
kung gaano karaming mga hakbang na ito ng pagpunta sa tumagal?

989
00:36:59,460 --> 00:37:00,980
1, Narinig ko.

990
00:37:00,980 --> 00:37:01,760
>> Tagapagsalita 1: n.

991
00:37:01,760 --> 00:37:03,286
>> David J. MALAN: n, Narinig ko.

992
00:37:03,286 --> 00:37:04,200
>> Tagapagsalita 1: 2.

993
00:37:04,200 --> 00:37:05,010
>> David J. MALAN: 2, Narinig ko.

994
00:37:05,010 --> 00:37:06,670
Huwag akong marinig 3?

995
00:37:06,670 --> 00:37:07,080
Ayos lang.

996
00:37:07,080 --> 00:37:11,390
Kaya ko nalaman 1 n, 2, ngunit sabihin pick
bukod ng hindi bababa sa ang unang ng mga

997
00:37:11,390 --> 00:37:12,330
mga mungkahi, 1.

998
00:37:12,330 --> 00:37:15,370
Ito ay hindi isang masamang likas na hilig, sapagkat ito
uri ng sumusunod sa isang pattern dito.

999
00:37:15,370 --> 00:37:19,670
Ngunit kung ito lamang ay tumatagal ng 1 hakbang, kung paano sa
mundo kaya kong i-claim na ang listahan

1000
00:37:19,670 --> 00:37:22,900
ay pinagsunod-sunod, dahil kung lamang ako pinapayagan
gumawa ng 1 hakbang, kung gaano karaming mga elemento

1001
00:37:22,900 --> 00:37:25,230
maaari ko talagang tingnan upang matiyak?

1002
00:37:25,230 --> 00:37:28,270
Well, may 1, na nangangahulugan na n
minus 1 elemento na maaaring maging out sa

1003
00:37:28,270 --> 00:37:31,310
pagkakasunud-sunod, at lang ako sa ng pagpunta sa pananampalataya pagkatapos ng
pagtingin sa 1 elemento na ang

1004
00:37:31,310 --> 00:37:31,850
bagay ay pinagsunod-sunod.

1005
00:37:31,850 --> 00:37:33,930
So 1 ay hindi itama dito.

1006
00:37:33,930 --> 00:37:35,710
Kaya Nagnais ng pinakamababang, kung gaano karaming
ang mayroon ako upang tumingin sa?

1007
00:37:35,710 --> 00:37:36,680
>> [INTERPOSING tinig]

1008
00:37:36,680 --> 00:37:40,160
>> David J. MALAN: n minus 1, o talagang,
n, dahil kailangan kong tumingin sa bawat

1009
00:37:40,160 --> 00:37:42,190
elemento upang matiyak na
hindi ito out ng order.

1010
00:37:42,190 --> 00:37:44,750
Ngunit muli, kailangan namin pagsunud-sunurin ng wave aming
mga kamay sa mas maliit na mga numero at

1011
00:37:44,750 --> 00:37:47,100
ipinapalagay na, bilang n nakukuha ng malaki, ang mga ito ay
hindi kawili-wili pa rin.

1012
00:37:47,100 --> 00:37:48,380
Kaya na bubble sort.

1013
00:37:48,380 --> 00:37:49,830
At ngayon, sabihin gawin ang mga nakaraang dalawang.

1014
00:37:49,830 --> 00:37:53,520
Pinili uri, at pagkatapos ay bibigyan namin ng
gawin insertion sort.

1015
00:37:53,520 --> 00:37:57,160
At pagkatapos kami ay pumutok ang iyong
isip may bagay magkano

1016
00:37:57,160 --> 00:37:58,926
mas mahusay kaysa sa lahat ng mga ito.

1017
00:37:58,926 --> 00:38:00,410
Ayos lang.

1018
00:38:00,410 --> 00:38:04,700
>> Ano ang pinakamasamang sitwasyon tumatakbo
oras ng pagpili-uri?

1019
00:38:04,700 --> 00:38:05,680
>> Tagapagsalita 4: n squared.

1020
00:38:05,680 --> 00:38:06,710
>> David J. MALAN: n square, ako pagdinig.

1021
00:38:06,710 --> 00:38:09,790
Ngunit bakit n nakalapat, intuitively?

1022
00:38:09,790 --> 00:38:11,170
>> Tagapagsalita 4: Dahil lang namin ginawa ito.

1023
00:38:11,170 --> 00:38:12,260
>> David J. MALAN: Dahil lang namin ginawa ito.

1024
00:38:12,260 --> 00:38:12,550
OK.

1025
00:38:12,550 --> 00:38:13,380
Magandang sagot.

1026
00:38:13,380 --> 00:38:16,660
Ngunit intuitively, bakit ang seleksyon
sort n squared?

1027
00:38:16,660 --> 00:38:18,980
Ano ang mayroon kami na gawin
muli at muli?

1028
00:38:18,980 --> 00:38:22,570
Kinailangan naming panatilihin ang pag-scan sa pamamagitan ng, mga
mo na ang pinakamaliit na, ikaw ang

1029
00:38:22,570 --> 00:38:24,020
pinakamaliliit na, ikaw ang pinakamaliit.

1030
00:38:24,020 --> 00:38:27,480
At ipinagkaloob, nagawa naming gumawa ng n
hakbang, pagkatapos n minus 1, pagkatapos n minus 2.

1031
00:38:27,480 --> 00:38:30,700
Ngunit kung ikaw uri ng magdagdag ng mga lahat up,
o dalhin ito sa paniniwala na ang Idinagdag ko na

1032
00:38:30,700 --> 00:38:34,810
up ang mga ito sa advance, makakuha ng mga namin humigit-kumulang n
squared minus ang ilang mga mas maliit na mga numero ng.

1033
00:38:34,810 --> 00:38:36,730
Kaya pupuntahan ko tawagan n ito squared.

1034
00:38:36,730 --> 00:38:39,530
Ngunit sa pagpili-uri sa ang pinakamahusay na
kaso, kung gaano karaming mga hakbang na ito

1035
00:38:39,530 --> 00:38:40,632
pagpunta sa tumagal sa akin?

1036
00:38:40,632 --> 00:38:41,840
>> Tagapagsalita 5: [hindi marinig]

1037
00:38:41,840 --> 00:38:44,350
>> David J. MALAN: Ito ay sa kasamaang-palad
pa rin n squared, tama?

1038
00:38:44,350 --> 00:38:49,590
Dahil kung ako ang pagpili sa mga pinakamaliliit
elemento, at nagkaroon kami ng pitong mga tao dito,

1039
00:38:49,590 --> 00:38:53,280
Ko lang alam, sa sandaling nakuha ko sa pinakadulo
end, na aking nakita na ang pinakamaliit na

1040
00:38:53,280 --> 00:38:55,670
numero, nasaan man siya o
maaaring siya ay naging.

1041
00:38:55,670 --> 00:38:58,820
Ngunit paano ko mahanap ang susunod na
pinakamaliliit number?

1042
00:38:58,820 --> 00:39:00,160
Mayroon akong gawin ang isa pang pass.

1043
00:39:00,160 --> 00:39:04,810
Kaya't sa pinakamahusay na kaso, kung ano ang
input upang seleksyon-uri?

1044
00:39:04,810 --> 00:39:07,830
Ito ay isang mayroon listahan-uri-uriin, ang bilang na ng isa,
bilang dalawang, ang bilang na tatlo, bilang apat.

1045
00:39:07,830 --> 00:39:08,600
Ngunit Ako ay isang computer.

1046
00:39:08,600 --> 00:39:10,190
Maaari lamang akong tumingin sa isa
bagay sa isang pagkakataon.

1047
00:39:10,190 --> 00:39:12,465
Hindi ako makapag-sort ng tumagal ng isang hakbang
bumalik tulad ng isang tao at sabihing,

1048
00:39:12,465 --> 00:39:14,030
ooh, ito mukhang tama.

1049
00:39:14,030 --> 00:39:17,580
>> Maaari lamang akong dinggin kawastuhan sa
pagpili-uri sa pamamagitan ng pagpili ng

1050
00:39:17,580 --> 00:39:18,370
pinakamaliliit na numero.

1051
00:39:18,370 --> 00:39:21,390
Ngunit kahit na mahanap ko ang numero ng isa muna,
kung hindi ko alam kung anumang bagay tungkol sa

1052
00:39:21,390 --> 00:39:24,460
ang iba pang mga numero, na gagawin ko hindi, lahat ko
malaman na ang ko na ang nai-ipinasa array isang

1053
00:39:24,460 --> 00:39:27,930
o isang hanay ng mga pinto sa likod na kung saan ay
mga numero, ang tanging paraan na alam ko na ang isa

1054
00:39:27,930 --> 00:39:28,680
ay ang pinakamaliit?

1055
00:39:28,680 --> 00:39:32,440
Kung nakukuha ko lahat ng paraan dito at nauunawaan,
sumpain, ang isa ay sa katunayan na ang pinakamaliit na.

1056
00:39:32,440 --> 00:39:34,870
>> Ngunit paano ko nang tukuyin na
dalawa ang susunod na pinakamaliit?

1057
00:39:34,870 --> 00:39:38,350
Sa pamamagitan ng paggawa ng parehong kawalang-kaya
muli at muli.

1058
00:39:38,350 --> 00:39:42,210
Kaya sa wakas, na may pagpapasok ng uri,
paano, sa pinakamasama kaso,

1059
00:39:42,210 --> 00:39:44,990
ang sabihin namin ito ay gumaganap?

1060
00:39:44,990 --> 00:39:49,100
Ito masyadong ay n squared.

1061
00:39:49,100 --> 00:39:53,020
At kung paano tungkol sa ang pinakamahusay na kaso?

1062
00:39:53,020 --> 00:39:56,282
Susubukan naming umalis na bilang isang cliffhanger.

1063
00:39:56,282 --> 00:40:00,090
Susubukan naming fill in na blangko ang susunod na oras,
ngunit unang hayaan mo akong magpanukala na namin

1064
00:40:00,090 --> 00:40:02,620
sa panimula gawin mas mahusay kaysa sa
lahat ng mga ito, ang lahat ng karapatan?

1065
00:40:02,620 --> 00:40:05,220
>> Kaya sa tingin para sa iyong sarili kung ano ang pagpapasok ng
-uri-uriin ang nangyayari upang maging.

1066
00:40:05,220 --> 00:40:06,910
Well, na noon ay hindi masyadong dramatic,
dahil ako ang isa lamang

1067
00:40:06,910 --> 00:40:08,970
na nakita ang pagbabago.

1068
00:40:08,970 --> 00:40:09,620
Wow.

1069
00:40:09,620 --> 00:40:10,420
OK.

1070
00:40:10,420 --> 00:40:12,615
Kaya dito kami ay may isang medyo
ibang pagpapakita.

1071
00:40:12,615 --> 00:40:16,580
Kung ako mag-zoom in dito, makikita mo na sa
sa kaliwa mayroon kaming bubble sort, sa

1072
00:40:16,580 --> 00:40:20,740
gitna mayroon kaming seleksyon uri, at sa
dulong kanan, mayroon kaming isang bagay namin

1073
00:40:20,740 --> 00:40:23,380
hindi Tiningnan pa
tinatawag na pagsamahin ang pag-uuri.

1074
00:40:23,380 --> 00:40:26,080
Subalit isaalang-alang kung ano ang aming nakapunta
paggawa dito kaya malayo ngayon.

1075
00:40:26,080 --> 00:40:29,200
Kapag Jennifer unang dumating up sa entablado,
kami nagpunta sa pamamagitan ng array ng mga numero

1076
00:40:29,200 --> 00:40:33,750
muli, at muli, na may linear paghahanap,
at kami nakakuha linear tumatakbo oras, malaki O

1077
00:40:33,750 --> 00:40:35,100
ng n, kaya na magsalita.

1078
00:40:35,100 --> 00:40:41,000
>> Kapag kami ngayon isaalang-alang ang unang linggo ng
klase, kapag kami ay hatiin at lupigin,

1079
00:40:41,000 --> 00:40:43,740
at kami ang phone book pansiwang,
at Jennifer, at kami sama-sama

1080
00:40:43,740 --> 00:40:47,500
magagamit na key pananaw, na noon ay sa
ulitin ang iyong sarili muli at muli sa pamamagitan ng

1081
00:40:47,500 --> 00:40:50,930
sa paano pa man ibinabato ang layo ng, ibinabato ang layo ng,
itsa, kalahati ng mga problema, o

1082
00:40:50,930 --> 00:40:55,320
Sa pangkalahatan, paghahati ng problema sa kalahati,
at pagkatapos ay pagpapagamot ng mga mas maliit na piraso ng

1083
00:40:55,320 --> 00:40:59,630
ang problema bilang conceptually katumbas
upang ang iba pang mga, namin sa paanuman ginawa

1084
00:40:59,630 --> 00:41:00,910
sa panimula mas mahusay.

1085
00:41:00,910 --> 00:41:04,720
Ngunit na may bubble-uri-uriin, na may mga seleksyon
uri, na may pagpapasok ng uri, kami nag maaari

1086
00:41:04,720 --> 00:41:06,560
walang ganoong mga pananaw na Jennifer ginawa.

1087
00:41:06,560 --> 00:41:10,220
Kami medyo magkano lamang lumakad pabalik at
nakalahad isang buo magsikisikan ng beses na, at namin

1088
00:41:10,220 --> 00:41:12,650
tweaked bagay Medyo, pagpapalit
sa ayos na ito, siguro

1089
00:41:12,650 --> 00:41:13,730
pagpasok o pagpili.

1090
00:41:13,730 --> 00:41:16,950
Ngunit sa pagtatapos ng araw, ako ginawa ng maraming isang
ng nakahihiya walking papunta at pabalik.

1091
00:41:16,950 --> 00:41:21,160
Kami ay hindi talaga pakikinabangan ang isang bagay
matalino tulad ng Jennifer ginawa tulad ng paghahati

1092
00:41:21,160 --> 00:41:22,040
at mapanakop.

1093
00:41:22,040 --> 00:41:25,620
>> Kaya pagsamahin ang uri, sa pamamagitan ng kaibahan, na aming
hindi makikita hanggang sa susunod na linggo, ito ay pagpunta

1094
00:41:25,620 --> 00:41:29,540
upang masulit na key ideya sa pamamagitan ng paghati
ang input, at pagkatapos ay paghati, at pagkatapos ay

1095
00:41:29,540 --> 00:41:30,580
paghati, at pagkatapos ay paghati.

1096
00:41:30,580 --> 00:41:34,590
At sa bawat pag-ulit ng na loop,
pag-uuri sa kaliwa kalahati, at ang karapatan

1097
00:41:34,590 --> 00:41:38,200
kalahati, at pagkatapos ay sa kaliwa kalahati ng kaliwang kalahati,
at ang kanang kalahati ng kaliwa, at pagkatapos ay

1098
00:41:38,200 --> 00:41:40,990
sa kaliwang kalahati ng kanang kalahati, at
ang karapatan kalahati ng kanang kalahati.

1099
00:41:40,990 --> 00:41:42,840
At paulit-ulit na muli at muli.

1100
00:41:42,840 --> 00:41:46,170
>> So makikita mo ang biswal, ngunit ito
ay kung ano ang naghihintay sa amin sa susunod na linggo.

1101
00:41:46,170 --> 00:41:49,760
At sa pangkalahatan, kapag sa tingin namin ang kaunti
bit na mas mahirap sa anumang naturang problema.

1102
00:41:49,760 --> 00:41:52,435

1103
00:41:52,435 --> 00:41:57,970
Kami n squared sa kaliwa, n
squared sa gitna, at n

1104
00:41:57,970 --> 00:41:59,400
mag-log n sa kanan.

1105
00:41:59,400 --> 00:42:00,590
Kaya mayroong iyong tunay na cliffhanger.

1106
00:42:00,590 --> 00:42:02,040
Gagamitin namin ang nakikita mo sa Lunes.

1107
00:42:02,040 --> 00:42:05,163
>> [Palakpakan]