1
00:00:00,000 --> 00:00:11,100
>> [Muzikavimo]

2
00:00:11,100 --> 00:00:11,490
>> Davidas J. Malan: Gerai.

3
00:00:11,490 --> 00:00:12,170
Taigi sveikiname atgal.

4
00:00:12,170 --> 00:00:15,180
Tai CS50 ir yra
Savaitės trijų pabaiga.

5
00:00:15,180 --> 00:00:17,770
>> Taigi prisiminti per pastaruosius keletą savaičių,
mes buvo išleisti gana šiek tiek apie

6
00:00:17,770 --> 00:00:20,820
laikas nuo C į programavimą, nuo sintaksės.

7
00:00:20,820 --> 00:00:24,680
Ir tai visai normalu, jei jūs vis dar
kovoja su problemą, 2, turi būti

8
00:00:24,680 --> 00:00:25,950
beldžiasi savo galvą į sieną.

9
00:00:25,950 --> 00:00:28,310
Tai paslaptingas atrodantys klaidų pranešimai
ir klaidų, kad jūs

10
00:00:28,310 --> 00:00:29,220
negali visiškai persekioti žemyn.

11
00:00:29,220 --> 00:00:32,310
Nes tikri, kad tik
kelių savaičių jums pažvelgti atgal

12
00:00:32,310 --> 00:00:35,930
dalykų, pavyzdžiui, Cezaris, ir [? V-genair,?]
gal net crack, ir

13
00:00:35,930 --> 00:00:40,050
suvokti, kaip toli jūs atėjote
per trumpą laiką.

14
00:00:40,050 --> 00:00:43,670
Taigi, jei tai paguos,
pakabinti ten dabar.

15
00:00:43,670 --> 00:00:46,610
>> Šiandien, nors mes pradėsime perėjimas
dalykų aukštesnį lygį.

16
00:00:46,610 --> 00:00:49,820
Ir mes pradedame laiko savaime suprantamu dalyku, kad
jūs žinote, kaip programa, arba

17
00:00:49,820 --> 00:00:52,090
jau ištakas
kad komforto lygį.

18
00:00:52,090 --> 00:00:56,520
Ir mes pradėsime svarstyti, kaip galime
eiti apie projektuojant programas daugiau

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

20
00:00:57,440 --> 00:01:01,090
Kaip mes galime eiti apie optimizavimą
efektyvumas mūsų algoritmai ir

21
00:01:01,090 --> 00:01:03,110
paprastai problemoms spręsti
įdomių problemų.

22
00:01:03,110 --> 00:01:06,850
Ir pradeda savaime suprantamu dalyku, kad
jei norime, galime koduoti iki bet

23
00:01:06,850 --> 00:01:08,350
pavyzdžių mes turime omenyje.

24
00:01:08,350 --> 00:01:11,430
Taigi šiandien, mes neturime liesti klaviatūrą
bet kodo forma.

25
00:01:11,430 --> 00:01:15,150
Tai bus daug aukštesnio lygio, ir
galiausiai apie problemų sprendimo.

26
00:01:15,150 --> 00:01:20,490
>> Taigi, norint gauti iki to taško, leiskite man pasiūlyti
kad šių septynių

27
00:01:20,490 --> 00:01:24,290
stačiakampiai atstovauja septynias duris, už
kurie yra visa krūva

28
00:01:24,290 --> 00:01:26,340
numerius, tarp kurių yra skaičius 50.

29
00:01:26,340 --> 00:01:30,470
Leiskite projektą, tai apie tai
ekranas čia taip pat.

30
00:01:30,470 --> 00:01:36,770
Ir siūlo, kad mums reikia Pasisiūlykite
padėti rasti man priešais skaičių

31
00:01:36,770 --> 00:01:38,140
Internetas čia pamatyti.

32
00:01:38,140 --> 00:01:40,755
Nagi ", remiantis rausva.

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

34
00:01:43,050 --> 00:01:43,930
Koks tavo vardas?

35
00:01:43,930 --> 00:01:44,850
>> JENNIFER: [nesigirdi]

36
00:01:44,850 --> 00:01:45,170
>> Davidas J. Malan: Atsiprašau?

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

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

39
00:01:46,390 --> 00:01:46,980
Visos teisės Jennifer.

40
00:01:46,980 --> 00:01:47,630
Malonu jus matyti.

41
00:01:47,630 --> 00:01:48,370
Ateik iki.

42
00:01:48,370 --> 00:01:52,430
Taigi tai čia yra septynios durys, ir kas
Norėčiau jums reikia padaryti, mums čia,

43
00:01:52,430 --> 00:01:56,560
prieš visus savo klasiokų,
yra mus rasti skaičių, 50.

44
00:01:56,560 --> 00:02:00,860
Norėdami rasti skaičių, galite žvilgtelėti už
nors iš šių durų, tiesiog paliesdami

45
00:02:00,860 --> 00:02:03,030
vieną iš durų, ir jis
atskleis jo numerį.

46
00:02:03,030 --> 00:02:06,080
Ir pažiūrėkime, kaip greitai jūs
Mus rasite skaičių, 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
Gražiai padaryta.

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

55
00:02:18,040 --> 00:02:19,906
Audringi plojimai už Jennifer.

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

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

58
00:02:22,320 --> 00:02:25,254
Taigi, kas buvo jūsų strategija
rasti skaičių, 50?

59
00:02:25,254 --> 00:02:27,222
>> JENNIFER: Hm, aš maniau, gal jei -

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

61
00:02:27,714 --> 00:02:28,206
>> Davidas J. Malan: O.

62
00:02:28,206 --> 00:02:29,630
Duok vieną sekundę.

63
00:02:29,630 --> 00:02:32,420
Taigi buvo jūsų strategija
rasti skaičių, 50?

64
00:02:32,420 --> 00:02:34,760
>> JENNIFER: Taigi aš tiesiog pradėti
pradeda rodyti, ką Pirmasis numeris

65
00:02:34,760 --> 00:02:38,590
buvo, ir tada aš pagalvojau, gal jei
jie rūšiuojami, aš tiesiog laikyti

66
00:02:38,590 --> 00:02:39,970
paliesdami aukščiau?

67
00:02:39,970 --> 00:02:40,140
>> Davidas J. Malan: Gerai.

68
00:02:40,140 --> 00:02:42,910
Ir mes, atrodo, kad rado
kad turi būti atveju.

69
00:02:42,910 --> 00:02:45,670
Nors galime žievelės atgal sluoksniai
tik šiek tiek, ir jūs norite eiti

70
00:02:45,670 --> 00:02:47,640
į priekį ir atskleisti kitas duris
Jums galėjo pasirinkti?

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

72
00:02:50,400 --> 00:02:51,712
>> JENNIFER: O, brangusis.

73
00:02:51,712 --> 00:02:53,128
>> Davidas J. Malan: Ak.

74
00:02:53,128 --> 00:02:54,280
>> JENNIFER: Taigi aš tiesiog pasisekė.

75
00:02:54,280 --> 00:02:55,270
>> Davidas J. Malan: Taigi jūs pasisekė.

76
00:02:55,270 --> 00:02:55,710
Gerai.

77
00:02:55,710 --> 00:02:56,795
Taigi nėra blogai.

78
00:02:56,795 --> 00:02:58,750
Bet tai įdomu
įžvalga, tiesa?

79
00:02:58,750 --> 00:03:01,870
Jei manoma, ir tu gauti,
tiesą sakant, šiek tiek pasisekė ten.

80
00:03:01,870 --> 00:03:05,350
Bet jei daroma prielaida, kad numeriai buvo
rūšiuojami, galite tiksliau

81
00:03:05,350 --> 00:03:08,750
, kaip tai įtakojo
Jūsų elgesys?

82
00:03:08,750 --> 00:03:11,715
>> JENNIFER: Taigi, jei jie buvo sutvarkyti, aš
maniau gal mažiausio iki didžiausio.

83
00:03:11,715 --> 00:03:11,970
>> Davidas J. Malan: Gerai.

84
00:03:11,970 --> 00:03:15,260
>> JENNIFER: Arba, jei tai galų gale buvo
tikrai didelis, tada didžiausiojo iki mažiausiojo.

85
00:03:15,260 --> 00:03:15,540
>> Davidas J. Malan: Gerai.

86
00:03:15,540 --> 00:03:18,170
Taigi didžiausiojo iki mažiausiojo, arba
mažiausio iki didžiausio.

87
00:03:18,170 --> 00:03:21,990
Bet leiskite man pasiūlyti, tarkime, jūs turėjote
Dotarłeś nelaimingas, ir manyti, kad jie

88
00:03:21,990 --> 00:03:26,840
nebuvo, tiesą sakant, rūšiuojami, kiek
šios durys gali jums turėjo žvilgtelėti

89
00:03:26,840 --> 00:03:28,590
atsilieka ir pačiu blogiausiu atveju?

90
00:03:28,590 --> 00:03:29,860
>> JENNIFER: Viskas apie juos.

91
00:03:29,860 --> 00:03:30,420
>> Davidas J. Malan: Viskas apie juos.

92
00:03:30,420 --> 00:03:31,740
Taigi, galime apibendrinti, kad n.

93
00:03:31,740 --> 00:03:34,790
Būna, kad 7, bet tegul daugiau
paprastai pasakyti, ten n durelės

94
00:03:34,790 --> 00:03:35,650
ekranas čia.

95
00:03:35,650 --> 00:03:40,110
Taigi, blogiausiu atveju, jums reikės
ieškoti užnugario 7 durimis arba n durys.

96
00:03:40,110 --> 00:03:44,140
Ir taip tai tikrai yra, tai tiek
Sėkmės šiandien, bet tai tikrai linijinis

97
00:03:44,140 --> 00:03:46,440
algoritmas rūšių, net jei
buvo rūšies praleidžiant aplink.

98
00:03:46,440 --> 00:03:47,080
Ar tai teisinga?

99
00:03:47,080 --> 00:03:47,500
>> JENNIFER: Taip.

100
00:03:47,500 --> 00:03:50,000
>> Davidas J. Malan: Na, leiskite man pamatyti, jei jūsų
strategijos pokyčiai, jei aš perkelti mus į

101
00:03:50,000 --> 00:03:52,190
Mūsų antrasis pavyzdys čia
7 skirtingų durys.

102
00:03:52,190 --> 00:03:55,240
Pačius numerius, tačiau tai
laiko jie yra rūšiuojami.

103
00:03:55,240 --> 00:03:58,350
Kokia jūsų strategija čia bus,
bando įdėti iš savo proto, kas

104
00:03:58,350 --> 00:03:59,310
kiti skaičiai buvo -

105
00:03:59,310 --> 00:03:59,930
>> JENNIFER: Gerai.

106
00:03:59,930 --> 00:04:02,290
>> Davidas J. Malan: - anksčiau?

107
00:04:02,290 --> 00:04:03,180
>> JENNIFER: Pradėkime
su pirmuoju.

108
00:04:03,180 --> 00:04:03,540
>> Davidas J. Malan: Gerai.

109
00:04:03,540 --> 00:04:05,190
Pradėti su pirmąja.

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

111
00:04:05,960 --> 00:04:08,810
Dabar, jei jūs ketinate eiti, ir kodėl?

112
00:04:08,810 --> 00:04:10,040
>> JENNIFER: 4 yra tikrai maža.

113
00:04:10,040 --> 00:04:12,500
Taigi, jei jie tarsi galbūt mažiausias
iki didžiausio, ji turėtų

114
00:04:12,500 --> 00:04:13,290
būti du kartus, ir -.

115
00:04:13,290 --> 00:04:13,670
>> Davidas J. Malan: Gerai.

116
00:04:13,670 --> 00:04:15,990
Pažiūrėkime, kuris manote?

117
00:04:15,990 --> 00:04:19,050
>> JENNIFER: Išbandykite naujausia.

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

119
00:04:19,500 --> 00:04:20,880
>> Davidas J. Malan: Labai gražiai padaryta.

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

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

122
00:04:23,010 --> 00:04:24,310
>> Davidas J. Malan: Gerai.

123
00:04:24,310 --> 00:04:26,790
Taigi jūs iš tikrųjų daro tai
siaubingai, nes jūs

124
00:04:26,790 --> 00:04:27,700
tai daro labai gerai.

125
00:04:27,700 --> 00:04:31,150
Kuris palieka mums negali
padaryti tam tikrus dalykus.

126
00:04:31,150 --> 00:04:32,565
Taigi pabandykime įvirsta čia.

127
00:04:32,565 --> 00:04:34,560
>> JENNIFER: Gerai.

128
00:04:34,560 --> 00:04:35,980
>> Davidas J. Malan: Labai gerai
padaryta, vis dėlto.

129
00:04:35,980 --> 00:04:39,060
Taigi jums pradėti iš pradžių,
Jūs matė, kad tai buvo 4, tada jūs

130
00:04:39,060 --> 00:04:40,240
persikėlė į pabaigą.

131
00:04:40,240 --> 00:04:42,320
Bet manau, kad tu negali gauti pasisekė
ten, ir tarkime 50

132
00:04:42,320 --> 00:04:42,890
buvo kažkur kitur.

133
00:04:42,890 --> 00:04:46,190
Kas jūsų Trečias žingsnis buvo?

134
00:04:46,190 --> 00:04:47,680
>> JENNIFER: Grįžti į pradžią.

135
00:04:47,680 --> 00:04:48,320
>> Davidas J. Malan: Grįžti atgal
į pradžią.

136
00:04:48,320 --> 00:04:51,320
Gerai, kad jūs tai jau palietė
šios durys, kuris buvo 8.

137
00:04:51,320 --> 00:04:51,660
Gerai.

138
00:04:51,660 --> 00:04:52,650
Taigi, tai ne 50.

139
00:04:52,650 --> 00:04:55,380
Kur turite pažvelgė toliau?

140
00:04:55,380 --> 00:04:56,720
>> JENNIFER: Jei aš ne
žinau, kad jie rūšiuojami.

141
00:04:56,720 --> 00:04:57,005
>> Davidas J. Malan: teisinga.

142
00:04:57,005 --> 00:04:58,490
Na, jei jūs žinote,
jie rūšiuojami -

143
00:04:58,490 --> 00:04:58,700
>> JENNIFER: O, ar žinote, taip.

144
00:04:58,700 --> 00:05:00,910
>> Davidas J. Malan: - bet tu negali
žinoti, kur 50 buvo dar?

145
00:05:00,910 --> 00:05:01,785
>> JENNIFER: Just keep going.

146
00:05:01,785 --> 00:05:02,130
>> Davidas J. Malan: Gerai.

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

148
00:05:02,520 --> 00:05:03,800
Keep going.

149
00:05:03,800 --> 00:05:05,270
Gerai, kad aš galiu dirbti.

150
00:05:05,270 --> 00:05:05,610
>> JENNIFER: Gerai.

151
00:05:05,610 --> 00:05:07,210
>> Davidas J. Malan: Dabar, jei jūs tiesiog
ketina nesustoti, kas yra jūsų

152
00:05:07,210 --> 00:05:09,680
algoritmas decentralizuoti remia į.

153
00:05:09,680 --> 00:05:10,740
>> JENNIFER: Linear -.

154
00:05:10,740 --> 00:05:11,820
>> Davidas J. Malan: Tai tipo linijinis.

155
00:05:11,820 --> 00:05:13,480
Bet leiskite man pasiūlyti, leiskite
man įdėti vietoje.

156
00:05:13,480 --> 00:05:14,900
Leiskite man atnaujinti puslapį.

157
00:05:14,900 --> 00:05:17,120
tas pats numeris, pats susitarimas,
patys durys.

158
00:05:17,120 --> 00:05:21,350
Tačiau prisiminkite, kad pirmosios dienos
klasė kai mes sudraskė telefono knygą

159
00:05:21,350 --> 00:05:25,480
pusė, tarsi, ir tai, kas buvo
mūsų strategija yra?

160
00:05:25,480 --> 00:05:26,450
>> JENNIFER: Pradėkite viduryje.

161
00:05:26,450 --> 00:05:26,690
>> Davidas J. Malan: Gerai.

162
00:05:26,690 --> 00:05:27,610
Taigi prasideda viduryje.

163
00:05:27,610 --> 00:05:28,790
Taigi eikime į priekį ir imituoti, kad.

164
00:05:28,790 --> 00:05:30,720
Pradėkite vidurį surengė
atskleidžia, kad duris.

165
00:05:30,720 --> 00:05:31,660
Taigi skaičius 16.

166
00:05:31,660 --> 00:05:35,290
Taigi, ką stiprus vaikinas padarė,
kuris sudraskė telefonų knygą per pusę,

167
00:05:35,290 --> 00:05:38,450
, kad patektumėte į kitą atspėti?

168
00:05:38,450 --> 00:05:39,400
>> JENNIFER: "Eik šioje pusėje.

169
00:05:39,400 --> 00:05:41,700
>> Davidas J. Malan: Ir kodėl į dešinę?

170
00:05:41,700 --> 00:05:43,900
>> JENNIFER: Jei jie tarsi mažiausias
iki didžiausio, tada 50 turėtų būti

171
00:05:43,900 --> 00:05:44,720
tuo tikslu.

172
00:05:44,720 --> 00:05:44,920
>> Davidas J. Malan: Geras.

173
00:05:44,920 --> 00:05:45,390
Visiškai pagrįsta.

174
00:05:45,390 --> 00:05:48,380
Taigi, kaip telefonų knygos, jūs einate į
teisę, o ne į kairę, bet čia

175
00:05:48,380 --> 00:05:49,500
yra raktas išsinešimui.

176
00:05:49,500 --> 00:05:53,930
Dabar jūs galite išmesti arba nuplėšti,
pusė šios problemos, paliekant Jums ne

177
00:05:53,930 --> 00:05:55,970
su 7 durimis, bet tikrai tik su 3.

178
00:05:55,970 --> 00:05:57,870
Kuris yra maždaug pusė
dydis problemą.

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

180
00:05:58,350 --> 00:06:01,890
Taigi dabar, ką jums reikės
padaryta po to, kai eiti tiesiai?

181
00:06:01,890 --> 00:06:05,870
>> JENNIFER: Taigi 16 yra vis dar gana maža,
, palyginti su 50, tai gal bandysiu,

182
00:06:05,870 --> 00:06:06,700
kaip, šio vieno.

183
00:06:06,700 --> 00:06:07,890
>> Davidas J. Malan: Gerai.

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

185
00:06:08,720 --> 00:06:10,830
Gerai, kad dabar kas yra jūsų
instinktas sakau?

186
00:06:10,830 --> 00:06:12,100
>> JENNIFER: galiu mesti toli
tai ir tada tik -

187
00:06:12,100 --> 00:06:12,360
>> Davidas J. Malan: Gerai.

188
00:06:12,360 --> 00:06:14,212
Geras, galite mesti toli
kairę pusę ten.

189
00:06:14,212 --> 00:06:14,890
>> JENNIFER: - pasiimti šį vieną.

190
00:06:14,890 --> 00:06:15,530
>> Davidas J. Malan: Ir teisingai.

191
00:06:15,530 --> 00:06:15,760
>> JENNIFER: Taip.

192
00:06:15,760 --> 00:06:17,820
>> Davidas J. Malan: Taigi, nors sunku
pamatyti, galbūt, kai tik

193
00:06:17,820 --> 00:06:21,320
7 durys, pagalvokite apie tai, o dabar,
iš nuoseklumas

194
00:06:21,320 --> 00:06:22,620
algoritmą tiesiog taikyti.

195
00:06:22,620 --> 00:06:24,510
Per praėjusius atveju tu
gauti pasisekė, kuris buvo puikus.

196
00:06:24,510 --> 00:06:26,540
Bet tu naudoti euristinis,
Sakyčiau.

197
00:06:26,540 --> 00:06:29,150
Jūs naudojote rūšiuoti savo instinktus ir
žinant tai sutvarkyti, jei tai gana

198
00:06:29,150 --> 00:06:31,600
maža pradžioje, žinoma, mes
turiu eiti daugiau į dešinę.

199
00:06:31,600 --> 00:06:34,990
Bet tam tikra prasme, jūs pasisekė,
nes gal tai buvo numeris 100,

200
00:06:34,990 --> 00:06:36,220
o gal 50 buvo daugiau per vidurį.

201
00:06:36,220 --> 00:06:37,910
Gal 50 buvo dar čia.

202
00:06:37,910 --> 00:06:40,960
>> Tačiau tai, ką padarė šiek tiek kitaip
šį kartą buvo, tu tą patį

203
00:06:40,960 --> 00:06:42,150
vėl ir vėl.

204
00:06:42,150 --> 00:06:45,310
Ir aš norėčiau teigti, kad ką tik
nebuvo, nors įtakos telefoną

205
00:06:45,310 --> 00:06:48,100
knyga, pavyzdžiui, yra kažkas daug
daugiau algoritmų, ir daug

206
00:06:48,100 --> 00:06:49,930
mažiau ypatinga dėžutę.

207
00:06:49,930 --> 00:06:51,620
Daug mažiau instinktyvus.

208
00:06:51,620 --> 00:06:57,160
Taigi, dienos pabaigoje, kaip būtų
jūs apibūdinti efektyvumą

209
00:06:57,160 --> 00:07:00,530
pirmas algoritmas, kur ėjo
kairės į dešinę, palyginti su

210
00:07:00,530 --> 00:07:03,430
Antrasis algoritmas čia?

211
00:07:03,430 --> 00:07:06,460
>> JENNIFER: Tai vienas turėtų, kaip, galbūt
perpus sumažinti laiką, ar net daugiau, taip.

212
00:07:06,460 --> 00:07:07,320
>> Davidas J. Malan: Gerai, gal net daugiau.

213
00:07:07,320 --> 00:07:10,150
Leiskite stumti šiek tiek sunkiau, kad.

214
00:07:10,150 --> 00:07:13,030
Kas iš tikrųjų, jei mes ir toliau tai
logika, mes tikrai perpus

215
00:07:13,030 --> 00:07:15,830
veikimo laikas su šio antrojo algoritmo
mesti toli pusę

216
00:07:15,830 --> 00:07:18,470
numeriai, bet ką mes galime padaryti kitą
iteracija, kai Jennifer atskleidė

217
00:07:18,470 --> 00:07:20,615
Antrasis numeris?

218
00:07:20,615 --> 00:07:22,830
>> Mes perpus Durų skaičiai dar kartą.

219
00:07:22,830 --> 00:07:25,270
Ir tada ką mes darome, po to, jei
ten buvo daugiau durys žaisti?

220
00:07:25,270 --> 00:07:27,520
Mes norėtume perpus sumažinti juos, ir vėl,
ir vėl, ir vėl.

221
00:07:27,520 --> 00:07:30,420
Ir tai buvo kaip jus vaikinai visi
atsistojus ne pirmą savaitę

222
00:07:30,420 --> 00:07:33,000
klasė, pusė iš jūsų sėdi, pusė
iš jūsų sėdi, pusė iš jūsų

223
00:07:33,000 --> 00:07:35,440
sėdi, kol vienas vienišas
siela stovi.

224
00:07:35,440 --> 00:07:39,050
Ir mes sakėme, kad veikimo laikas
kad žingsnių skaičius užtruko buvo

225
00:07:39,050 --> 00:07:40,430
apie kokia tvarka?

226
00:07:40,430 --> 00:07:41,230
>> GARSIAKALBIS 1: [nesigirdi]

227
00:07:41,230 --> 00:07:43,970
>> Davidas J. Malan: Taigi žurnalas bazė 2 n,
arba tiesiog daugiau tiesiog, prisijunkite n.

228
00:07:43,970 --> 00:07:45,060
Taigi kažkas logaritminė.

229
00:07:45,060 --> 00:07:48,380
Ir grafikas nebuvo tiesi linija
kad ką tik gavo blogiau ir blogiau, jis buvo

230
00:07:48,380 --> 00:07:52,490
Tai įdomu kreivė, kad nebuvo
gauti taip blogai laikui bėgant.

231
00:07:52,490 --> 00:07:53,910
Taigi, galime eiti į šią idėją.

232
00:07:53,910 --> 00:07:54,690
Leiskite padėkoti Jennifer.

233
00:07:54,690 --> 00:07:56,150
Labai ačiū, kad atvykote iki.

234
00:07:56,150 --> 00:07:57,400
Ir vienas sek.

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

236
00:08:00,170 --> 00:08:02,925
Nėra stalines lempas šiandien, bet mes
turiu CS50 streso kamuoliukus.

237
00:08:02,925 --> 00:08:03,420
>> JENNIFER: Šaunu.

238
00:08:03,420 --> 00:08:04,410
>> Davidas J. Malan: Gerai, čia.

239
00:08:04,410 --> 00:08:06,545
Dėkojame už patiria
stresas čia.

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

241
00:08:07,350 --> 00:08:10,620
Taigi pažiūrėkime, jei mes negalime dabar
formalizuoti tai šiek tiek daugiau.

242
00:08:10,620 --> 00:08:14,820
Taigi dar kartą, ką tik padariau buvo
iš esmės tas pats, kaip mes padarėme

243
00:08:14,820 --> 00:08:16,660
toje pirmąją savaitę.

244
00:08:16,660 --> 00:08:23,780
Tačiau užuot pabaigos tiesiog linijinis
algoritmas, kurį mes vaizduojamas

245
00:08:23,780 --> 00:08:27,210
anksčiau, nes tai tiesi linija,
pagal kurią, jei mes įdėti dar vieną duris

246
00:08:27,210 --> 00:08:29,610
ekranas, tada Jennifer būtų
turėjo ieškoti, potencialiai

247
00:08:29,610 --> 00:08:30,600
Už dar vieną durų.

248
00:08:30,600 --> 00:08:33,490
Jei mes įdėti dvi duris, ji gali turėti
ieškoti už dvi duris.

249
00:08:33,490 --> 00:08:35,990
>> Ir taip, ten buvo toks linijinis
santykiai tarp dydžio

250
00:08:35,990 --> 00:08:39,059
problema, tarkim, x ašies ir
Kiek laiko užtrunka

251
00:08:39,059 --> 00:08:40,440
išspręsti y.

252
00:08:40,440 --> 00:08:43,330
Bet vaizdas man buvo užuominos į
anksčiau buvo tai žalia linija.

253
00:08:43,330 --> 00:08:45,970
Žalioji sąmoningai, kadangi
jis tiesiog pajuto geriau.

254
00:08:45,970 --> 00:08:49,790
Teoriškai algoritmą, kai mes tai padarėme
su telefonų knygoje, kai mes tai padarėme

255
00:08:49,790 --> 00:08:52,420
su vaikinai skaičiavimas tarpusavyje, o
Antruoju atveju, kai Jennifer tik

256
00:08:52,420 --> 00:08:55,250
tai padarė čia, tai buvo tarsi
iš esmės geriau.

257
00:08:55,250 --> 00:08:57,180
Kadangi tai buvo ne tik du kartus taip greitai.

258
00:08:57,180 --> 00:08:58,870
Tai buvo net ne keturis kartus greitai.

259
00:08:58,870 --> 00:09:03,290
Tai buvo visiškai priklausoma nuo to, ką
dydis įėjimo buvo, kaip, kiek

260
00:09:03,290 --> 00:09:05,220
veiksmus, kurių ji galiausiai paėmė.

261
00:09:05,220 --> 00:09:08,040
>> Ir todėl ši paprasta idėja, kad mes visi buvo
už suteiktas telefonų knygoje,

262
00:09:08,040 --> 00:09:10,200
gali panašiai būti taikomos
į kažką panašaus į tai.

263
00:09:10,200 --> 00:09:12,380
Ir tai gali būti labiau atsainiai
žinomas kaip, nes galbūt

264
00:09:12,380 --> 00:09:13,940
įsivaizduoti, skaldyk ir valdyk.

265
00:09:13,940 --> 00:09:16,390
Ne kitaip, ką mes padarėme, žinoma,
su telefonų knygoje.

266
00:09:16,390 --> 00:09:18,300
>> Bet Pseudocode, išėmimą iš apyvartos, buvo tai.

267
00:09:18,300 --> 00:09:21,800
Taigi mes ne tai padaryti ir vėl, bet prisimenu
kad pirmą savaitę, mes visi atsistojo

268
00:09:21,800 --> 00:09:25,140
ir tada pusė iš jūsų atsisėdo pusė
jūs atsisėdo, pusė iš jūsų atsisėdo.

269
00:09:25,140 --> 00:09:29,280
Kad algoritmas buvo įgyvendintas
tiek oszukiwanie Beje, tai, kad ji

270
00:09:29,280 --> 00:09:32,870
buvo ne man tik vienas skaičiavimas
esmės, efektyviau.

271
00:09:32,870 --> 00:09:35,830
Tokiu atveju, man buvo sverto
antrinis šaltinis.

272
00:09:35,830 --> 00:09:39,470
Rūšiuoti, daug CPU, daug smegenys,
daug protingų žmonių

273
00:09:39,470 --> 00:09:42,740
kambarys buvo padėti man gauti nuo kažko
linijinis kažką

274
00:09:42,740 --> 00:09:45,190
logaritminė, nuo kažko
raudona kažką žalia.

275
00:09:45,190 --> 00:09:48,650
>> Tačiau šiuo atveju, Jennifer vien tik
esmės patobulinti

276
00:09:48,650 --> 00:09:52,370
atlikimas savo pirmąjį algoritmus,
vėl, tiesiog galvoju šiek tiek sunkiau.

277
00:09:52,370 --> 00:09:56,650
Ir dabar, kai ateina laikas įgyvendinti
šie dalykai, suprasti,

278
00:09:56,650 --> 00:10:00,670
kas eilučių kodo, galite rašyti, pavyzdžiui
kad jūs galite juos pakartoti dar kartą, ir

279
00:10:00,670 --> 00:10:03,350
vėl, ir vėl, tarsi
į apsisukimo mados.

280
00:10:03,350 --> 00:10:06,370
Kadangi jūs nesiruošia turėti
prabanga, kaip Jennifer darė pirma,

281
00:10:06,370 --> 00:10:10,460
tiesiog visa krūva IF ir pasakyti,
Hmm, jei tai pirmas skaičius yra 4,

282
00:10:10,460 --> 00:10:11,800
leiskite man pereiti visą kelią iki pabaigos.

283
00:10:11,800 --> 00:10:14,180
Ooh, jei šis skaičius yra per didelis,
leiskite man perkelti savavališkai atgal

284
00:10:14,180 --> 00:10:15,220
į antrąjį elementą sumą.

285
00:10:15,220 --> 00:10:18,210
Jūs pamatysite, kad tai bus daug
sunkiau formalizuoti, ką mes, žmonės

286
00:10:18,210 --> 00:10:21,270
laiko savaime suprantamu dalyku, kaip labai protinga
euristika, bet kompiuteris yra tik

287
00:10:21,270 --> 00:10:23,260
ketina daryti tai, ką pasakyti, kad tai padaryti.

288
00:10:23,260 --> 00:10:25,280
>> Dabar tai yra labai įdomu
pasekmės.

289
00:10:25,280 --> 00:10:29,950
Šis grafikas yra tarsi skirtas rūšiuoti
sukrėsti vizualiai, bet pastebėkite, kur

290
00:10:29,950 --> 00:10:32,230
yra tiesi linija šioje diagramoje?

291
00:10:32,230 --> 00:10:35,330
Kur yra linijinis grafikas
kurį mes vadiname n?

292
00:10:35,330 --> 00:10:37,580
Na, tai tarsi link apačios
Šio paveikslėlio, tiesa?

293
00:10:37,580 --> 00:10:40,500
Taigi viskas, mes padarėme tai mes tarsi
Mastelis dėmesį į x ašies ir

294
00:10:40,500 --> 00:10:44,780
y ašis bandyti gauti tai, ką jausmas
kitų rūšių kreivių atrodyti.

295
00:10:44,780 --> 00:10:47,760
>> Ir matematinis specifika
išraiškos šiandien nesvarbu, kad

296
00:10:47,760 --> 00:10:52,440
daug, bet pastebėsite, kad yra daug
algoritmai, kurie yra kur kas blogesnė nei

297
00:10:52,440 --> 00:10:53,470
kažkas, kad linijinė.

298
00:10:53,470 --> 00:10:55,410
Iš tiesų, n kubeliais atrodo gana neblogai.

299
00:10:55,410 --> 00:10:58,400
2 n atrodo gana neblogai.
n kvadratu atrodo gana neblogai.

300
00:10:58,400 --> 00:11:01,630
Ir mes pamatyti, ką kai kurie iš tų,
gali būti iš tikrųjų šiandien.

301
00:11:01,630 --> 00:11:05,430
Ir log n nesijaučia taip blogai, bet
geriau nei n yra žurnalo bazė 2 n.

302
00:11:05,430 --> 00:11:08,080
Bet žinote, tai būtų buvę dar
labiau stebina, jei Jennifer ar mes,

303
00:11:08,080 --> 00:11:12,910
kad pirmą savaitę, turėjo sugalvoti
kažkas, kad žurnalą žurnale n.

304
00:11:12,910 --> 00:11:15,880
>> Taigi, kitaip tariant, visa ši
galimas intervalas sprendimų

305
00:11:15,880 --> 00:11:18,570
problemų, tačiau net ir čia, pranešimas
kas nutiks.

306
00:11:18,570 --> 00:11:22,910
Kai aš nutolinti, kuris iš šių kreivių
ketina įrodyti, kad absoliuti

307
00:11:22,910 --> 00:11:26,630
blogiausia ant ekrano tie dabar?

308
00:11:26,630 --> 00:11:28,680
Taigi n kubeliais atrodo gana
blogai tuo metu.

309
00:11:28,680 --> 00:11:32,470
Bet jei mes padidinti ir pamatyti daugiau
x ir y ašis, kas vyksta

310
00:11:32,470 --> 00:11:34,550
dominuoja galiausiai?

311
00:11:34,550 --> 00:11:37,120
Taigi iš tikrųjų paaiškėja, kad nuo 2 iki
n, ir jūs galite suprasti tai tiesiog

312
00:11:37,120 --> 00:11:39,990
prijungti kai vis didesnį
numeriai ir pamatysite, kad 2

313
00:11:39,990 --> 00:11:42,070
n, tiesą sakant, plečiasi daug greičiau.

314
00:11:42,070 --> 00:11:45,530
Jeigu mes tikrai nutolinti nuo 2 iki
n algoritmas visiškai sucks.

315
00:11:45,530 --> 00:11:48,170
Aš turiu galvoje, tai ketina imtis
gana šiek tiek laiko ir

316
00:11:48,170 --> 00:11:49,460
kompiuteris bidonas per.

317
00:11:49,460 --> 00:11:52,500
>> Bet jūs pamatysite, laikui bėgant, ypač
su ateities problemų rinkinius ir net

318
00:11:52,500 --> 00:11:55,600
galutiniai projektai, yra jūsų duomenų
rinkinys tampa didelis, gerai?

319
00:11:55,600 --> 00:11:58,300
Net pirmoji versija "Facebook",
kaip draugų skaičių ir

320
00:11:58,300 --> 00:12:01,840
registruojamų vartotojų gavo didelis,
galite rūšiuoti telefonu jį ir

321
00:12:01,840 --> 00:12:05,530
įgyvendinti kažką su linijiniu paieškos,
arba labai paprasta rūšiavimas

322
00:12:05,530 --> 00:12:07,030
algoritmas, kaip mes matome šiandien.

323
00:12:07,030 --> 00:12:09,280
Jūs turite pradėti galvoti sunkiau
ir sunkiau apie šias problemas.

324
00:12:09,280 --> 00:12:12,070
Ir problemų vietų tipų, pavyzdžiui,
"Facebook" ir "Google" ir "Microsoft",

325
00:12:12,070 --> 00:12:16,350
o kiti dirba apie būtent šios
tarsi didelis duomenų rūšiuoti klausimų

326
00:12:16,350 --> 00:12:18,530
vis šių dienų.

327
00:12:18,530 --> 00:12:18,900
>> Gerai.

328
00:12:18,900 --> 00:12:23,800
Taigi Jennifer sėkmės, kad antrasis
algoritmas, tiesą sakant, ji padarė nuostabiai

329
00:12:23,800 --> 00:12:26,110
gerai pirmas kartas, bet tegul
rašyti kaip sėkmės, kad mes

330
00:12:26,110 --> 00:12:27,000
galite padaryti šį punktą.

331
00:12:27,000 --> 00:12:30,970
Antruoju atveju, ji subalansavo
algoritmas, kuris kartojamas vėl ir

332
00:12:30,970 --> 00:12:34,670
vėl, bet ji paėmė už suteiktas
tikra prielaida, kad leidome

333
00:12:34,670 --> 00:12:39,370
ją, bet ji išnaudojama gana išsamiai
antras kartas, kai ji neturėjo

334
00:12:39,370 --> 00:12:39,840
pirmą kartą.

335
00:12:39,840 --> 00:12:41,800
Kuris buvo ką?

336
00:12:41,800 --> 00:12:43,050
>> Kad sąrašas buvo rūšiuojamos.

337
00:12:43,050 --> 00:12:46,350
Taigi, kuo greičiau sąrašas buvo rūšiuojami, mes
teigia, kad Jennifer galėjo padaryti

338
00:12:46,350 --> 00:12:47,480
iš esmės geriau.

339
00:12:47,480 --> 00:12:51,450
7 durys, taip yra ne tai, kad įdomus,
bet manau, kad jį mes 7 mln durys.

340
00:12:51,450 --> 00:12:54,080
Prisijungti n neabejotinai bus
atlikti daug, daug

341
00:12:54,080 --> 00:12:55,610
greičiau ilgalaikėje perspektyvoje.

342
00:12:55,610 --> 00:12:58,880
Bet ji turėjo būti
durys surūšiuoti ja.

343
00:12:58,880 --> 00:13:02,320
Dabar, aš paėmė tai, kad laisvės
iš anksto kompiuterio ekrane

344
00:13:02,320 --> 00:13:05,160
čia, bet manau, kad Jennifer
turėjo padaryti, kad sau?

345
00:13:05,160 --> 00:13:10,120
Tarkime, kad nagrinėjamos durys
atstovauja duomenis į duomenų bazę arba

346
00:13:10,120 --> 00:13:14,260
draugai registruoti Facebook, arba
visi tinklalapiai internete, kad

347
00:13:14,260 --> 00:13:16,880
įvairių svetainių, gali prireikti
į indeksą arba ieškokite per.

348
00:13:16,880 --> 00:13:20,940
>> Tarkime, kad jūs tiesiog turėjo neapdorotus duomenis
nustatyti ir ji liko su jumis, arba

349
00:13:20,940 --> 00:13:23,010
Jennifer padaryti, kad rūšiavimą?

350
00:13:23,010 --> 00:13:26,950
Tai veikiau reikalauja, kad mes atsakome
klausimas, gerai, kiek laiko

351
00:13:26,950 --> 00:13:31,080
būtų imtasi Jennifer, ar net mane,
rūšiuoti tuos numerius iš anksto,

352
00:13:31,080 --> 00:13:32,680
, kad ji galėtų pasinaudoti, kad?

353
00:13:32,680 --> 00:13:32,880
Teisė?

354
00:13:32,880 --> 00:13:36,620
Kadangi išvada, žinoma, yra
jei reikia man gana ilgai rūšiuoti

355
00:13:36,620 --> 00:13:40,800
skaičiai, kas gi rūpinasi, kad jums
galite rasti, pavyzdžiui, 50 skaičių taip greitai,

356
00:13:40,800 --> 00:13:44,850
kaip Jennifer atveju, jei mes daugiau nei
neliko visos laiką,

357
00:13:44,850 --> 00:13:46,920
jis paėmė rūšiuoti dalykų iš anksto?

358
00:13:46,920 --> 00:13:49,320
>> Taigi pažiūrėkime, jei mes negalime
dažų paveikslėlį čia.

359
00:13:49,320 --> 00:13:51,370
Turiu visa krūva daugiau streso
rutuliukai, jei tai padeda

360
00:13:51,370 --> 00:13:52,270
pralaužti ledus čia.

361
00:13:52,270 --> 00:13:55,690
O jei ne tai, mes
reikia septynių savanoris -

362
00:13:55,690 --> 00:13:57,060
ant, Gerai.

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

364
00:13:57,240 --> 00:13:59,250
Taigi mes neturime praleisti
apie stalines lempas, atrodo.

365
00:13:59,250 --> 00:13:59,690
Gerai.

366
00:13:59,690 --> 00:14:01,530
Taigi, kaip apie judviejų priekyje.

367
00:14:01,530 --> 00:14:04,160
Kaip apie jus du vaikinai atgal.

368
00:14:04,160 --> 00:14:04,870
Štai keturi.

369
00:14:04,870 --> 00:14:09,890
Kaip apie jus priešais
penkių, šešių ir septynių.

370
00:14:09,890 --> 00:14:10,320
Štai čia.

371
00:14:10,320 --> 00:14:13,260
Jūsų draugo nukreipta jus,
taigi, galėsite gauti prizą.

372
00:14:13,260 --> 00:14:13,700
>> Gerai.

373
00:14:13,700 --> 00:14:14,410
Ateik iki.

374
00:14:14,410 --> 00:14:17,120
Ir kodėl gi ne, mes turime jums
vaikinai ateiti čia.

375
00:14:17,120 --> 00:14:18,960
Aš norėčiau duoti jums kiekvieną numerį.

376
00:14:18,960 --> 00:14:22,150
Ir eiti į priekį ir pasirūpinti patys
identiškai, kas

377
00:14:22,150 --> 00:14:25,180
vaizduojamas ekrane.

378
00:14:25,180 --> 00:14:26,530
>> [Tarpines BALSAS]

379
00:14:26,530 --> 00:14:28,160
>> Davidas J. Malan: OOP, atsiprašau.

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

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

382
00:14:32,180 --> 00:14:32,750
Na, čia mes einame.

383
00:14:32,750 --> 00:14:34,180
Skaičius penki.

384
00:14:34,180 --> 00:14:35,136
Numeris šeši.

385
00:14:35,136 --> 00:14:37,770
Vienas, du, trys, keturi,
penkių, šešių, septynių.

386
00:14:37,770 --> 00:14:39,410
O, tai yra nepatogu.

387
00:14:39,410 --> 00:14:41,210
>> SPEAKER 2: Aš tiesiog gauti -.

388
00:14:41,210 --> 00:14:41,900
>> Davidas J. Malan: Geras dalykas.

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

390
00:14:43,130 --> 00:14:44,611
Dėkojame už dalyvavimą.

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

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

393
00:14:48,580 --> 00:14:48,860
Gerai.

394
00:14:48,860 --> 00:14:51,970
Taigi, mes turime keturis, du, šeši,
vienas, trys, septyni, penki.

395
00:14:51,970 --> 00:14:56,010
Perfect todėl mes turime septynis savanorių
čia kurie yra lygūs plotis

396
00:14:56,010 --> 00:14:57,430
masyvas, kad mes žaisti
su anksčiau.

397
00:14:57,430 --> 00:14:59,470
Ir aš pasirinkau septynių priežasčių
kad bus tik

398
00:14:59,470 --> 00:15:00,840
patogus truputį.

399
00:15:00,840 --> 00:15:04,400
Ir aš ruošiuosi pasiūlyti, pirma, kad
mes surūšiuoti šių septynių savanorių.

400
00:15:04,400 --> 00:15:06,786
Jei norite, pirma,
to say hello nors.

401
00:15:06,786 --> 00:15:08,970
Kadangi tai bus
nepatogi keletą minučių.

402
00:15:08,970 --> 00:15:10,370
Įvesti save.

403
00:15:10,370 --> 00:15:10,980
>> GRACE: Sveiki, aš malonė.

404
00:15:10,980 --> 00:15:14,190
Aš į Leverett House antrakursis.

405
00:15:14,190 --> 00:15:14,620
>> BRANSON: Sveiki.

406
00:15:14,620 --> 00:15:15,620
Aš Bransonas.

407
00:15:15,620 --> 00:15:16,920
Aš į Weld pirmakursis.

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

409
00:15:19,755 --> 00:15:20,230
>> GABE: Sveiki.

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

411
00:15:21,040 --> 00:15:22,300
Aš į Cabot jaunesnysis.

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

413
00:15:24,826 --> 00:15:25,980
>> Neil: Aš Neilas.

414
00:15:25,980 --> 00:15:29,090
Aš Matthews pirmakursis.

415
00:15:29,090 --> 00:15:29,550
>> JASON: Aš Jasonas.

416
00:15:29,550 --> 00:15:32,816
Aš į Greenough pirmakursis.

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

418
00:15:33,700 --> 00:15:37,360
Aš Grays pirmakursis.

419
00:15:37,360 --> 00:15:37,990
>> JESS: Aš Jess.

420
00:15:37,990 --> 00:15:40,313
Aš į Leverett antrakursis.

421
00:15:40,313 --> 00:15:41,300
>> Davidas J. Malan: Puikiai.

422
00:15:41,300 --> 00:15:41,850
Gerai.

423
00:15:41,850 --> 00:15:44,190
Na, ačiū visiems mūsų
savanoriai čia iki šiol.

424
00:15:44,190 --> 00:15:47,110
Ir po ranka iššūkis dabar vyksta
būti išspręsti šie vaikinai, bet tada

425
00:15:47,110 --> 00:15:50,250
mes ketiname galvoti mažai
sunku apie tai, kaip efektyviai mes iš tikrųjų

426
00:15:50,250 --> 00:15:51,110
rūšiuoti juos.

427
00:15:51,110 --> 00:15:52,580
Taigi tegul pirma pabandykite.

428
00:15:52,580 --> 00:15:55,970
Jus vaikinai galite matyti vieni kitų numerius
tik pateikdamas aplink kampuose.

429
00:15:55,970 --> 00:15:59,380
Eiti į priekį ir per kelias sekundes, ir
rūšiuoti patys nuo mažiausios nuo

430
00:15:59,380 --> 00:16:01,240
palikta didžiausia dešinėje.

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

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

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

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

435
00:16:08,030 --> 00:16:09,370
Tai buvo tikrai adyti greitai.

436
00:16:09,370 --> 00:16:14,040
Dabar kažkas čia, kas buvo algoritmas
kad šie vaikinai taikomos?

437
00:16:14,040 --> 00:16:14,900
>> GARSIAKALBIS 1: mažiausiai iki didžiausių.

438
00:16:14,900 --> 00:16:15,000
>> Davidas J. Malan: Gerai.

439
00:16:15,000 --> 00:16:18,070
Jau Greatest tikrai rūšiuoti
tikslas, tačiau aš nesu įsitikinęs, kad tai

440
00:16:18,070 --> 00:16:18,890
tikrai algoritmas.

441
00:16:18,890 --> 00:16:21,810
Jau didžiausias nepasako
man žingsnis po žingsnio, ką daryti.

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

443
00:16:22,833 --> 00:16:24,083
>> GARSIAKALBIS 1: [nesigirdi]

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

445
00:16:26,010 --> 00:16:26,280
>> Davidas J. Malan: Gerai.

446
00:16:26,280 --> 00:16:28,920
Taigi, jei matote asmuo mažesnis nei
jūsų telefono numeris, tada pereiti prie

447
00:16:28,920 --> 00:16:29,680
iš jų teisus.

448
00:16:29,680 --> 00:16:32,800
Taigi, tai dabar vis labiau išraiškingas,
daugiau kaip algoritmą, nes

449
00:16:32,800 --> 00:16:35,410
galiu pasakyti, jei tai, tai.

450
00:16:35,410 --> 00:16:37,050
Taigi mes turime kokią nors
sąlyga konstruktas.

451
00:16:37,050 --> 00:16:39,700
Ir šie vaikinai atrodė, kad tai padaryti kelias
kartus, nes kai kurie iš jūsų persikėlė šiek tiek

452
00:16:39,700 --> 00:16:40,420
iš tolo.

453
00:16:40,420 --> 00:16:43,410
Taigi ten buvo matyt kažkokia iš
kilpų vyksta jų protus.

454
00:16:43,410 --> 00:16:44,610
>> Tačiau pabandykime formalizuoti tai.

455
00:16:44,610 --> 00:16:47,540
Jei vaikinai galėtų atstatyti atgal
šį susitarimą.

456
00:16:47,540 --> 00:16:50,650
Leiskite pamatyti, jei mes negalime įteisinti tai
truputį, ir tada užduoti klausimą, tiesiog

457
00:16:50,650 --> 00:16:51,580
kaip efektyviai tai yra?

458
00:16:51,580 --> 00:16:54,220
Žinoma, kai mes tai darome lėčiau,
jis ketina jaustis taip gerai

459
00:16:54,220 --> 00:16:57,210
algoritmas, bet pažiūrėkime, jei mes galime
įdėti mūsų pirštus ant tikslius veiksmus.

460
00:16:57,210 --> 00:16:58,670
>> Taigi jūs du vaikinai yra keturių ir du.

461
00:16:58,670 --> 00:17:01,020
Arba jūs teisinga ar neteisinga tvarka?

462
00:17:01,020 --> 00:17:01,900
Akivaizdu neteisinga.

463
00:17:01,900 --> 00:17:02,710
Taigi mes pavertė.

464
00:17:02,710 --> 00:17:05,170
Dabar aš ruošiuosi persikelti žemę
čia ir pasakyti, keturių iki šešių.

465
00:17:05,170 --> 00:17:06,240
Ar teisinga ar neteisinga?

466
00:17:06,240 --> 00:17:06,599
>> GABE: teisinga.

467
00:17:06,599 --> 00:17:07,180
>> Davidas J. Malan: teisinga.

468
00:17:07,180 --> 00:17:08,300
Šeši ir vienas?

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

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

471
00:17:09,630 --> 00:17:10,490
Štai du apsikeitimo sandoriai.

472
00:17:10,490 --> 00:17:11,710
Šešių ir trijų?

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

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

475
00:17:13,000 --> 00:17:13,930
Šešių ir septynių?

476
00:17:13,930 --> 00:17:14,630
Gerai atrodo.

477
00:17:14,630 --> 00:17:15,396
Septyni ir penkių?

478
00:17:15,396 --> 00:17:16,150
>> JESS: [nesigirdi]

479
00:17:16,150 --> 00:17:17,089
>> Davidas J. Malan: Gerai, mainytis.

480
00:17:17,089 --> 00:17:19,770
Ir rūšiuojamos.

481
00:17:19,770 --> 00:17:19,980
Gerai.

482
00:17:19,980 --> 00:17:21,440
Taigi akivaizdu, kad ne, tiesa?

483
00:17:21,440 --> 00:17:22,470
Taigi buvo daugiau vyksta.

484
00:17:22,470 --> 00:17:24,920
Bet, tiesą sakant, šie vaikinai, net
tiesiog instinktyviai.

485
00:17:24,920 --> 00:17:25,450
nuolat juda.

486
00:17:25,450 --> 00:17:27,710
Jie ne tik sustabdyti, kai jie
pataisyti vieną problemą.

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

488
00:17:27,839 --> 00:17:29,390
Iš tiesų, aš ruošiuosi
daryti tą patį.

489
00:17:29,390 --> 00:17:32,720
Aš teks rūšiuoti atsukti atgal
į šią problemą pradžioje,

490
00:17:32,720 --> 00:17:35,630
arba šio masyvo pradžia
žmonės, pradėkime vadindamas juos.

491
00:17:35,630 --> 00:17:38,366
>> Ir dabar kas turėtų mano algoritmas
antrame perdavimą būti?

492
00:17:38,366 --> 00:17:39,220
>> GARSIAKALBIS 1: Tas pats dalykas.

493
00:17:39,220 --> 00:17:39,940
>> Davidas J. Malan: Tas pats dalykas.

494
00:17:39,940 --> 00:17:41,460
Ir tai, aš pradedu patinka, tiesa?

495
00:17:41,460 --> 00:17:44,720
Kaip greitai, kaip jūs galite rasti sau daro
tą patį vėl ir vėl, tai

496
00:17:44,720 --> 00:17:47,890
tampa daugiau kaip algoritmą,
ir mažiau žmogaus instinktas.

497
00:17:47,890 --> 00:17:48,680
>> Taigi dabar, čia mes einame vėl.

498
00:17:48,680 --> 00:17:49,870
Dviejų ir keturių?

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

500
00:17:50,220 --> 00:17:51,050
Keturių ir vienas?

501
00:17:51,050 --> 00:17:53,380
Ak, ten buvo iš tiesų, kai
dirbti dar reikia nuveikti.

502
00:17:53,380 --> 00:17:53,620
Už ir trijų?

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

504
00:17:54,572 --> 00:17:56,000
Keturių ir šešių?

505
00:17:56,000 --> 00:17:58,380
Šešių ir penkių?

506
00:17:58,380 --> 00:17:59,470
Šešių ir septynių?

507
00:17:59,470 --> 00:18:00,970
Gerai, dabar padaryta.

508
00:18:00,970 --> 00:18:01,550
Gerai, Nr.

509
00:18:01,550 --> 00:18:02,710
Turiu eiti atgal.

510
00:18:02,710 --> 00:18:05,130
>> Taigi dabar, vėlgi, mes darome tai
šiek tiek daugiau sąmoningai.

511
00:18:05,130 --> 00:18:08,700
Ir dabar ten tik vienas smegenų
vykdant šį algoritmą.

512
00:18:08,700 --> 00:18:10,290
Vienas procesorius, jei bus.

513
00:18:10,290 --> 00:18:13,090
Ir tiesą sakant, tai vienintelis išteklius,
mes ketiname turėti prieigą prie.

514
00:18:13,090 --> 00:18:16,280
Ir kai mes grįžti prie klaviatūros
ir turėti kažką panašaus į C mūsų

515
00:18:16,280 --> 00:18:19,600
šalinimo, mes tik raštu programą
kad galima padaryti vieną dalyką vienu metu.

516
00:18:19,600 --> 00:18:22,900
Kadangi šie vaikinai metu senumo, mes
skolintomis kolektyvinė intelektinių gebėjimų sutelkimas

517
00:18:22,900 --> 00:18:24,180
kaip jus vaikinai darė savaitę nulio.

518
00:18:24,180 --> 00:18:24,980
Taigi galime laikyti tai daryti.

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

520
00:18:26,260 --> 00:18:26,945
Dviejų ir trijų.

521
00:18:26,945 --> 00:18:27,460
Trijų ir keturių.

522
00:18:27,460 --> 00:18:28,310
Keturių ir penkių.

523
00:18:28,310 --> 00:18:28,620
Penkių ir šešių.

524
00:18:28,620 --> 00:18:30,510
Šeši ir septyni.

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

526
00:18:31,880 --> 00:18:34,560
Taigi, aš esu, bet leiskite man žaisti
velnio advokatas.

527
00:18:34,560 --> 00:18:37,950
Ar man, kompiuterio rūšiuoti, kurie tiesiog
padarė kerta šio masyvo

528
00:18:37,950 --> 00:18:40,225
žmonės, žinau, kad aš padariau?

529
00:18:40,225 --> 00:18:40,670
>> GARSIAKALBIS 1: Ne

530
00:18:40,670 --> 00:18:41,050
>> Davidas J. Malan: Taigi, kodėl?

531
00:18:41,050 --> 00:18:46,900
Ką turiu daryti, kad
sudaryti ryžtingai, kad aš padariau?

532
00:18:46,900 --> 00:18:48,230
Tikriausiai dar vienas smūgis.

533
00:18:48,230 --> 00:18:48,430
Teisė?

534
00:18:48,430 --> 00:18:51,760
Nes aš žinau, kad iš ankstesnių
pass kad aš ištaisyti klaidą.

535
00:18:51,760 --> 00:18:53,920
O tai reiškia, gal ten
dar viena klaida

536
00:18:53,920 --> 00:18:54,840
kad man reikia ištaisyti.

537
00:18:54,840 --> 00:18:58,680
Taigi galiu tik būtinai pagal pervyniojimas, ir
tada patikrinti, 01:59, du ir

538
00:18:58,680 --> 00:19:00,940
trijų, trijų ir keturių, keturių ir penkių,
penkių ir šešių, šešių ir septynių.

539
00:19:00,940 --> 00:19:02,510
Gerai, dabar aš jokio darbo.

540
00:19:02,510 --> 00:19:05,990
>> Aš tikrai gali prisiminti, kad aš ne
dirbti su kažkuo panašaus kintamojo,

541
00:19:05,990 --> 00:19:06,975
kaip int.

542
00:19:06,975 --> 00:19:12,490
Pavadinkite tai apsikeitimo sandoriai ir, jei sandoriai yra 0, kai aš
gauti čia, ir jis pradėjo 0, tada

543
00:19:12,490 --> 00:19:15,520
Aš tiesiog kvaila nesustoti
pirmyn ir atgal, tikrinimo ir vėl

544
00:19:15,520 --> 00:19:16,450
vėl, ir vėl, tiesa?

545
00:19:16,450 --> 00:19:18,450
Kadangi jūs įstrigti kai
rūšies begalinis ciklas.

546
00:19:18,450 --> 00:19:21,250
Taigi, kuo greičiau ten 0 apsikeitimo sandoriai,
galima teigti, kad šis

547
00:19:21,250 --> 00:19:23,810
algoritmas yra tikrai baigtas.

548
00:19:23,810 --> 00:19:25,400
>> Dabar galime įdėti pavadinimą apie tai.

549
00:19:25,400 --> 00:19:28,930
Algoritmas, kuris Siūlau mes tiesiog
įgyvendinti yra kažkas vadinamas burbulas

550
00:19:28,930 --> 00:19:32,800
rūšiuoti, žinomas kaip pavyzdžiui ta prasme, kad
skaičiai yra didesni rūšies

551
00:19:32,800 --> 00:19:37,990
burbulas savo kelią į viršų, arba iki
į skaičių masyvo pabaigos.

552
00:19:37,990 --> 00:19:40,270
Bet kaip efektyvus buvo šis algoritmas?

553
00:19:40,270 --> 00:19:44,600
Kiek žingsnių aš fiziškai turi
imtis, pavyzdžiui, norite surūšiuoti šių

554
00:19:44,600 --> 00:19:45,850
Septyni žmonės?

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

556
00:19:48,560 --> 00:19:49,550
>> Keturių iki penkių?

557
00:19:49,550 --> 00:19:51,420
Gerai, per daug, galiausiai
bus atsakymas.

558
00:19:51,420 --> 00:19:54,960
Bet net ir tada, konkretus dienų skaičius
nėra taip įdomu.

559
00:19:54,960 --> 00:19:56,670
Leiskite apibendrinti tai, kaip n.

560
00:19:56,670 --> 00:20:00,520
Taigi, jei aš n žmonių čia, ir jie
buvo, tarsi, atsitiktine tvarka ne

561
00:20:00,520 --> 00:20:02,180
pradžioje, toje pradinės tvarkos.

562
00:20:02,180 --> 00:20:04,910
Na, kiek žingsnių aš turėti
imtis pirmą perdavimą?

563
00:20:04,910 --> 00:20:09,810
Tai buvo vienas, du, trys, keturi, penki,
šešių, ir jie septyni žmonės, todėl

564
00:20:09,810 --> 00:20:13,670
kad septynių, šešių -, kad tai n
minus viena veiksmus pirmą kartą.

565
00:20:13,670 --> 00:20:16,280
>> Dabar, kiek žingsnių aš turėti
imtis, kai aš apsukti iš naujo?

566
00:20:16,280 --> 00:20:19,310
Na, iš tikrųjų galime padvigubinti, kad jei
mes tikrai norėjo, bet dabar, aš tikiu,

567
00:20:19,310 --> 00:20:22,300
tiesiog ketinate pasakyti, gerai,
dar n atėmus 1.

568
00:20:22,300 --> 00:20:25,240
Taigi n atėmus 1 ketinate gauti
erzina sekti, todėl galime

569
00:20:25,240 --> 00:20:26,400
tik suapvalinti šiek tiek.

570
00:20:26,400 --> 00:20:27,770
Taigi 2n veiksmus.

571
00:20:27,770 --> 00:20:29,310
Taigi 14 žingsnių, duoti ar priimti.

572
00:20:29,310 --> 00:20:31,930
>> Kiek kartų aš
žingsnis kitą kartą?

573
00:20:31,930 --> 00:20:33,740
Na, tai 3n.

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

575
00:20:34,510 --> 00:20:37,920
Ir dabar, blogiausiu atveju,
Pavyzdžiui, kiek kartų aš norėjau

576
00:20:37,920 --> 00:20:41,730
dingo ir atgal, pirmyn ir atgal,
vykdant šį algoritmą, Swapping

577
00:20:41,730 --> 00:20:44,620
žmonių kiekvieną perdavimą, maždaug?

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

579
00:20:47,720 --> 00:20:50,010
Tai iš tikrųjų n kvadratu, tiesa?

580
00:20:50,010 --> 00:20:53,000
>> Nes blogiausiu atveju, galite natūra
iš pagalvoti apie tai intuityviai,

581
00:20:53,000 --> 00:20:54,800
nors tai gali užtrukti šiek tiek
tiek laiko nuskandinti in

582
00:20:54,800 --> 00:20:57,590
Blogiausiu atveju, ką jie
septyni žmonės atrodė, kad

583
00:20:57,590 --> 00:21:00,230
sąlygos susitarimą
jų numerius?

584
00:21:00,230 --> 00:21:01,460
Visiškai atgal, tiesa?

585
00:21:01,460 --> 00:21:02,815
Ir tik imituoti, kad
kas buvo tavo vardas?

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

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

588
00:21:03,640 --> 00:21:08,100
Gerai, Mike, galite tiesiog prisijungti prie manęs per
čia tik vieną sekundę?

589
00:21:08,100 --> 00:21:08,880
Tiesą sakant, ne.

590
00:21:08,880 --> 00:21:10,150
Atsiprašome Mike, tegul atgal.

591
00:21:10,150 --> 00:21:10,910
Kas tavo vardas?

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

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

594
00:21:11,640 --> 00:21:13,750
Gerai, Neil, galite ateiti su
man, jei jūs neprieštaraujate.

595
00:21:13,750 --> 00:21:17,150
Taigi, aš ruošiuosi pasiūlyti tik
paprastumas, kad Neil dabar jo

596
00:21:17,150 --> 00:21:18,510
Blogiausias atvejis.

597
00:21:18,510 --> 00:21:20,720
Tačiau prisiminti, kaip aš parašiau
mano algoritmas.

598
00:21:20,720 --> 00:21:24,530
Aš lyginant, lyginant, lyginant,
lyginant, lyginant, oi.

599
00:21:24,530 --> 00:21:26,640
Dabar šie vaikinai yra iš
iš eilės, todėl aš nustatyti.

600
00:21:26,640 --> 00:21:27,980
Taigi vaikinai sukeisti.

601
00:21:27,980 --> 00:21:31,630
Tačiau mano, kad dabar, kiek toliau
nėra Neil eiti?

602
00:21:31,630 --> 00:21:32,690
Tai maždaug n.

603
00:21:32,690 --> 00:21:33,570
Jūs žinote, tai nėra faktiškai n.

604
00:21:33,570 --> 00:21:36,040
Tai kaip, n atėmus 1, bet aš gaunu
Sapīcis sekti mažai

605
00:21:36,040 --> 00:21:37,550
skaičius, todėl galime tik jį vadiname n.

606
00:21:37,550 --> 00:21:42,860
>> Taigi, jei Neilas juda vienas žingsnis maksimaliai kiekvienas
laiką ir pereiti Neil vieną žingsnį,

607
00:21:42,860 --> 00:21:46,580
Aš turiu padaryti tai tikrai nuobodų perdavimą
pirmyn ir atgal, tai yra maždaug

608
00:21:46,580 --> 00:21:52,080
Tokiu būdu, n žingsnių, iš n kartų iš viso,
nes ji ketina imtis man

609
00:21:52,080 --> 00:21:55,820
kad daug žingsnių gauti Neilas visi
būdas, kur jis priklauso.

610
00:21:55,820 --> 00:21:58,620
Jau nekalbant visi kiti, jei jus vaikinai
visi buvo neteisingai nurodė taip pat.

611
00:21:58,620 --> 00:22:01,100
>> Taigi galime skambinti burbulas rūšiuoti n kvadratu.

612
00:22:01,100 --> 00:22:04,860
Veikimo laikas šį algoritmą,
vykdo šią algoritmas,

613
00:22:04,860 --> 00:22:07,120
efektyvumas šio algoritmo
mes tiesiog aprašyti daugiau

614
00:22:07,120 --> 00:22:08,800
paprastai kaip n kvadratu.

615
00:22:08,800 --> 00:22:11,650
Kuris yra gražus, nes aš galėtų padaryti
tas pats pavyzdys su aštuonių žmonių, devynių

616
00:22:11,650 --> 00:22:15,450
žmonių, milijonai žmonių, ir kad
Atsakymas yra nesiruošia keisti.

617
00:22:15,450 --> 00:22:18,870
>> Taigi, jei jus vaikinai ne tai, galime
naujo jums, kur jums pradėti.

618
00:22:18,870 --> 00:22:22,510
Ir pabandykime kitus du metodus ir
pamatyti, jei mes negalime padaryti iš esmės

619
00:22:22,510 --> 00:22:23,820
geriau nei šis.

620
00:22:23,820 --> 00:22:27,130
Taigi šiuo metu, aš pasiūlyti
iš įvairių algoritmas rūšiuoti.

621
00:22:27,130 --> 00:22:29,950
Tai buvo labai protingas iš mūsų paskutinis kartas,
ir vaikinai buvo teisė į

622
00:22:29,950 --> 00:22:32,470
teisė instinktai tiesiog rūšies
Swapping poromis.

623
00:22:32,470 --> 00:22:36,500
Bet jei aš tikrai norėjo imtis šio
tiesiog, ir mano tikslas yra perkelti

624
00:22:36,500 --> 00:22:39,800
visi mažai numerius šiuo būdu, ir
stumti visi didieji numerius,

625
00:22:39,800 --> 00:22:43,030
Beje, kodėl ne aš tiesiog padaryti, kad
labiausiai naivus būdas įmanoma ir pamatyti, jei aš

626
00:22:43,030 --> 00:22:45,730
gali padaryti geriau nei buvo
gana sudėtingas algoritmas?

627
00:22:45,730 --> 00:22:46,620
>> Taigi pažiūrėkime.

628
00:22:46,620 --> 00:22:48,940
Keturi yra gana nedaug, todėl aš
ketina palikti jus ten metu.

629
00:22:48,940 --> 00:22:50,610
Ooh, numeris du yra net geriau.

630
00:22:50,610 --> 00:22:52,230
Taigi, galite tiesiog žingsnis į priekį
metu?

631
00:22:52,230 --> 00:22:55,670
Tai šiuo metu mano mažiausias sunumeruoti
kandidatas, ir aš ruošiuosi prisiminti

632
00:22:55,670 --> 00:22:57,000
kad ten, patinka, kintamasis.

633
00:22:57,000 --> 00:22:57,930
Bet aš ruošiuosi nuolat tikrinti.

634
00:22:57,930 --> 00:22:59,890
Ar yra asmuo, kurio
skaičius yra mažesnis?

635
00:22:59,890 --> 00:23:00,460
Šeši, Nr.

636
00:23:00,460 --> 00:23:01,390
O, ten Neil dar kartą.

637
00:23:01,390 --> 00:23:04,050
>> Taigi, aš ruošiuosi stumti jus atgal
Rūšiuoti konceptualiai.

638
00:23:04,050 --> 00:23:05,120
Neil ateis į priekį.

639
00:23:05,120 --> 00:23:08,440
Ir dabar, kintamąjį, kad aš naudoju, kad
sekti, kas yra mažiausias

640
00:23:08,440 --> 00:23:11,390
skaičius atnaujintas, kad turi
Neil vieta.

641
00:23:11,390 --> 00:23:12,110
Na, pažiūrėkime.

642
00:23:12,110 --> 00:23:13,960
Trys, septyni, penki.

643
00:23:13,960 --> 00:23:15,590
Gerai, aš žinau, Neil buvo mažiausias.

644
00:23:15,590 --> 00:23:18,110
Kas yra paprasčiausias dalykas
man dabar daryti?

645
00:23:18,110 --> 00:23:21,410
Nesiruošiu gaišti savo laiką tik
burbuliuoja Neil vienoje vietoje į kairę.

646
00:23:21,410 --> 00:23:25,350
Kodėl ne aš tiesiog įdėti Neil kur jis
priklauso, kuris, žinoma, kur?

647
00:23:25,350 --> 00:23:26,160
>> Visi pradžioje būdas.

648
00:23:26,160 --> 00:23:27,720
Taigi Neil, ateik pas mane.

649
00:23:27,720 --> 00:23:28,910
O kas buvo tavo vardas?

650
00:23:28,910 --> 00:23:29,310
>> GRACE: malonė.

651
00:23:29,310 --> 00:23:29,710
>> Davidas J. Malan: malonė.

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

653
00:23:29,920 --> 00:23:32,490
Taigi malonė, deja, jūs
rūšies į kelią.

654
00:23:32,490 --> 00:23:34,290
Taigi, kaip mes išspręsti šią problemą?

655
00:23:34,290 --> 00:23:34,490
Teisė?

656
00:23:34,490 --> 00:23:37,500
Jei tai yra masyvas, yra
tik septynios vietos.

657
00:23:37,500 --> 00:23:40,830
Prisiminkite, kad su Rob, mes kalbėjome apie
skelbiantis amžių, ir mes turėjo tik

658
00:23:40,830 --> 00:23:41,740
baigtinis skaičius amžius?

659
00:23:41,740 --> 00:23:42,535
Pati idėja čia.

660
00:23:42,535 --> 00:23:44,300
Mes turime tik baigtinio skaičiaus Ints.

661
00:23:44,300 --> 00:23:47,590
Malonė yra tipo mūsų
būdas, taip, kaip mes nustatyti?

662
00:23:47,590 --> 00:23:49,555
>> Paprasčiausias būdas yra panašus,
Malonė, atsiprašau.

663
00:23:49,555 --> 00:23:51,870
Jūs ketinate eiti per
ten, mes galime padaryti kambarį.

664
00:23:51,870 --> 00:23:55,290
Dabar, jei jūs manote apie tai, gal
mes tiesiog padarė problema blogiau.

665
00:23:55,290 --> 00:23:58,510
O gal mes padarėme, nes kas, jei
Malonė buvo reikiamoje vietoje?

666
00:23:58,510 --> 00:24:01,730
Bet mes žinome, ji ne, nes
kitaip, ji būtų buvusi

667
00:24:01,730 --> 00:24:03,980
stovint į priekį, o ne
Neil šiuo metu, tiesa?

668
00:24:03,980 --> 00:24:05,550
Mes jau patikrinti jos numerį iš.

669
00:24:05,550 --> 00:24:05,770
>> Gerai.

670
00:24:05,770 --> 00:24:09,110
Taigi dabar, Neil reikiamoje vietoje, ir
Galiu padaryti šiek tiek optimizavimas.

671
00:24:09,110 --> 00:24:11,740
Kitam minutę, aš ignoruoti
Neil visi kartu, kad nebūtų

672
00:24:11,740 --> 00:24:15,280
gaišti savo laiką, arba atsitiktinai
apsikeitimo jį į neteisingą vietą.

673
00:24:15,280 --> 00:24:17,805
Taigi dabar, kaip man rasti kitą
elementas, kuris yra mažiausias?

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

675
00:24:18,480 --> 00:24:20,225
Tai gana geras numeris, jei
jūs norite žingsnis į priekį ir

676
00:24:20,225 --> 00:24:21,100
Aš prisimenu tave.

677
00:24:21,100 --> 00:24:21,980
Šeši, nieko gero.

678
00:24:21,980 --> 00:24:24,820
Keturi, trys, septyni, penki, nieko gero.

679
00:24:24,820 --> 00:24:26,800
Taigi leiskite man pereiti jums
Jūsų tinkama vieta.

680
00:24:26,800 --> 00:24:28,470
Ir mes tiesiog pasisekė šį kartą.

681
00:24:28,470 --> 00:24:31,350
>> Dabar aš ruošiuosi juos ignoruoti
du vaikinai, o dabar tai dar vienas

682
00:24:31,350 --> 00:24:32,260
pro tai.

683
00:24:32,260 --> 00:24:33,490
Šeši, kad gana mažas skaičius.

684
00:24:33,490 --> 00:24:34,300
Nagi pirmyn.

685
00:24:34,300 --> 00:24:35,220
Oi, atsiprašau.

686
00:24:35,220 --> 00:24:37,640
Grace numeris yra geriau,
taip žingsnis į priekį.

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

688
00:24:38,260 --> 00:24:39,120
Atsiprašome, Grace.

689
00:24:39,120 --> 00:24:39,950
Eik ir sugrįžk.

690
00:24:39,950 --> 00:24:41,550
Numeris trys yra geresnis.

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

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

693
00:24:42,720 --> 00:24:43,550
Ir dabar kas tavo vardas?

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

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

696
00:24:44,420 --> 00:24:47,050
Taigi Jasonas dabar mažiausias
elementas Aš pasirinktas.

697
00:24:47,050 --> 00:24:49,160
Kur jis ketina eiti?

698
00:24:49,160 --> 00:24:50,380
Taigi, kur yra šešių.

699
00:24:50,380 --> 00:24:51,210
Ir jūsų vardas vėl?

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

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

702
00:24:52,340 --> 00:24:53,220
Gabe tai tokiu būdu.

703
00:24:53,220 --> 00:24:54,640
Kas yra lengviausias, ką reikia padaryti?

704
00:24:54,640 --> 00:24:58,390
Sukeisti šiuos du vaikinai ir tęsti.

705
00:24:58,390 --> 00:24:59,020
Taigi dabar pažiūrėkime.

706
00:24:59,020 --> 00:25:00,170
Kas yra mažiausias?

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

708
00:25:01,030 --> 00:25:01,990
Leiskite man tiesiog rūšies apgauti.

709
00:25:01,990 --> 00:25:03,090
Penkių bus mažiausias.

710
00:25:03,090 --> 00:25:05,220
Manau, kitą, jei jūs norite žingsnis
į priekį, ką man daryti su

711
00:25:05,220 --> 00:25:06,820
šie vaikinai, su Gabe?

712
00:25:06,820 --> 00:25:08,450
Sukeisti dar kartą.

713
00:25:08,450 --> 00:25:10,740
Taigi dabar, vis dar šiek tiek iš eilės.

714
00:25:10,740 --> 00:25:14,140
Radau Gabe būti mažiausias, todėl
Aš pop jį, perkelti jus vaikinai daugiau.

715
00:25:14,140 --> 00:25:15,190
Ir padaryta.

716
00:25:15,190 --> 00:25:17,200
>> Taigi atsakymas yra tas pats.

717
00:25:17,200 --> 00:25:18,600
Galutinis rezultatas yra tas pats.

718
00:25:18,600 --> 00:25:22,730
Kuris iš šių dviejų algoritmų
kas yra geriau?

719
00:25:22,730 --> 00:25:23,500
Antrasis, aš girdėjau.

720
00:25:23,500 --> 00:25:24,252
Kodėl?

721
00:25:24,252 --> 00:25:25,900
>> GARSIAKALBIS 3: Tai n žingsnių [nesigirdi].

722
00:25:25,900 --> 00:25:27,600
>> Davidas J. Malan: Tai n pakopomis labiausiai.

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

724
00:25:28,490 --> 00:25:30,610
Taigi tai yra nors?

725
00:25:30,610 --> 00:25:33,630
Taigi, kaip aš rasti
mažiausias elementas?

726
00:25:33,630 --> 00:25:37,060
Kiek žingsnių aš turi imtis
rasti mažiausią elementą?

727
00:25:37,060 --> 00:25:39,220
Aš ieškoti visą kelią
pabaigoje, tiesa?

728
00:25:39,220 --> 00:25:41,530
Nes tokiu blogiausiu atveju, ką
jei Neil buvo čia?

729
00:25:41,530 --> 00:25:45,700
Taigi, tiesiog rasti mažiausią elementą
priima mane n priemonių, arba n ± 1.

730
00:25:45,700 --> 00:25:46,100
Bet Gerai.

731
00:25:46,100 --> 00:25:46,980
Taigi nustatyti Neil.

732
00:25:46,980 --> 00:25:48,740
Nepamirškite, kad per minutę arba tiek atgal.

733
00:25:48,740 --> 00:25:51,680
>> Bet kaip aš rasti kitą
mažiausias elementas?

734
00:25:51,680 --> 00:25:54,830
Tai n atėmus 1, arba N ± 2 tikrai,
iš etapų.

735
00:25:54,830 --> 00:25:55,440
Taigi Gerai.

736
00:25:55,440 --> 00:25:57,390
Taigi, aš n ± 2.

737
00:25:57,390 --> 00:25:57,600
Gerai.

738
00:25:57,600 --> 00:25:59,130
Taigi, kad jaučiasi šiek tiek geriau.

739
00:25:59,130 --> 00:25:59,730
Gerai.

740
00:25:59,730 --> 00:26:03,270
Kiek žingsnių kitą kartą
rasti skaičių tris?

741
00:26:03,270 --> 00:26:04,420
Taigi n atėmus 4.

742
00:26:04,420 --> 00:26:07,670
Taigi jis mažėja, vienas mažiau
žingsnis kiekvienos iteracijos.

743
00:26:07,670 --> 00:26:08,740
Taigi tai jaustis geriau, tiesa?

744
00:26:08,740 --> 00:26:13,450
Jei paskutinį kartą tai buvo maždaug n kartų n
šį kartą tai n atėmus 1, plius n atėmus

745
00:26:13,450 --> 00:26:16,500
2, plius n atėmus 3, plius n
minus 4, taškas, taškas, taškas.

746
00:26:16,500 --> 00:26:18,750
Bet jei jūs prisimenate iš savo aukštosios mokyklos
vadovėliai, tiek apgauti

747
00:26:18,750 --> 00:26:24,380
lapas gale, kuris turi formules, jei
pridėsite šį numerių serijos,

748
00:26:24,380 --> 00:26:31,280
Koks bendras pakopų skaičius
bus, kad aš čia?

749
00:26:31,280 --> 00:26:36,580
>> Tai yra vienas iš tų, kaip, n atėmus
1 times n, padalintas iš 2.

750
00:26:36,580 --> 00:26:39,040
Taigi leiskite man pamatyti, jei aš galiu traukti
tai tik akimirką aukštyn.

751
00:26:39,040 --> 00:26:42,230
Ir vėl, aš natūra apvalinimo kai
numeriai tik išlaikyti mūsų gyvenimas paprastas,

752
00:26:42,230 --> 00:26:47,830
bet aš pamenu, tai kažkas panašaus, jei
Aš n ± 1 dalykų, tada n atėmus

753
00:26:47,830 --> 00:26:53,570
2, tada n atėmus 3, tai maždaug
kažkas panašaus į tai nei 2, o jei aš

754
00:26:53,570 --> 00:26:55,510
padauginti šį naudą, tai
iš tikrųjų n aikštėje.

755
00:26:55,510 --> 00:26:58,940
Tai ne jausmas pernelyg gerai.
n atėmus n per 2.

756
00:26:58,940 --> 00:27:00,350
>> Bet čia dalykas.

757
00:27:00,350 --> 00:27:03,720
Informatikos, kai problemos
pradeda gauti įdomus, kai n

758
00:27:03,720 --> 00:27:04,700
bus tikrai didelis.

759
00:27:04,700 --> 00:27:08,110
Ir kai n bus tikrai didelis, kuris iš
šios vertybės ketina valdyti visą

760
00:27:08,110 --> 00:27:09,750
iš kitų?

761
00:27:09,750 --> 00:27:10,990
Tai tipo "n kvadratu, tiesa?

762
00:27:10,990 --> 00:27:13,340
Taip, dalijant 2 yra gana gera.

763
00:27:13,340 --> 00:27:16,740
Bet jei kalbame apie milijardus
vienetų duomenų ar trilijonai

764
00:27:16,740 --> 00:27:18,700
vienetų duomenis, Gerai, kad
jūs dvigubai greičiau.

765
00:27:18,700 --> 00:27:22,440
Bet kas tikrai rūpi, jei, kad didelis skaičius,
jei šis veiksnys yra tai, ką gauna

766
00:27:22,440 --> 00:27:23,040
didesni ir didesni.

767
00:27:23,040 --> 00:27:25,990
Ir tikrai, tai daro daugiau
nei šis vaikinas skirtumas.

768
00:27:25,990 --> 00:27:29,120
Taigi, nors vaikinai teisūs,
Antrasis algoritmas, mes jį vadiname

769
00:27:29,120 --> 00:27:32,970
pasirinkimas rūšiuoti, yra realiame pasaulyje,
tiek greičiau potencialiai nes aš esu

770
00:27:32,970 --> 00:27:35,360
atsižvelgiant mažiau ir mažiau
veiksmus kiekvieną kartą.

771
00:27:35,360 --> 00:27:37,340
>> Tai tikrai ne iš esmės greičiau.

772
00:27:37,340 --> 00:27:41,430
Nes jei mes iš tikrųjų žaisti šį už
didelės reikšmės N, pabaigoje

773
00:27:41,430 --> 00:27:44,750
per parą, pakankamai didelis n, jis vis dar
ketina jaustis gana lėtai.

774
00:27:44,750 --> 00:27:46,770
Na, leiskite man vieną
paskutinis perdavimas tuo.

775
00:27:46,770 --> 00:27:48,920
Štai ką aš vadinčiau
pasirinkimas rūšiuoti.

776
00:27:48,920 --> 00:27:51,040
Ar jums, vaikinai, iš naujo save
vienas paskutinį kartą?

777
00:27:51,040 --> 00:27:53,550
Ir pastaruoju atveju, aš ruošiuosi
pasiūlyti kažką

778
00:27:53,550 --> 00:27:54,970
vadinama įterpimo rūšiuoti.

779
00:27:54,970 --> 00:27:57,470
Įtraukiama rūšiuoti yra, konceptualiai
šiek tiek kitaip.

780
00:27:57,470 --> 00:28:00,980
>> Užuot vyksta pirmyn ir atgal ir
Pasirinkę mažiausią elementą, aš

781
00:28:00,980 --> 00:28:05,030
tik ketina kovoti su kiekviena iš šių
vaikinai kaip aš susiduria juos ir įdėkite

782
00:28:05,030 --> 00:28:06,850
juos į savo teisingą vietą.

783
00:28:06,850 --> 00:28:10,160
Taigi, aš tik ketina pradėti malonės,
ir matau, kad ji numeris keturi.

784
00:28:10,160 --> 00:28:11,720
Kur numeris keturi priklauso?

785
00:28:11,720 --> 00:28:14,940
Aš dar nepradėjo rūšiavimo nieko,
taip malonė pasireiškia pasilikti teisę ten.

786
00:28:14,940 --> 00:28:18,355
Ir dabar aš ruošiuosi reikalauti, jei galėtumėte
žengti žingsnį į dešinę, tai

787
00:28:18,355 --> 00:28:21,650
mano surūšiuoti sąrašas, tai yra mano
Unsorted likę sąrašą.

788
00:28:21,650 --> 00:28:23,260
Taigi, dabar aš ruošiuosi pradėti kitą,
o kas tavo vardas?

789
00:28:23,260 --> 00:28:23,700
>> BRANSON: Bransonas.

790
00:28:23,700 --> 00:28:24,150
>> Davidas J. Malan: Bransonas.

791
00:28:24,150 --> 00:28:25,375
Taigi Bransonas yra numeris du.

792
00:28:25,375 --> 00:28:27,490
Taigi, aš ruošiuosi jus
už akimirką.

793
00:28:27,490 --> 00:28:30,940
Ir dabar, kur Jūs priklausote
šiame masyve?

794
00:28:30,940 --> 00:28:32,360
Taigi prie malonės teisės.

795
00:28:32,360 --> 00:28:35,670
Taigi dar kartą, mes natūra padaryti
Malonė padaryti daug darbo čia.

796
00:28:35,670 --> 00:28:37,290
Kur mes padėsime jums?

797
00:28:37,290 --> 00:28:40,120
Taigi, mes ketiname į skaidrę jums
į kairę, ir įdėkite Bransonas ten.

798
00:28:40,120 --> 00:28:41,680
Bet dabar galiu reikalauti, kad
vaikinai yra padaryta.

799
00:28:41,680 --> 00:28:43,240
Tačiau pastebėkite, aš ne naudojant papildomą erdvę.

800
00:28:43,240 --> 00:28:45,130
Jis vis dar 2 elementai
čia 5 čia.

801
00:28:45,130 --> 00:28:47,910
Iš viso masyvo dydis yra 7, todėl aš
ne oszukiwanie, viskas gerai?

802
00:28:47,910 --> 00:28:51,950
>> Taigi dabar mes turime, su Gabe čia
skaičius šešių, kur Jūs priklausote?

803
00:28:51,950 --> 00:28:52,650
Jūs pasisekė dar kartą.

804
00:28:52,650 --> 00:28:53,820
Taigi jums likti teisus ten.

805
00:28:53,820 --> 00:28:57,210
Tiesiog šiek tiek žingsnį į dešinę
tiesiog įsitikinkite, aišku, kad jūs surūšiuoti.

806
00:28:57,210 --> 00:29:00,520
Ir dabar mes turime Neil vėl skaičių
vienas, kur jūs einate?

807
00:29:00,520 --> 00:29:03,540
Ir dabar, kur mes pradėsime matyti, kad
Šis algoritmas, nors nuo pirmos

808
00:29:03,540 --> 00:29:05,950
žvilgsnio atrodo gana protingas, žiūrėti
kas apie atsitikti.

809
00:29:05,950 --> 00:29:07,370
Jei galėtumėte žingsnis į priekį.

810
00:29:07,370 --> 00:29:09,260
>> Kur norime įdėti Neil?

811
00:29:09,260 --> 00:29:11,830
Taigi akivaizdu, čia, taip, kaip
mes gauname Neil ten?

812
00:29:11,830 --> 00:29:12,970
Leiskite tai padaryti žingsnis po žingsnio.

813
00:29:12,970 --> 00:29:15,620
Gabe, kur jums reikia eiti?

814
00:29:15,620 --> 00:29:19,590
Taip, todėl į vieną didelį žingsnį,
arba dvi pusės žingsniai padaryti

815
00:29:19,590 --> 00:29:20,820
vienas žingsnis ten.

816
00:29:20,820 --> 00:29:21,750
Malonė, kur jūs einate?

817
00:29:21,750 --> 00:29:22,510
Geras.

818
00:29:22,510 --> 00:29:23,500
Taigi dar vienas žingsnis.

819
00:29:23,500 --> 00:29:24,960
Ir, pagaliau, Bransonas?

820
00:29:24,960 --> 00:29:25,460
Kitas žingsnis.

821
00:29:25,460 --> 00:29:27,190
Ir dabar mes galime įdėti Neil į vietą.

822
00:29:27,190 --> 00:29:28,440
>> Taigi dabar, tęsti šią logiką.

823
00:29:28,440 --> 00:29:32,420
Nors mes negalime perkelti Neil
daugiau, ir daugiau, ir daugiau, įdėti jį

824
00:29:32,420 --> 00:29:36,420
kur jis eina, blogiausiu atveju,
kitas skaičius, mes galime susidurti galėtų

825
00:29:36,420 --> 00:29:42,220
būti skaičius, tarkim, buvo skaičius
nulis, tada mes ketiname pereiti visus

826
00:29:42,220 --> 00:29:42,730
šie vaikinai.

827
00:29:42,730 --> 00:29:44,950
Tarkime, kad yra skaičius, neigiamas
vienas, tada mes turime pereiti

828
00:29:44,950 --> 00:29:46,080
visi šie vaikinai.

829
00:29:46,080 --> 00:29:48,500
Taigi mes tikrai tik natūra prakeiktas
problema aplink, pavyzdžiui, kad mes

830
00:29:48,500 --> 00:29:52,620
perkeliant išlaidas iš
atrankos procesas, todėl įdėjimas

831
00:29:52,620 --> 00:29:56,930
procesas, taip, kad jūs, vaikinai tiesiog turėjo
perkelti maždaug n atėmus kažką

832
00:29:56,930 --> 00:29:57,940
pakopų skaičius.

833
00:29:57,940 --> 00:30:01,200
Ir žingsnių skaičius yra tik ketina
didinti, kaip aš pasirinkti daugiau numerių,

834
00:30:01,200 --> 00:30:04,730
jei aš turiu išlaikyti stumdymas jus vaikinai
atgal, ir vėl, ir vėl.

835
00:30:04,730 --> 00:30:08,320
>> Taigi liūdna dabar visi šie
algoritmai yra n kvadratu.

836
00:30:08,320 --> 00:30:10,570
Eikime į priekį ir dėka jų
vaikinai, ir vizualizuoti šiuos šiek tiek

837
00:30:10,570 --> 00:30:11,090
skirtingai.

838
00:30:11,090 --> 00:30:12,312
Labai gerai padaryta.

839
00:30:12,312 --> 00:30:14,120
>> [Plojimai]

840
00:30:14,120 --> 00:30:15,030
>> Gerai.

841
00:30:15,030 --> 00:30:16,280
There you go.

842
00:30:16,280 --> 00:30:18,390

843
00:30:18,390 --> 00:30:18,470
Dėkojame už -

844
00:30:18,470 --> 00:30:19,190
>> BRANSON: [nesigirdi] išlaikyti numerius.

845
00:30:19,190 --> 00:30:21,990
>> Davidas J. Malan: Ne, tu gali
išlaikyti numerius, taip pat.

846
00:30:21,990 --> 00:30:23,440
Gerai.

847
00:30:23,440 --> 00:30:24,100
Gražiai padaryta.

848
00:30:24,100 --> 00:30:25,300
Gerai.

849
00:30:25,300 --> 00:30:30,510
Taigi pažiūrėkime, jei mes negalime dabar apibendrinti
greičiau ir labiau vizualiai,

850
00:30:30,510 --> 00:30:33,410
ką tik atsitiko
čia taip.

851
00:30:33,410 --> 00:30:36,510

852
00:30:36,510 --> 00:30:38,770
Aš ruošiuosi eiti į priekį
ir atsigriebti Firefox.

853
00:30:38,770 --> 00:30:41,310
Susiesime šią demonstraciją
nuo kurso tinklalapyje.

854
00:30:41,310 --> 00:30:43,870
"Java" yra šiek tiek erzina, kad gauti darbo
kai kuriose naršyklėse šių dienų.

855
00:30:43,870 --> 00:30:46,760
Taigi, jei jūs žaisti šį namuose,
suprasite, jums gali tekti naudoti "Firefox"

856
00:30:46,760 --> 00:30:47,990
gauti darbo.

857
00:30:47,990 --> 00:30:50,440
Ir ką aš ruošiuosi daryti su šiuo
demonstravimas yra taip.

858
00:30:50,440 --> 00:30:54,875
>> Apačioje, turiu visa krūva
meniu pasirinktys, įskaitant pradžioje ir

859
00:30:54,875 --> 00:30:55,840
išjungimo mygtuką.

860
00:30:55,840 --> 00:30:59,450
Be to, kaip panaikinti, atrodo, kad
klaidų šiose programose, kai jūs

861
00:30:59,450 --> 00:31:03,720
iš tikrųjų negali matyti pradėti arba sustabdyti
mygtuką, jei turite arba komandą Alt

862
00:31:03,720 --> 00:31:06,560
plius ir padidinti, kuris smalsiai
rodo jums daugiau mygtukų.

863
00:31:06,560 --> 00:31:09,090
Taigi tiesiog FYI, jei tu žaidi
su šia namuose.

864
00:31:09,090 --> 00:31:12,870
Dabar aš ruošiuosi spustelėkite Start tik
momentas, kai nurodant vėlavimo,

865
00:31:12,870 --> 00:31:16,810
kaip, 200 milisekundžių čia, tiesiog
todėl mes galime pamatyti, kas atsitiks.

866
00:31:16,810 --> 00:31:20,180
>> Taigi, aš teigti, kad tai yra vizualizacija
pirmojo algoritmo

867
00:31:20,180 --> 00:31:23,730
šie vaikinai padarė, burbulas rūšiuoti, kuriuo
mes pavertė žmones porinių.

868
00:31:23,730 --> 00:31:27,490
Pagrindinis įžvalga šios vizualizacijos
yra tai, kad iš stulpelių aukščiai

869
00:31:27,490 --> 00:31:30,510
atstovauja skaičiaus dydį.

870
00:31:30,510 --> 00:31:32,210
Taigi aukštesni baras,
didesnis skaičius.

871
00:31:32,210 --> 00:31:33,680
Trumpesnis baras, mažesnis skaičius.

872
00:31:33,680 --> 00:31:38,630
Ir jei pastebėjote, mes ketiname per
pirmoji iteracija šio algoritmo

873
00:31:38,630 --> 00:31:42,620
Swapping dideli ir maži numerius, kad
nedaug ateina pirmas ir

874
00:31:42,620 --> 00:31:44,280
didelis skaičius eina į dešinę.

875
00:31:44,280 --> 00:31:48,770
>> Ir kuo greičiau mes gauname iš masyvo pabaigos
daug daugiau skaičių nei septynių, mes

876
00:31:48,770 --> 00:31:49,900
ketina grįžti į pradžią.

877
00:31:49,900 --> 00:31:51,140
Ir numatyti tai.

878
00:31:51,140 --> 00:31:54,860
Dėl toli į kairę, kad mažai vaikinas vyksta
apsikeitimo į šoną, ir tai

879
00:31:54,860 --> 00:31:56,010
procesas kartojasi.

880
00:31:56,010 --> 00:31:59,450
Dabar ši vizualizacija greitai gauna
nuobodu, todėl leiskite man eiti į priekį ir sustabdyti

881
00:31:59,450 --> 00:32:04,170
tai, pakeiskite uždelsimo kažką daug
greičiau tik gauti dabar jaustis

882
00:32:04,170 --> 00:32:05,060
Šis algoritmas.

883
00:32:05,060 --> 00:32:07,840
>> Taigi, nors aš pagreitino jį, tai
kaip atnaujinti savo procesorių, perkant

884
00:32:07,840 --> 00:32:08,580
naujas kompiuteris.

885
00:32:08,580 --> 00:32:12,980
Aš iš esmės nepasikeitė mano
algoritmas, bet jūs iš tiesų gali pamatyti daugiau

886
00:32:12,980 --> 00:32:16,800
aiškiau nei su žmonėmis, kad didelis
numeriai burbuliuoja iki viršaus,

887
00:32:16,800 --> 00:32:20,900
ir tai yra nedidelis kiekis burbuliuoja
į apačią.

888
00:32:20,900 --> 00:32:22,390
O dabar tai, ką čia sutvarkyti.

889
00:32:22,390 --> 00:32:25,260
Ir kaip žemę, aikštėse, yra
tik keletas buhalterijos ten

890
00:32:25,260 --> 00:32:28,010
padėti jums suskaičiuoti, kiek palyginimus,
ar kiek apsikeitimo sandoriai turi

891
00:32:28,010 --> 00:32:28,950
iš tikrųjų buvo padaryta.

892
00:32:28,950 --> 00:32:30,750
>> Na, pabandykime vieną
kiti matėme.

893
00:32:30,750 --> 00:32:37,116
Leiskite spustelėkite burbulas rūšiuoti čia, ir
leiskite man pasirinkti, ir visas šis interneto puslapis

894
00:32:37,116 --> 00:32:38,936
yra šiek tiek klaidų.

895
00:32:38,936 --> 00:32:41,155
Tegul prisiima riziką
ir paleisti jį dar kartą.

896
00:32:41,155 --> 00:32:44,560

897
00:32:44,560 --> 00:32:45,030
Čia mes eiti.

898
00:32:45,030 --> 00:32:47,180
Taigi darykime atrankos rūšiuoti.

899
00:32:47,180 --> 00:32:49,140
Aš nežinau, kodėl meniu
pasirodo ten.

900
00:32:49,140 --> 00:32:54,070
Leiskite priartinti nustatyti, kad
klaida, tai pakeisti iki 50.

901
00:32:54,070 --> 00:32:56,020
Ak, tegul iš tikrųjų
kad daug greičiau.

902
00:32:56,020 --> 00:32:59,160
Penki milisekundžių ar taip, ir pradėti.

903
00:32:59,160 --> 00:33:00,470
>> Taigi tai yra pasirinkimas rūšiuoti.

904
00:33:00,470 --> 00:33:03,070
Taigi dar kartą, manau, apie tai, ką mes
padarė su žmonių čia.

905
00:33:03,070 --> 00:33:08,490
Mes išgyveno masyvo ir pasirinktas
mažiausias elementas vėl,

906
00:33:08,490 --> 00:33:09,250
ir vėl, ir vėl.

907
00:33:09,250 --> 00:33:11,110
Dabar aš teigia, kad vis dar buvo gana blogai.

908
00:33:11,110 --> 00:33:15,010
Tai buvo dar n kvadratu, duoti ar priimti,
bet tai buvo, realiame pasaulyje, tiek

909
00:33:15,010 --> 00:33:18,280
greičiau, nes aš iš tikrųjų atsižvelgiant
šiek tiek mažiau veiksmus kiekvieną kartą.

910
00:33:18,280 --> 00:33:19,800
Bet mes kalbame tik ką?

911
00:33:19,800 --> 00:33:21,830
Gal 40 ar taip barai čia?

912
00:33:21,830 --> 00:33:23,200
Mes nekalbame 40 mln.

913
00:33:23,200 --> 00:33:27,430
Taigi, tai nėra visiškai aišku, man, kad
iš tikrųjų buvo didelis pelnas.

914
00:33:27,430 --> 00:33:32,530
>> Leiskite man dabar grįžti atgal ir pakeisti mūsų
Trečiasis algoritmas, kuris buvo pasirinkti

915
00:33:32,530 --> 00:33:33,180
įterpimo rūšiuoti.

916
00:33:33,180 --> 00:33:36,380
Ir dabar tai tikrai Buggy nes
meniu tikrai neturėtų būti ten.

917
00:33:36,380 --> 00:33:40,840
Taigi dabar mes pereikite atgal čia
ir pradėti šį algoritmą.

918
00:33:40,840 --> 00:33:43,270
Rėkauti, paleisti ir sustabdyti.

919
00:33:43,270 --> 00:33:47,160
Taigi tai vienos rūšies yra gana modelį
jai, kai mes vėl

920
00:33:47,160 --> 00:33:50,240
įterpiant žmonėms, arba
Šiuo atveju, barai į

921
00:33:50,240 --> 00:33:52,620
jų atitinkamą vietą.

922
00:33:52,620 --> 00:33:55,430
Ir tai jau padaryta prieš
Aš atsisukau.

923
00:33:55,430 --> 00:33:58,940
Bet tai viena, taip pat teoriškai
vis dar n kvadratu.

924
00:33:58,940 --> 00:34:01,430
>> Taigi pažiūrėkime, jei mes negalime apibendrinti
tai taip.

925
00:34:01,430 --> 00:34:04,750
Aš ruošiuosi eiti į priekį ir tiesiog duoti
mums tarsi paplitęs būdas kalbėti

926
00:34:04,750 --> 00:34:08,489
apie šiuos dalykus, leiskite man pristatyti
tik žymėjimo tiek čia.

927
00:34:08,489 --> 00:34:12,480
Jūs ruošiatės pamatyti kažką vadinama didelis
O, nes jis yra tiesiog didelis

928
00:34:12,480 --> 00:34:16,320
O. Ir tai yra taip, kad kompiuteris
mokslininkas ar matematikas net naudoja

929
00:34:16,320 --> 00:34:19,230
apibūdinti važiavimo laikas
kai kurių algoritmas.

930
00:34:19,230 --> 00:34:21,400
Kiek žingsnių ji iš tikrųjų užtruks?

931
00:34:21,400 --> 00:34:25,080
>> Dabar aš ruošiuosi varžyti save su
mano rašysenos čia vos akimirką.

932
00:34:25,080 --> 00:34:29,020
Bet leiskite man eiti į priekį ir pasakyti, kad
tai bus didelis O čia.

933
00:34:29,020 --> 00:34:33,610
Ir leiskite man pristatyti vienas kitas
simbolis, kapitalas omega.

934
00:34:33,610 --> 00:34:37,080
Omega bus atvirkščiai,
vadinasi, iš esmės didelės O. kadangi didelis O

935
00:34:37,080 --> 00:34:40,790
reiškia, blogiausiu atveju, kiek laiko
gali kai algoritmas, imtis visų būtinų

936
00:34:40,790 --> 00:34:43,480
terminai n omega ketina
būti, kiek laiko jis galėtų

937
00:34:43,480 --> 00:34:45,409
imtis geriausiu atveju.

938
00:34:45,409 --> 00:34:48,090
Ir mes pamatyti, ką mes vadiname
geriausiu atveju vos akimirką.

939
00:34:48,090 --> 00:34:49,940
>> Taigi, pradėkime ką nors paprasto.

940
00:34:49,940 --> 00:34:54,719
Leiskite man pradėti su linijiniu paiešką.

941
00:34:54,719 --> 00:34:55,679
Taigi, ne rūšiavimo.

942
00:34:55,679 --> 00:34:58,000
Mes vadiname tai linijinis paiešką.

943
00:34:58,000 --> 00:35:01,140
Ir dabar, kad mažai
lentelė iš šio.

944
00:35:01,140 --> 00:35:06,600
Ir dabar, linijinės paieškos atveju
blogiausiu atveju, kiek žingsnių yra

945
00:35:06,600 --> 00:35:11,770
ji ketina imtis man rasti
skaičius savavališko pasirinkimo?

946
00:35:11,770 --> 00:35:14,540
Ir yra N Iš viso durys
arba N Iš viso numeriai.

947
00:35:14,540 --> 00:35:15,940
Blogiausiu atveju.

948
00:35:15,940 --> 00:35:18,800
Kiek žingsnių aš teks
imtis rasti skaičių 50 masyve

949
00:35:18,800 --> 00:35:20,830
iš n durų?

950
00:35:20,830 --> 00:35:21,410
Ir kodėl?

951
00:35:21,410 --> 00:35:23,680
Kadangi tai gali būti visi
būdas per ant pabaigos.

952
00:35:23,680 --> 00:35:27,120
Taigi, panašiai kaip Jennifer susidūrė,
numeris 50 buvo visą kelią per, todėl

953
00:35:27,120 --> 00:35:30,760
Blogiausiu atveju linijinis paieška
yra didelis O n, mes pasakyti.

954
00:35:30,760 --> 00:35:33,430
>> Ką apie geriausiu atveju,
jei jums tikrai pasisekė?

955
00:35:33,430 --> 00:35:36,200
Tai tiesiog ketina imtis dar vieną žingsnį,
ar pastovus pakopų skaičius.

956
00:35:36,200 --> 00:35:37,830
Taigi mes aprašysime, kad: 1.

957
00:35:37,830 --> 00:35:39,010
Taigi, tai yra gana gera.

958
00:35:39,010 --> 00:35:41,210
Dabar ką daryti, jei mes padarėme kažką
kaip dvejetainis ieškoti?

959
00:35:41,210 --> 00:35:43,860

960
00:35:43,860 --> 00:35:47,846
Taigi dvejetainis paieška, blogiausia
bylą, paėmė, kiek laiko?

961
00:35:47,846 --> 00:35:49,250
>> [Tarpines BALSAS]

962
00:35:49,250 --> 00:35:51,310
>> Davidas J. Malan: Taigi, iš tikrųjų, aš
išgirdo po poros vietose.

963
00:35:51,310 --> 00:35:56,390
Taigi tai tikrai log n, duoti ar priimti,
nes, kaip mes padalinti sąrašą per pusę

964
00:35:56,390 --> 00:36:00,730
vėl, ir vėl, ir vėl, mes galime
rasti, galiausiai, vertė,

965
00:36:00,730 --> 00:36:04,750
jei jis ten, bet yra laimikis.

966
00:36:04,750 --> 00:36:08,590
Kas yra prielaida, kad mes turime
imtis už suteiktas naudojant dvejetainį paieškos?

967
00:36:08,590 --> 00:36:09,700
Ji turi būti rūšiuojami.

968
00:36:09,700 --> 00:36:12,770
Tai nėra rūšiuojamos, galite padalinti dalykas
per pusę vėl ir vėl, ir jūs

969
00:36:12,770 --> 00:36:15,490
gali eiti į kairę, ir jūs galite eiti į dešinę, ir
galite eiti į kairę ir į dešinę, bet jūs

970
00:36:15,490 --> 00:36:18,070
nesiruošia rasti elementą, jei
sąrašas nėra rūšiuojamos, nes

971
00:36:18,070 --> 00:36:18,790
galite praleisti jį.

972
00:36:18,790 --> 00:36:22,120
Kadangi jūsų euristini ↩ u, vykstantiems į kairę
ar teisė bus klaidingi, jei tai

973
00:36:22,120 --> 00:36:23,420
iš tiesų nėra rūšiuojamos.

974
00:36:23,420 --> 00:36:26,110
Taigi, čia yra tarsi paslėptų išlaidų
naudojant kažką panašaus į tai.

975
00:36:26,110 --> 00:36:29,250
>> Dabar eikime į mūsų rūšiavimo
algoritmai neieško -

976
00:36:29,250 --> 00:36:31,140
Oh, iš tikrųjų eikime šiuo pavyzdžiu.

977
00:36:31,140 --> 00:36:33,190
Dvejetainė paieška geriausiu atveju?

978
00:36:33,190 --> 00:36:36,290
Taip pat 1, jei ji tiesiog atsitinka būti
ir labai vidutinio masyvo arba

979
00:36:36,290 --> 00:36:37,810
iš telefonų knygos viduryje.

980
00:36:37,810 --> 00:36:39,710
Dabar darykime burbulas rūšiuoti.

981
00:36:39,710 --> 00:36:42,570
Taigi dar kartą, dabar mes patekti
rūšių, o ne paieškas.

982
00:36:42,570 --> 00:36:47,220
>> Blogiausiu atveju, kiek žingsnių argi mes
reikalavimas burbulas rūšiuoti ketina imtis?

983
00:36:47,220 --> 00:36:48,410
n kvadratu.

984
00:36:48,410 --> 00:36:49,200
Taigi, aš ruošiuosi padaryti tai.

985
00:36:49,200 --> 00:36:51,710
Ooh, mano ranka atrodo dar blogiau
kai jis Numatoma, kad didelis.

986
00:36:51,710 --> 00:36:52,510
Gerai.

987
00:36:52,510 --> 00:36:53,570
Taigi tai n kvadratu.

988
00:36:53,570 --> 00:36:59,460
Ir geriausiu atveju burbulas rūšiuoti,
kiek žingsnių ji ketina imtis?

989
00:36:59,460 --> 00:37:00,980
1, aš girdėjau.

990
00:37:00,980 --> 00:37:01,760
>> GARSIAKALBIS 1 n.

991
00:37:01,760 --> 00:37:03,286
>> Davidas J. Malan: n išgirdau.

992
00:37:03,286 --> 00:37:04,200
>> GARSIAKALBIS 1: 2.

993
00:37:04,200 --> 00:37:05,010
>> Davidas J. Malan: 2, aš girdėjau.

994
00:37:05,010 --> 00:37:06,670
Ar girdžiu 3?

995
00:37:06,670 --> 00:37:07,080
Gerai.

996
00:37:07,080 --> 00:37:11,390
Taigi, aš girdėjau, 1, n, 2, bet tegul pasirinkti
išskyrus mažiausiai pirmojo iš šių

997
00:37:11,390 --> 00:37:12,330
pasiūlymai, 1.

998
00:37:12,330 --> 00:37:15,370
Tai nėra blogai, instinktas, nes jį
tipo taip šabloną čia.

999
00:37:15,370 --> 00:37:19,670
Bet jei tai trunka tik 1 žingsnį, kaip į
pasaulis galėčiau teigti, kad sąrašas

1000
00:37:19,670 --> 00:37:22,900
yra rūšiuojamos, nes jei aš leidžiama tik
gerti po 1 žingsnį Kiek elementai

1001
00:37:22,900 --> 00:37:25,230
galėčiau tikrai įsitikinkite?

1002
00:37:25,230 --> 00:37:28,270
Na, tiesiog 1, kuris reiškia, kad yra n
atėmus 1 elementai, kurie gali būti iš

1003
00:37:28,270 --> 00:37:31,310
kad ir aš tik ketina tikėjimu po
žiūri 1 elementas, kuris

1004
00:37:31,310 --> 00:37:31,850
dalykas rūšiuoti.

1005
00:37:31,850 --> 00:37:33,930
Taigi, 1 neteisingas, čia.

1006
00:37:33,930 --> 00:37:35,710
Taigi minimaliai, kiek
turiu pažvelgti?

1007
00:37:35,710 --> 00:37:36,680
>> [Tarpines BALSAS]

1008
00:37:36,680 --> 00:37:40,160
>> Davidas J. Malan: n atėmus 1, ar tikrai,
n, nes man reikia pažvelgti į kiekvieną

1009
00:37:40,160 --> 00:37:42,190
elementas, įsitikinkite, kad
tai ne iš eilės.

1010
00:37:42,190 --> 00:37:44,750
Bet vėl, mes tarsi banga mūsų
rankos ties mažesniais skaičiais ir

1011
00:37:44,750 --> 00:37:47,100
manyti, kad n tampa didelis, jie
neįdomu vistiek.

1012
00:37:47,100 --> 00:37:48,380
Štai burbulas rūšiuoti.

1013
00:37:48,380 --> 00:37:49,830
Ir dabar, darykime paskutinius du.

1014
00:37:49,830 --> 00:37:53,520
Atrankos rūšiuoti, ir tada mes
padaryti įterpimo rūšiuoti.

1015
00:37:53,520 --> 00:37:57,160
Ir tada mes bus smūgis
protus su kažkuo daug

1016
00:37:57,160 --> 00:37:58,926
geriau nei visiems.

1017
00:37:58,926 --> 00:38:00,410
Gerai.

1018
00:38:00,410 --> 00:38:04,700
>> Kas yra blogiausias atvejis veikia
laikas atrankos rūšiuoti?

1019
00:38:04,700 --> 00:38:05,680
>> GARSIAKALBIS 4: n kvadratu.

1020
00:38:05,680 --> 00:38:06,710
>> Davidas J. Malan: n aikštė, aš klausos.

1021
00:38:06,710 --> 00:38:09,790
Bet kodėl n kvadratu, intuityviai?

1022
00:38:09,790 --> 00:38:11,170
>> GARSIAKALBIS 4: Kadangi mes tiesiog padarė.

1023
00:38:11,170 --> 00:38:12,260
>> Davidas J. Malan: Kadangi mes tiesiog padarė.

1024
00:38:12,260 --> 00:38:12,550
Gerai.

1025
00:38:12,550 --> 00:38:13,380
Geras atsakymas.

1026
00:38:13,380 --> 00:38:16,660
Bet intuityviai, kodėl atrankos
rūšiuoti n kvadratu?

1027
00:38:16,660 --> 00:38:18,980
Ką mes turime padaryti
vėl ir vėl?

1028
00:38:18,980 --> 00:38:22,570
Mes turėjome išlaikyti nuskaitymo, yra
Jūs mažiausias, tu

1029
00:38:22,570 --> 00:38:24,020
mažiausias, tu mažiausias.

1030
00:38:24,020 --> 00:38:27,480
Ir patenkintas, mes galėjome imtis n
žingsniai, tada n minus 1, tada n ± 2.

1031
00:38:27,480 --> 00:38:30,700
Bet jei jūs rūšies pridėti tie visi,
arba priimti jį tikėjimu, kad aš pridėjo

1032
00:38:30,700 --> 00:38:34,810
juos iš anksto, mes beveik n
kvadratu minus kai kurių mažesnių skaičių.

1033
00:38:34,810 --> 00:38:36,730
Taigi, aš ruošiuosi tai vadiname n kvadratu.

1034
00:38:36,730 --> 00:38:39,530
Bet su atrankos rūšiuoti geriausias
atveju, kiek žingsnių jis

1035
00:38:39,530 --> 00:38:40,632
ketina imtis domėjosi?

1036
00:38:40,632 --> 00:38:41,840
>> GARSIAKALBIS 5 [nesigirdi]

1037
00:38:41,840 --> 00:38:44,350
>> Davidas J. Malan: Tai, deja,
dar n kvadratu, tiesa?

1038
00:38:44,350 --> 00:38:49,590
Nes jei aš pasirinkdami mažiausias
elementas, ir mes turėjo septynis žmones čia

1039
00:38:49,590 --> 00:38:53,280
Aš tik žinau, kai aš gauti labai
galo, radau mažiausias

1040
00:38:53,280 --> 00:38:55,670
numeris, kur jis arba
ji galėjo būti.

1041
00:38:55,670 --> 00:38:58,820
Bet kaip man rasti kitą
mažiausias skaičius?

1042
00:38:58,820 --> 00:39:00,160
Turiu daryti kitą leidimą.

1043
00:39:00,160 --> 00:39:04,810
Taigi, geriausiu atveju, kas yra
indėlis į atrankos rūšiuoti?

1044
00:39:04,810 --> 00:39:07,830
Tai jau tarsi sąrašas, numeris vienas,
numeris du, numeris trys, skaičius keturi.

1045
00:39:07,830 --> 00:39:08,600
Bet aš kompiuterį.

1046
00:39:08,600 --> 00:39:10,190
Galiu tik pažvelgti į vieną
dalykas vienu metu.

1047
00:39:10,190 --> 00:39:12,465
Aš negaliu rūšiuoti žengti žingsnį
atgal kaip žmogus ir sako:

1048
00:39:12,465 --> 00:39:14,030
ooh, tai atrodo teisinga.

1049
00:39:14,030 --> 00:39:17,580
>> Galiu tik priimti sprendimo teisingumas
pasirinkimas yra rikiuoti pagal atrankos

1050
00:39:17,580 --> 00:39:18,370
mažiausias skaičius.

1051
00:39:18,370 --> 00:39:21,390
Bet net jei manau skaičius iš pradžių,
jei aš nežinau nieko daugiau apie

1052
00:39:21,390 --> 00:39:24,460
kiti skaičiai, kurios aš neturiu, viskas, ką aš
žinau, kad aš buvo perduoti masyvą

1053
00:39:24,460 --> 00:39:27,930
arba Durų rinkinys, už kurios yra
numeriai, vienintelis būdas aš žinau, kad vienas

1054
00:39:27,930 --> 00:39:28,680
buvo mažiausias?

1055
00:39:28,680 --> 00:39:32,440
Jei gaunu visą kelią čia ir suvokti,
Damn, vienas iš tikrųjų buvo mažiausias.

1056
00:39:32,440 --> 00:39:34,870
>> Bet kaip man tada nustatyti, kad
du yra kitas mažiausias?

1057
00:39:34,870 --> 00:39:38,350
Tokiu ta pati neveiksmingumo
vėl ir vėl.

1058
00:39:38,350 --> 00:39:42,210
Taigi pagaliau, su įterpimo rūšiuoti,
kaip, blogiausiu atveju,

1059
00:39:42,210 --> 00:39:44,990
Ar mes pasakyti, kad tai atlieka?

1060
00:39:44,990 --> 00:39:49,100
Jis taip pat yra n kvadratu.

1061
00:39:49,100 --> 00:39:53,020
Ir kaip apie su geriausiu atveju?

1062
00:39:53,020 --> 00:39:56,282
Mes palikti, kad kaip Įspūdingos filmą.

1063
00:39:56,282 --> 00:40:00,090
Mes užpildyti tą tuščią kito karto,
bet pirmiausia leiskite man pasiūlyti, kad mes

1064
00:40:00,090 --> 00:40:02,620
esmės padaryti geriau nei
visa tai, gerai?

1065
00:40:02,620 --> 00:40:05,220
>> Taigi, manau sau, ką įdėjimas
rūšiuoti manimi bus.

1066
00:40:05,220 --> 00:40:06,910
Na, tai nebuvo labai dramatiška,
nes aš tik viena

1067
00:40:06,910 --> 00:40:08,970
kad pamačiau pakeitimą.

1068
00:40:08,970 --> 00:40:09,620
Oho.

1069
00:40:09,620 --> 00:40:10,420
Gerai.

1070
00:40:10,420 --> 00:40:12,615
Taigi čia mes turime šiek tiek
kitoks demonstravimas.

1071
00:40:12,615 --> 00:40:16,580
Jei aš priartinti čia, pamatysite, kad
kairėje turime burbulas rūšiuoti, į

1072
00:40:16,580 --> 00:40:20,740
vidutinio turime pasirinkimo rūšiuoti, ir
kas teisinga, mes turime tai, ką mes

1073
00:40:20,740 --> 00:40:23,380
turite ne pažvelgė dar
vadinamas sujungti rūšiuoti.

1074
00:40:23,380 --> 00:40:26,080
Tačiau mano, kad tai, ką mes jau
čia darai iki šiol šiandien.

1075
00:40:26,080 --> 00:40:29,200
Kai Jennifer pirmą kartą atėjo į sceną,
mes išgyveno skaičių masyvas

1076
00:40:29,200 --> 00:40:33,750
vėl, ir vėl, su linijine paieškos,
ir mes turime tiesinę važiavimo laikas, didelis O

1077
00:40:33,750 --> 00:40:35,100
n, taip sakant.

1078
00:40:35,100 --> 00:40:41,000
>> Kai mes dabar mano pirmą savaitę
klasės, kai mes turėjome skaldyk ir valdyk,

1079
00:40:41,000 --> 00:40:43,740
ir mes Telefonų knyga ašarojimas,
ir Jennifer, ir mes kartu

1080
00:40:43,740 --> 00:40:47,500
pagausėtų, kad raktas įžvalga, kuris buvo
kartoti sau vėl ir vėl

1081
00:40:47,500 --> 00:40:50,930
kažkaip mesti toli, mesti toli,
mesti toli pusė problema, ar

1082
00:40:50,930 --> 00:40:55,320
Apskritai, dalijant per pusę problemą,
ir tada gydyti mažesnių gabalas

1083
00:40:55,320 --> 00:40:59,630
kaip konceptualiai ekvivalentas problema
į kitą, mes kažkaip

1084
00:40:59,630 --> 00:41:00,910
iš esmės geriau.

1085
00:41:00,910 --> 00:41:04,720
Bet burbulas rūšiuoti, su atranka
rūšiuoti, su įterpimo rūšiuoti, mes gali

1086
00:41:04,720 --> 00:41:06,560
tokios įžvalgos, kad Jennifer padarė.

1087
00:41:06,560 --> 00:41:10,220
Mes gana daug tik vaikščiojo pirmyn ir
atgal visa krūva kartų, ir mes

1088
00:41:10,220 --> 00:41:12,650
nežymiai dalykų šiek tiek, Swapping
tokia tvarka, gal

1089
00:41:12,650 --> 00:41:13,730
įdėdami arba pasirinkdami.

1090
00:41:13,730 --> 00:41:16,950
Bet dienos pabaigoje, aš daug
nepatogu vaikščioti pirmyn ir atgal.

1091
00:41:16,950 --> 00:41:21,160
Mes tikrai ne sverto kažkas
protingas kaip Jennifer patiko dalijant

1092
00:41:21,160 --> 00:41:22,040
ir užkariauja.

1093
00:41:22,040 --> 00:41:25,620
>> Taigi sujungti rūšiuoti, priešingai, kurį mes
nematysite tol, kol kitą savaitę jis ketina

1094
00:41:25,620 --> 00:41:29,540
sverto, kad esminė idėja dalijant
įėjimas, tada perpus, tada

1095
00:41:29,540 --> 00:41:30,580
perpus, tada perpus.

1096
00:41:30,580 --> 00:41:34,590
Ir kiekvienam tos linijos iteracija,
rūšiavimas yra kairėje pusėje, o dešinėje

1097
00:41:34,590 --> 00:41:38,200
pusę, tada kairėje pusėje, kairėje pusėje,
ir dešinėje pusėje kairėje, tada

1098
00:41:38,200 --> 00:41:40,990
kairėje pusėje, dešinėje pusėje, ir
Dešinė pusė iš dešinės pusės.

1099
00:41:40,990 --> 00:41:42,840
Ir kartoti vėl ir vėl.

1100
00:41:42,840 --> 00:41:46,170
>> Taigi pamatysite tai vizualiai, bet tai
yra tai, kas mūsų laukia kitą savaitę.

1101
00:41:46,170 --> 00:41:49,760
Ir apskritai, kai mes galvojame tiek
tiek sunkiau dėl tokio problema.

1102
00:41:49,760 --> 00:41:52,435

1103
00:41:52,435 --> 00:41:57,970
Mes n kvadratu kairėje pusėje, n
kvadrato viduryje, ir n

1104
00:41:57,970 --> 00:41:59,400
log n dešinėje.

1105
00:41:59,400 --> 00:42:00,590
Taigi, čia yra jūsų tikrasis Įspūdingos filmą.

1106
00:42:00,590 --> 00:42:02,040
Dar pasimatysime pirmadienį.

1107
00:42:02,040 --> 00:42:05,163
>> [Plojimai]