1
00:00:00,000 --> 00:00:00,488

2
00:00:00,488 --> 00:00:10,800
>> [Duke luajtur muzikë]

3
00:00:10,800 --> 00:00:13,500
DAVID Malan: Të gjithë të drejtë.

4
00:00:13,500 --> 00:00:14,670
Të gjithë të drejtë, të mirëpritur mbrapa.

5
00:00:14,670 --> 00:00:18,120
Pra, kjo është Java 4, fillimi
tij, tashmë.

6
00:00:18,120 --> 00:00:21,320
Dhe ju do të kujtojnë se javën e kaluar, ne kemi vënë
kodojnë mënjanë për vetëm pak

7
00:00:21,320 --> 00:00:24,240
dhe kemi filluar të flasim pak më shumë
të nivelit të lartë, rreth gjëra të tilla si

8
00:00:24,240 --> 00:00:28,130
kërkimin dhe sorting, e cila edhe pse
Idetë disi të thjeshta, janë

9
00:00:28,130 --> 00:00:31,840
përfaqësues i një klase të problemeve
ju do të fillojnë për të zgjidhur veçanërisht

10
00:00:31,840 --> 00:00:34,820
si ju filloni të menduarit rreth final
Projektet dhe zgjidhjet interesante që ju

11
00:00:34,820 --> 00:00:36,760
mund të ketë të vërtetë të botës problemeve.

12
00:00:36,760 --> 00:00:39,490
Tani lloj flluskë ishte një nga më të thjeshtë
algoritme të tilla, dhe

13
00:00:39,490 --> 00:00:42,900
punuar duke pasur këto numra të vogla
ne nje lista ose ne nje lloj vargut të

14
00:00:42,900 --> 00:00:46,530
flluskë rrugën e tyre deri në krye, dhe
Numrat e mëdha të lëvizë në rrugën e tyre poshtë për të

15
00:00:46,530 --> 00:00:47,930
fundi i kësaj liste.

16
00:00:47,930 --> 00:00:50,650
>> Dhe kujtojnë se ne mund të parashikoj
lloj flluskë pak

17
00:00:50,650 --> 00:00:52,310
diçka si kjo.

18
00:00:52,310 --> 00:00:53,640
Pra më lejoni të shkoj përpara dhe klikoni Start.

19
00:00:53,640 --> 00:00:55,350
Unë kam përzgjedhur lloj flluskë.

20
00:00:55,350 --> 00:00:58,920
Dhe në qoftë se ju kujtohet se blu shtatlartë
Linjat përfaqësojnë numra të mëdha, të vogla

21
00:00:58,920 --> 00:01:03,300
Linjat e blu paraqesin numra të vogla, si
ne do të shkojmë nëpër këtë përsëri dhe përsëri dhe

22
00:01:03,300 --> 00:01:07,680
përsëri, duke krahasuar dy bare pranë njëri-
të tjera në të kuqe, ne jemi duke shkuar për të bie në ujdi

23
00:01:07,680 --> 00:01:11,010
më i madh dhe më i vogël nëse
ata janë jashtë funksionit.

24
00:01:11,010 --> 00:01:14,150
>> Pra, kjo do të shkoj në dhe të shkoj në dhe të shkojnë
on, dhe ju do të shihni se madhe

25
00:01:14,150 --> 00:01:16,700
Elementet janë duke bërë rrugën e tyre për të
drejtë, dhe elementet më të vogla janë

26
00:01:16,700 --> 00:01:17,900
duke e bërë rrugën e tyre në të majtë.

27
00:01:17,900 --> 00:01:21,380
Por ne filluam të përcaktoj sasinë
efikasitetit,

28
00:01:21,380 --> 00:01:22,970
Cilësia e këtij algoritmi.

29
00:01:22,970 --> 00:01:25,200
Dhe ne i thamë se në më të keq
rasti, ky algoritëm mori

30
00:01:25,200 --> 00:01:27,940
afërsisht sa hapa?

31
00:01:27,940 --> 00:01:28,980
>> Pra, n katror.

32
00:01:28,980 --> 00:01:30,402
Dhe çfarë ishte n?

33
00:01:30,402 --> 00:01:31,650
>> Audienca: Numri i elementeve.

34
00:01:31,650 --> 00:01:32,790
>> DAVID Malan: Pra, ishte n
Numri i elementeve.

35
00:01:32,790 --> 00:01:33,730
Dhe kështu që ne do të bëjmë këtë shpesh.

36
00:01:33,730 --> 00:01:36,650
Çdo herë që ne duam të flasim në lidhje me madhësinë
e një problemi apo madhësinë e një

37
00:01:36,650 --> 00:01:39,140
input, apo sasia e kohës që merr
për të prodhuar prodhimit, ne vetëm do të

38
00:01:39,140 --> 00:01:41,610
çfarëdo përgjithësuar
input është si n.

39
00:01:41,610 --> 00:01:45,970
Pra, përsëri në Javën 0, numri faqet
në librin e telefonit ishte n.

40
00:01:45,970 --> 00:01:47,550
Numri i nxënësve
në dhomë u n.

41
00:01:47,550 --> 00:01:49,630
Kështu që këtu, gjithashtu, ne jemi duke ndjekur
se model.

42
00:01:49,630 --> 00:01:52,800
>> Tani n katror nuk është veçanërisht i
të shpejtë, kështu që ne u përpoqëm të bëjmë më mirë.

43
00:01:52,800 --> 00:01:55,970
Dhe kështu kemi shikuar në një çift të
algoritme të tjera, ndër të cilat

44
00:01:55,970 --> 00:01:57,690
ishin të lloj përzgjedhje.

45
00:01:57,690 --> 00:01:59,180
Pra lloj zgjedhja ishte
pak më ndryshe.

46
00:01:59,180 --> 00:02:03,130
Ajo ishte pothuajse e thjeshtë, unë guxoj të them,
ku kam filluar në fillim të

47
00:02:03,130 --> 00:02:06,740
Lista e vullnetarëve tanë dhe unë vetëm përsëri
dhe përsëri dhe përsëri shkoi nëpër

48
00:02:06,740 --> 00:02:10,060
lista, plucking jashtë vogël
element në një kohë dhe të vënë atë apo

49
00:02:10,060 --> 00:02:13,040
saj në fillim të listës.

50
00:02:13,040 --> 00:02:16,410
>> Por kjo, gjithashtu, sapo kemi filluar të mendojmë
përmes matematikë dhe më të mëdha

51
00:02:16,410 --> 00:02:19,860
foto, mendova rreth asaj se sa herë
Unë kam qenë duke shkuar mbrapa dhe me radhë dhe mbrapa

52
00:02:19,860 --> 00:02:24,090
dhe me radhë, kemi thënë në rastin më të keq,
lloj përzgjedhje, gjithashtu, ishte ajo?

53
00:02:24,090 --> 00:02:24,960
n katror.

54
00:02:24,960 --> 00:02:27,490
Tani në botën e vërtetë, ajo mund të
në fakt të jetë pak më të shpejtë.

55
00:02:27,490 --> 00:02:30,620
Sepse përsëri, unë nuk kam për të mbajtur
backtracking herë kisha renditura

56
00:02:30,620 --> 00:02:31,880
elemente të vogël.

57
00:02:31,880 --> 00:02:35,090
Por në qoftë se ne mendojmë për n shumë të mëdha, dhe
në qoftë se ju lloj i bëni jashtë matematikë si

58
00:02:35,090 --> 00:02:39,170
I bërë në dërrasë, me katror n
diçka minus, çdo gjë tjetër

59
00:02:39,170 --> 00:02:41,850
përveç katror n, dikur n
merr me të vërtetë e madhe, nuk

60
00:02:41,850 --> 00:02:42,850
me të vërtetë rëndësi sa më shumë.

61
00:02:42,850 --> 00:02:45,470
Pra, si shkencëtarët kompjuterike, ne lloj nga
të kthehet një sy qorr ndaj vogla

62
00:02:45,470 --> 00:02:49,220
faktorët dhe të përqëndrohet vetëm në faktorin e në
një shprehje që do të bëjë

63
00:02:49,220 --> 00:02:50,330
Dallimi më i madh.

64
00:02:50,330 --> 00:02:52,840
>> E pra, së fundi, kemi shikuar
në lloj futje.

65
00:02:52,840 --> 00:02:56,620
Dhe kjo ishte e ngjashme në frymë, por
në vend se të shkojnë nëpër iteratively dhe

66
00:02:56,620 --> 00:03:01,250
zgjidhni një element të vogël në një
herë, unë në vend mori dorën që unë

67
00:03:01,250 --> 00:03:04,070
u trajtuar, dhe unë vendosa, të gjithë
drejtë, ju i përkasin këtu.

68
00:03:04,070 --> 00:03:06,160
Pastaj unë u zhvendos për në elementin e ardhshëm
dhe vendosi që ai ose

69
00:03:06,160 --> 00:03:07,470
ajo i përkiste këtu.

70
00:03:07,470 --> 00:03:08,810
Dhe pastaj unë u zhvendos në dhe në.

71
00:03:08,810 --> 00:03:11,780
Dhe unë mund të, përgjatë rrugës,
zhvendosë këto guys në mënyrë që të

72
00:03:11,780 --> 00:03:13,030
të bëjë vend për ta.

73
00:03:13,030 --> 00:03:16,880
Kështu që ishte lloj i anullimit mendor
lloj i përzgjedhjes se ne

74
00:03:16,880 --> 00:03:18,630
quajtur lloj futje.

75
00:03:18,630 --> 00:03:20,810
>> Kështu që këto tema të ndodhin
në botën reale.

76
00:03:20,810 --> 00:03:23,640
Vetëm disa vjet më parë, kur një farë
Senatori u kandidon për president,

77
00:03:23,640 --> 00:03:27,160
Eric Schmidt, në atë kohë CEO i
Google, në fakt kishte mundësi

78
00:03:27,160 --> 00:03:28,040
ta intervistonin atë.

79
00:03:28,040 --> 00:03:32,010
Dhe ne menduam se do të ndajnë këtë YouTube
clip për ju këtu, në qoftë se ne mund të kthehet deri

80
00:03:32,010 --> 00:03:32,950
vëllimi.

81
00:03:32,950 --> 00:03:39,360
>> [Video playback]

82
00:03:39,360 --> 00:03:44,620
>> -Tani, senatori, ju jeni këtu në Google,
dhe unë doja të mendoj se i presidencës

83
00:03:44,620 --> 00:03:46,042
si një intervistë pune.

84
00:03:46,042 --> 00:03:47,770
>> [Qeshura]

85
00:03:47,770 --> 00:03:50,800
>> -Tani është e vështirë për të marrë
një punë si president.

86
00:03:50,800 --> 00:03:52,480
Dhe ju jeni duke kaluar nëpër
masa të rrepta tani.

87
00:03:52,480 --> 00:03:54,330
Është gjithashtu e vështirë për të marrë një punë në Google.

88
00:03:54,330 --> 00:03:59,610
Ne kemi pyetje dhe ne kërkojmë
Pyetjet kandidatët tanë.

89
00:03:59,610 --> 00:04:02,250
Dhe kjo është një nga Larry Schwimmer.

90
00:04:02,250 --> 00:04:05,325
>> [Qeshura]

91
00:04:05,325 --> 00:04:06,400
-Ju djema mendoni se unë jam kidding?

92
00:04:06,400 --> 00:04:08,750
Ajo është e drejtë këtu.

93
00:04:08,750 --> 00:04:12,110
Cila është mënyra më efikase për
lloj milioni dy-bit integers?

94
00:04:12,110 --> 00:04:15,810
>> [Qeshura]

95
00:04:15,810 --> 00:04:18,260
>> -Epo, uh -

96
00:04:18,260 --> 00:04:19,029
>> -Me fal.

97
00:04:19,029 --> 00:04:19,745
Ndoshta ne duhet -

98
00:04:19,745 --> 00:04:21,000
>> -Jo, jo, jo, jo, jo.

99
00:04:21,000 --> 00:04:21,470
>> -Kjo nuk është një -

100
00:04:21,470 --> 00:04:22,185
OK.

101
00:04:22,185 --> 00:04:25,328
>> -Unë mendoj se lloj flluskë do
të jetë mënyra e gabuar për të shkuar.

102
00:04:25,328 --> 00:04:26,792
>> [Qeshura]

103
00:04:26,792 --> 00:04:28,510
>> [Brohoritje dhe duartrokitje]

104
00:04:28,510 --> 00:04:31,211
>> -Come on, i cili i tha atij këtë?

105
00:04:31,211 --> 00:04:32,155
OK.

106
00:04:32,155 --> 00:04:33,350
>> [VIDEO END rishikim]

107
00:04:33,350 --> 00:04:35,070
>> DAVID Malan: Pra, nuk keni atë.

108
00:04:35,070 --> 00:04:39,600
Pra, kemi filluar për të përcaktoj sasinë këto running
herë, kështu që të flasin, me diçka

109
00:04:39,600 --> 00:04:43,480
quajtur simbol asymptotic, e cila është
vetëm duke iu referuar lloj tonë të kthyer

110
00:04:43,480 --> 00:04:47,420
një sy të verbër ndaj këtyre faktorëve të vogla dhe të
vetëm në kërkim në kohë të rrjedhshëm,

111
00:04:47,420 --> 00:04:51,250
Ecuria e këtyre algoritmeve,
si n merr me të vërtetë i madh me kalimin e kohës.

112
00:04:51,250 --> 00:04:55,110
Dhe kështu që ne kemi prezantuar madh O. And Big O
diçka që ne kemi menduar të përfaqësuara

113
00:04:55,110 --> 00:04:57,000
e si një kufi i sipërm.

114
00:04:57,000 --> 00:04:59,570
Dhe në të vërtetë, Barry, mund të ulim
mic se pak pak?

115
00:04:59,570 --> 00:05:01,040
>> Ne kemi menduar e kjo është një kufi i sipërm.

116
00:05:01,040 --> 00:05:04,710
O kaq i madh i mjeteve n katror se në
Rasti më i keq, diçka si

117
00:05:04,710 --> 00:05:07,780
lloj përzgjedhje do të marrë
n hapa në katror.

118
00:05:07,780 --> 00:05:10,310
Ose diçka si lloj futje
do hapa n kuadratuar.

119
00:05:10,310 --> 00:05:15,150
Tani për diçka si futje
lloj, çfarë ishte rasti më i keq?

120
00:05:15,150 --> 00:05:18,200
Duke pasur parasysh një grup, çka është më e keqja
Skenari e mundur që ju mund të gjeni

121
00:05:18,200 --> 00:05:20,650
veten të përballur me të?

122
00:05:20,650 --> 00:05:21,860
>> Kjo është plotësisht prapa, të drejtë?

123
00:05:21,860 --> 00:05:24,530
Sepse në qoftë se kjo është plotësisht prapa,
ju duhet të bëni një shumë e tërë e punës.

124
00:05:24,530 --> 00:05:26,420
Sepse në qoftë se ju jeni plotësisht prapa,
ju jeni duke shkuar për të gjetur

125
00:05:26,420 --> 00:05:28,840
Elementi më i madh këtu, edhe pse
ajo i takon atje poshtë.

126
00:05:28,840 --> 00:05:31,140
Pra, ju jeni duke shkuar për të thënë, të gjithë të drejtë, në
ky moment në kohë, ju i përkisni këtu,

127
00:05:31,140 --> 00:05:32,310
kështu që ju lënë atë vetëm.

128
00:05:32,310 --> 00:05:35,425
>> Pastaj ju kuptojnë, oh, mallkuar, unë kam për të
lëvizur këtë element paksa më të vogël në

129
00:05:35,425 --> 00:05:36,470
majtë prej jush.

130
00:05:36,470 --> 00:05:38,770
Pastaj unë kam për të bërë atë përsëri
dhe përsëri dhe përsëri.

131
00:05:38,770 --> 00:05:41,410
Dhe në qoftë se unë eci mbrapa dhe me radhë, ju
do lloj të ndjehen performancën e

132
00:05:41,410 --> 00:05:45,540
se algoritmi, sepse vazhdimisht jam unë
shuffling të gjithë të tjerët poshtë në

133
00:05:45,540 --> 00:05:46,510
array për të bërë vend për të.

134
00:05:46,510 --> 00:05:47,750
Pra, kjo është rasti më i keq.

135
00:05:47,750 --> 00:05:48,570
>> Nga ana tjetër -

136
00:05:48,570 --> 00:05:50,320
dhe kjo ishte një cliffhanger hera e fundit -

137
00:05:50,320 --> 00:05:54,065
kemi thënë se lloj futje
ishte një omega e kujt?

138
00:05:54,065 --> 00:05:57,530
Çfarë është e mirë-rasti running
koha e lloj futje?

139
00:05:57,530 --> 00:05:58,520
Pra, kjo është n fakt.

140
00:05:58,520 --> 00:06:00,980
Kjo ishte bosh që ne e kemi lënë
në bordin hera e fundit.

141
00:06:00,980 --> 00:06:03,160
>> Dhe kjo është e omega n sepse pse?

142
00:06:03,160 --> 00:06:06,630
E pra, në rastin shumë të mirë, çfarë është
lloj futje do të dorëzohet?

143
00:06:06,630 --> 00:06:09,830
E pra, që është një listë të renditura tërësisht
tashmë, puna minimale për të bërë.

144
00:06:09,830 --> 00:06:12,460
Por ajo që është i zoti për lloj futje
është se për shkak se ajo fillon këtu dhe

145
00:06:12,460 --> 00:06:15,340
vendos, oh, ju jeni numri
një, ju i përkisni këtu.

146
00:06:15,340 --> 00:06:16,970
Oh, çfarë një pasuri të mirë.

147
00:06:16,970 --> 00:06:17,740
>> Ju jeni numri dy.

148
00:06:17,740 --> 00:06:19,030
Ju gjithashtu përkasin këtu.

149
00:06:19,030 --> 00:06:21,010
Numri tre, edhe më të mirë,
ju i përkisni këtu.

150
00:06:21,010 --> 00:06:25,210
Sa më shpejt që ajo merr deri në fund të
pseudokod, lista per futje e Rendit

151
00:06:25,210 --> 00:06:28,010
se kemi ecur nëpër gojë
Herën e fundit, ajo është bërë.

152
00:06:28,010 --> 00:06:32,790
Por lloj përzgjedhje, nga ana tjetër,
mbahet duke bërë çfarë?

153
00:06:32,790 --> 00:06:35,260
>> Mbajtur shkuar nëpër lista
përsëri dhe përsëri dhe përsëri.

154
00:06:35,260 --> 00:06:39,160
Sepse Insight kyç atje ishte vetëm
një herë ju kam shikuar gjatë gjithë rrugës për

155
00:06:39,160 --> 00:06:42,500
fundi i listës mund të jenë të sigurt
se elementi keni zgjedhur ishte

156
00:06:42,500 --> 00:06:45,560
me të vërtetë elementi aktualisht i vogël.

157
00:06:45,560 --> 00:06:48,920
Pra, këto modele të ndryshme mendore fundi
up japin disa shumë të vërtetë të botës

158
00:06:48,920 --> 00:06:53,130
Dallimet për ne, si këto
dallimet teorike asymptotic.

159
00:06:53,130 --> 00:06:56,910
>> Pra, vetëm për radhitje, pastaj, i madh o n
katror, ​​ne kemi parë një të tillë pak

160
00:06:56,910 --> 00:06:58,350
Algoritme deri tani.

161
00:06:58,350 --> 00:06:59,580
Madhe O prej n?

162
00:06:59,580 --> 00:07:02,870
Çfarë është një algoritmi që mund të
të thuhet të jetë i madh o n?

163
00:07:02,870 --> 00:07:06,930
Në rastin më të keq, ai merr
një numër i hapave linear.

164
00:07:06,930 --> 00:07:07,810
>> OK, kërko lineare.

165
00:07:07,810 --> 00:07:10,470
Dhe në rastin më të keq, ku është
Elementi ju jeni duke kërkuar për kur

166
00:07:10,470 --> 00:07:12,950
aplikoni kërkim linear?

167
00:07:12,950 --> 00:07:14,680
>> Rregull, ne rastin keq,
kjo nuk është edhe atje.

168
00:07:14,680 --> 00:07:17,000
Ose në rastin e dytë më të keq, kjo është
të gjitha rrugën në fund, e cila është

169
00:07:17,000 --> 00:07:18,880
-plus ose minus-një-hap ndryshim.

170
00:07:18,880 --> 00:07:21,180
Pra, në fund të ditës,
ne mund të themi se është linear.

171
00:07:21,180 --> 00:07:23,910
Big O n do të jenë kërkim linear,
sepse në rastin më të keq,

172
00:07:23,910 --> 00:07:26,610
element nuk është edhe atje apo kjo është
të gjitha rrugën në fund.

173
00:07:26,610 --> 00:07:29,370
>> Well, Big O i log e n.

174
00:07:29,370 --> 00:07:32,760
Ne nuk flasim në hollësi të madhe në lidhje me
këtë, por ne kemi parë këtë më parë.

175
00:07:32,760 --> 00:07:36,840
Çfarë shkon në të ashtuquajturat logaritmike
kohë, në rastin më të keq?

176
00:07:36,840 --> 00:07:38,500
>> Yeah, kështu që kërko binar.

177
00:07:38,500 --> 00:07:42,930
Dhe kërko binar në rastin më të keq
mund të ketë elementin diku në

178
00:07:42,930 --> 00:07:45,640
mesme, apo diku
brenda vektorit.

179
00:07:45,640 --> 00:07:48,040
Por ju të gjeni vetëm atë një herë ju
ndajnë listën në gjysmë, në

180
00:07:48,040 --> 00:07:48,940
gjysmë, në gjysmë, në gjysmë.

181
00:07:48,940 --> 00:07:50,200
Dhe pastaj voila, ajo është aty.

182
00:07:50,200 --> 00:07:52,500
Ose përsëri, rasti më i keq,
kjo nuk është edhe atje.

183
00:07:52,500 --> 00:07:56,770
Por ju nuk e dini se kjo nuk është atje
derisa ju lloj i të arrijnë që zgjasin

184
00:07:56,770 --> 00:08:00,470
bottom-shumica elemente nga përgjysmimi
dhe përgjysmimi dhe pergjysmimin.

185
00:08:00,470 --> 00:08:01,400
>> Big O i 1.

186
00:08:01,400 --> 00:08:03,540
Kështu që ne mund madhe O 2 O, i madh prej 3.

187
00:08:03,540 --> 00:08:06,260
Çdoherë ju doni vetëm një numër konstant,
Ne vetëm lloj të vetëm të thjeshtojë

188
00:08:06,260 --> 00:08:07,280
se si Big O i 1.

189
00:08:07,280 --> 00:08:10,440
Edhe pse në qoftë se realisht, ajo merr
2 apo edhe 100 hapa, në qoftë se kjo është një

190
00:08:10,440 --> 00:08:13,680
Numri i vazhdueshëm i hapave,
ne vetëm të themi O e madhe e 1.

191
00:08:13,680 --> 00:08:15,930
Çfarë është një algoritmi që është
në Big O e 1?

192
00:08:15,930 --> 00:08:18,350
>> Audienca: Gjetja gjatësinë
e një variable.

193
00:08:18,350 --> 00:08:21,090
>> DAVID Malan: Gjetja
gjatësia e një variable?

194
00:08:21,090 --> 00:08:23,870
>> Audienca: Jo, gjatësia
në qoftë se ajo është renditur tashmë.

195
00:08:23,870 --> 00:08:24,160
>> DAVID Malan: Mirë.

196
00:08:24,160 --> 00:08:27,850
OK, kështu që gjetja gjatësinë e diçka
nëse gjatësia e atij diçka, si

197
00:08:27,850 --> 00:08:30,020
një grup, është ruajtur në disa ndryshore.

198
00:08:30,020 --> 00:08:33,380
Sepse vetëm ju mund të lexoni ndryshore,
ose printoni ndryshore, ose

199
00:08:33,380 --> 00:08:34,960
vetëm në përgjithësi të hyrë në këtë variabël.

200
00:08:34,960 --> 00:08:37,299
Dhe voila, që merr kohë konstante.

201
00:08:37,299 --> 00:08:38,909
>> Nga ana tjetër, mendoj se mbrapa për të zeroja.

202
00:08:38,909 --> 00:08:42,460
Mendoni përsëri për javën e parë të C,
duke e quajtur vetëm printf dhe shtypje

203
00:08:42,460 --> 00:08:46,240
diçka në ekran është ndoshta
Ora konstante, sepse ajo merr vetëm

204
00:08:46,240 --> 00:08:50,880
numrin e disa cikle CPU për të treguar
se tekst në ekran.

205
00:08:50,880 --> 00:08:52,720
Apo prisni - e bën atë?

206
00:08:52,720 --> 00:08:56,430
Si tjetër mund të modelojnë ne
Performanca e printf?

207
00:08:56,430 --> 00:09:00,420
Dikush do të donte të pajtohen, se
ndoshta kjo nuk është hera e vërtetë konstante?

208
00:09:00,420 --> 00:09:03,600
Në çfarë kuptimi mund të printf është drejtimin e
kohë, në të vërtetë shtypjen e një varg në

209
00:09:03,600 --> 00:09:05,580
ekran, të jetë diçka e
përveç konstante.

210
00:09:05,580 --> 00:09:07,860
>> Audienca: [padëgjueshme].

211
00:09:07,860 --> 00:09:08,230
>> DAVID Malan: Po.

212
00:09:08,230 --> 00:09:09,300
Pra, kjo varet nga këndvështrimi ynë.

213
00:09:09,300 --> 00:09:13,390
Nëse ne mendojmë në fakt e kontributit të
printf si string, dhe

214
00:09:13,390 --> 00:09:16,380
prandaj ne të matur madhësinë e që
input nga gjatësinë e saj - kështu që le ta quajmë

215
00:09:16,380 --> 00:09:17,780
se gjatësia n si edhe -

216
00:09:17,780 --> 00:09:21,990
ndoshta, printf është në vetvete O i madh n
sepse ajo do të marrë ju n hapat

217
00:09:21,990 --> 00:09:24,750
të shtypura nga secili prej atyre n
karaktere, më shumë gjasa.

218
00:09:24,750 --> 00:09:27,730
Të paktën në atë masë që ne supozojmë
se ndoshta ajo është duke përdorur një për lak

219
00:09:27,730 --> 00:09:28,560
nën kapuç.

220
00:09:28,560 --> 00:09:30,860
>> Por ne do të duhet të shikojmë në se
kod për të kuptuar atë më mirë.

221
00:09:30,860 --> 00:09:33,650
Dhe me të vërtetë, sapo ju të filloni djema
analizimin algoritme tuaja, ju do të

222
00:09:33,650 --> 00:09:34,900
fjalë për fjalë të bëjë vetëm se.

223
00:09:34,900 --> 00:09:37,765
Lloj kokërdhok kodin tuaj dhe mendoni
rreth - të gjithë të drejtë, unë kam këtë lak

224
00:09:37,765 --> 00:09:41,870
këtu, ose unë kam një sythe mbivendosur këtu,
që do të bëjë gjëra N n herë,

225
00:09:41,870 --> 00:09:46,050
dhe ju mund të lloj i arsyes në rrugën tuaj
me anë të kodit, edhe nëse ajo është

226
00:09:46,050 --> 00:09:47,980
pseudokod dhe jo kodin aktual.

227
00:09:47,980 --> 00:09:49,730
>> Pra, çka në lidhje me omega e n katror?

228
00:09:49,730 --> 00:09:53,582
Cila ishte një algoritmi që në më të mirë
rasti, ende mori n hapa kuadratuar?

229
00:09:53,582 --> 00:09:54,014
Po?

230
00:09:54,014 --> 00:09:54,880
>> Audienca: [padëgjueshme].

231
00:09:54,880 --> 00:09:55,900
>> DAVID Malan: lloj Pra përzgjedhjes.

232
00:09:55,900 --> 00:09:59,150
Sepse në atë problem të vërtetë të reduktohet
për faktin se përsëri, unë nuk e di

233
00:09:59,150 --> 00:10:02,600
Unë e kam gjetur më të vogël deri tanishme
Unë e kam kontrolluar të gjitha elementet e mallkuar.

234
00:10:02,600 --> 00:10:08,050
Pra, omega, të themi, n, ne
ardhur vetëm me një.

235
00:10:08,050 --> 00:10:09,300
Lloj futje.

236
00:10:09,300 --> 00:10:12,370
Nëse lista ndodh të jenë të renditura sipas
tashmë, në rastin më të mirë që ne sapo kemi

237
00:10:12,370 --> 00:10:15,090
të bëjë një të kalojë nëpërmjet saj,
në të cilën pikë ne jemi të sigurt.

238
00:10:15,090 --> 00:10:17,890
Dhe pastaj që mund të thuhet
të jetë linear, për sigurt.

239
00:10:17,890 --> 00:10:20,570
>> Po në lidhje me omega e 1?

240
00:10:20,570 --> 00:10:23,790
Çfarë, në rastin më të mirë, mund të marrë
një numër konstant i hapave?

241
00:10:23,790 --> 00:10:27,220
Kërko Pra linear, në qoftë se ju vetëm të merrni me fat
dhe elementi ju jeni në kërkim

242
00:10:27,220 --> 00:10:31,000
është e drejtë në fillim të listës,
nëse kjo është ajo ku ju jeni tuaj duke filluar

243
00:10:31,000 --> 00:10:33,070
linear traversal e atë listë.

244
00:10:33,070 --> 00:10:35,180
>> Dhe kjo është e vërtetë për një
Numri i gjërave.

245
00:10:35,180 --> 00:10:37,660
Për shembull, edhe binar
kërko është omega e 1.

246
00:10:37,660 --> 00:10:40,310
Sepse çfarë nëse ju merrni të vërtetë i mallkuar
fat dhe mu-çik në mes të

247
00:10:40,310 --> 00:10:42,950
array juaj është numri i
ju jeni duke kërkuar për të?

248
00:10:42,950 --> 00:10:45,730
Kështu që ju mund të merrni me fat atje, si edhe.

249
00:10:45,730 --> 00:10:49,190
>> Kjo, së fundi, omega e n log n.

250
00:10:49,190 --> 00:10:52,573
Pra, n log n, ne nuk e bëri me të vërtetë
flasim rreth ende, por -

251
00:10:52,573 --> 00:10:53,300
>> Audienca: Merge lloj?

252
00:10:53,300 --> 00:10:53,960
>> DAVID Malan: lloj Merge.

253
00:10:53,960 --> 00:10:56,920
Kjo ishte cliffhanger i kohës së fundit,
ku kemi propozuar, dhe kemi treguar

254
00:10:56,920 --> 00:10:58,600
vizualisht, se nuk janë algoritme.

255
00:10:58,600 --> 00:11:02,470
Dhe të shkrihej vetëm një lloj të tillë
algoritmi që është krejtësisht i shpejtë

256
00:11:02,470 --> 00:11:03,450
se disa prej këtyre guys tjera.

257
00:11:03,450 --> 00:11:07,800
Në fakt, shkrihen shkurtër është jo vetëm në
Rasti më i mirë n log n, në më të keq

258
00:11:07,800 --> 00:11:09,460
Rasti n log n.

259
00:11:09,460 --> 00:11:14,540
Dhe kur ju e keni këtë rastësi e
omega dhe të mëdha o të qenit e njëjta gjë?

260
00:11:14,540 --> 00:11:17,310
Ne fakt mund të përshkruajnë se sa ajo që është
quajtur Theta, edhe pse kjo është një

261
00:11:17,310 --> 00:11:18,220
më pak të zakonshme.

262
00:11:18,220 --> 00:11:21,730
Por kjo vetëm do të thotë të dy kufijtë,
në këtë rast, janë të njëjta.

263
00:11:21,730 --> 00:11:25,770
>> Pra bashkojë lloj, çfarë e bën këtë
vërtetë të valoj poshtë për të për ne?

264
00:11:25,770 --> 00:11:27,000
E pra, kujtojnë motivimin.

265
00:11:27,000 --> 00:11:30,340
Më lejoni të tërheq lart një animacion që
ne nuk e shohim në kohën e fundit.

266
00:11:30,340 --> 00:11:33,390
Kjo, të njëjtën ide, por
kjo është një pak më të mëdha.

267
00:11:33,390 --> 00:11:36,160
Dhe unë jam duke shkuar për të shkuar përpara dhe të theksojnë
parë - ne kemi lloj futje në

268
00:11:36,160 --> 00:11:39,410
lart majtas, pastaj lloj përzgjedhje,
lloj flluskë, një çift i llojet e tjera -

269
00:11:39,410 --> 00:11:42,670
shell dhe të shpejtë - se ne nuk kemi biseduar
rreth, dhe tog dhe të shkrihej lloj.

270
00:11:42,670 --> 00:11:47,090
>> Pra, të paktën të përpiqet të përqëndrohet sytë tuaj në
lartë tre në majtë dhe pastaj

271
00:11:47,090 --> 00:11:49,120
bashkojë lloj kur unë klikoni
kjo shigjetë e gjelbër.

272
00:11:49,120 --> 00:11:51,900
Por unë do të le të gjithë ata të kandiduar, vetëm për të
t'ju japë një ndjenjë të diversitetit të

273
00:11:51,900 --> 00:11:53,980
algoritme që ekzistojnë në botë.

274
00:11:53,980 --> 00:11:56,180
Unë jam duke shkuar për këtë le të kandidojë
për vetëm disa sekonda.

275
00:11:56,180 --> 00:11:59,640
Dhe në qoftë se ju të përqëndrohet sytë tuaj - marr një
algorithm, të përqëndrohet në atë për vetëm një

276
00:11:59,640 --> 00:12:02,970
sekonda - ju do të fillojnë të shohin
model që ajo zbaton.

277
00:12:02,970 --> 00:12:04,530
>> Merge lloj, njoftimi, është bërë.

278
00:12:04,530 --> 00:12:06,430
Lloj tog, të shpejtë, lloj shell -

279
00:12:06,430 --> 00:12:09,480
kështu që ajo duket ne kemi prezantuar tre
Algoritme keq javën e kaluar.

280
00:12:09,480 --> 00:12:12,960
Por kjo është mirë që ne jemi këtu sot për të
po në lloj bashkohen, e cila është një prej

281
00:12:12,960 --> 00:12:16,500
ato lehtë është që të shikojmë në të, madje edhe
edhe pse ajo ndoshta do të bëj mendjen tuaj

282
00:12:16,500 --> 00:12:17,490
vetëm pak.

283
00:12:17,490 --> 00:12:21,130
Këtu ne mund të shohim se sa shumë
lloj përzgjedhje sucks.

284
00:12:21,130 --> 00:12:24,600
>> Por në anën rrokullisje, kjo është
të vërtetë e lehtë për t'u zbatuar.

285
00:12:24,600 --> 00:12:28,160
Dhe ndoshta për Set P 3, kjo është një nga
Algoritme keni zgjedhur për të zbatuar

286
00:12:28,160 --> 00:12:28,960
për edicionin standard.

287
00:12:28,960 --> 00:12:30,970
Perfectly gjobë, të përkryer i saktë.

288
00:12:30,970 --> 00:12:35,210
>> Por përsëri, si n merr të mëdha, në qoftë se ju
të zgjedhin për të zbatuar një algoritëm të shpejtë

289
00:12:35,210 --> 00:12:39,020
doja bashkojë lloj, shanset janë të mëdha dhe në
inputeve të mëdha, kodi juaj është vetëm

290
00:12:39,020 --> 00:12:39,800
duke shkuar për të kandiduar më të shpejtë.

291
00:12:39,800 --> 00:12:41,090
Faqja juaj e internetit do të punojnë më mirë.

292
00:12:41,090 --> 00:12:42,650
Përdoruesit e juaj do të jetë i lumtur.

293
00:12:42,650 --> 00:12:45,280
Dhe kështu që nuk janë këto efekte
e vërtetë duke i dhënë

294
00:12:45,280 --> 00:12:47,350
ne disa menduar thellë.

295
00:12:47,350 --> 00:12:49,990
>> Pra, le të marrin një vështrim në atë që bashkohen
Rendit është në të vërtetë të gjithë rreth.

296
00:12:49,990 --> 00:12:52,992
Gjëja e ftohtë është që të bashkojë
lloj është vetëm kjo.

297
00:12:52,992 --> 00:12:56,300
Kjo është, përsëri, ajo që ne e kemi quajtur
pseudokod, qenia pseudokod

298
00:12:56,300 --> 00:12:57,720
Anglisht-si sintaksa.

299
00:12:57,720 --> 00:12:59,890
Dhe thjeshtësia është
lloj i interesante.

300
00:12:59,890 --> 00:13:02,840
>> Pra, në futjen e elementeve n - kështu që
thjesht do të thotë, këtu është një koleksion.

301
00:13:02,840 --> 00:13:04,000
Ajo e mori gjërat n në të.

302
00:13:04,000 --> 00:13:05,370
Kjo është e gjitha që ne jemi duke thënë atje.

303
00:13:05,370 --> 00:13:07,560
>> Nëse n është më pak se 2, kthehen.

304
00:13:07,560 --> 00:13:08,640
Pra, kjo është vetëm rasti i parëndësishëm.

305
00:13:08,640 --> 00:13:12,580
Nëse n është më pak se 2, atëherë padyshim që kjo është
0 ose 1, në të cilin rast gjë

306
00:13:12,580 --> 00:13:14,780
është renditur tashmë ose nuk ekzistojnë,
kështu që vetëm të kthehen.

307
00:13:14,780 --> 00:13:15,900
Nuk ka asgjë për të bërë.

308
00:13:15,900 --> 00:13:18,360
Pra, kjo është një rast i thjeshtë të këpusin off.

309
00:13:18,360 --> 00:13:20,110
>> Tjetër, ne kemi tre hapa.

310
00:13:20,110 --> 00:13:23,650
Sort gjysmën e majtë të elementeve, lloj
gjysma e drejta e elementeve,

311
00:13:23,650 --> 00:13:26,650
dhe pastaj të bashkojë gjysmave renditen.

312
00:13:26,650 --> 00:13:29,400
Ajo që është interesante këtu është se
Unë jam natyrë e punting, e drejtë?

313
00:13:29,400 --> 00:13:32,300
Nuk është lloj i një përkufizim rrethore
të këtij algoritmi.

314
00:13:32,300 --> 00:13:35,986
Në çfarë kuptimi është ky algoritëm të
rrethore definicion?

315
00:13:35,986 --> 00:13:37,850
>> Audienca: [padëgjueshme].

316
00:13:37,850 --> 00:13:41,670
>> DAVID Malan: Yeah, Algoritmi im sorting,
dy hapat e saj janë "lloj

317
00:13:41,670 --> 00:13:44,640
diçka. "Dhe kështu që ngre
pyetja, mirë, çfarë jam unë do të përdorin

318
00:13:44,640 --> 00:13:46,460
për të zgjidhur gjysmën e majtë
dhe gjysma e drejtë?

319
00:13:46,460 --> 00:13:49,600
Dhe bukuria këtu është se edhe pse
përsëri, kjo është mendje-bending

320
00:13:49,600 --> 00:13:54,030
Pjesa potencialisht, ju mund të përdorni të njëjtën
algorithm për të zgjidhur gjysmën e majtë.

321
00:13:54,030 --> 00:13:54,700
>> Por, prit një minutë.

322
00:13:54,700 --> 00:13:57,070
Kur ju jeni duke thënë për të zgjidhur
gjysma e majtë, çfarë janë dy

323
00:13:57,070 --> 00:13:58,240
Hapat do të jetë e ardhshme?

324
00:13:58,240 --> 00:14:00,550
Ne do të zgjidhur gjysmën e majtë të
gjysma e majtë dhe të djathtë

325
00:14:00,550 --> 00:14:01,420
gjysma e gjysmës së majtë.

326
00:14:01,420 --> 00:14:04,430
Damn, si nuk kam zgjidhur ato dy
gjysmave, apo lagjet, tani?

327
00:14:04,430 --> 00:14:05,260
>> Por kjo është OK.

328
00:14:05,260 --> 00:14:07,830
Ne kemi një algoritëm sorting këtu.

329
00:14:07,830 --> 00:14:10,660
Dhe, edhe pse ju mund të shqetësohen në
parë kjo është lloj i një infinit

330
00:14:10,660 --> 00:14:12,780
loop, kjo është një cikël që kurrë nuk është
duke shkuar për t'i dhënë fund - kjo do të

331
00:14:12,780 --> 00:14:15,770
të përfundojë një herë se çfarë ndodh?

332
00:14:15,770 --> 00:14:16,970
Pasi n është më pak se 2.

333
00:14:16,970 --> 00:14:19,180
E cila përfundimisht do të ndodhë,
sepse në qoftë se ju mbani dhe pergjysmimin

334
00:14:19,180 --> 00:14:23,020
përgjysmimi i përgjysmuar në këto gjysmave, me siguri
përfundimisht ju jeni do të përfundojë

335
00:14:23,020 --> 00:14:25,350
deri me vetëm 1 ose 0 elementeve.

336
00:14:25,350 --> 00:14:28,500
Në cilën pikë, ky algoritëm
thotë se ju jeni bërë.

337
00:14:28,500 --> 00:14:31,020
>> Pra, magjia e vërtetë në këtë
algorithm duket të jetë në

338
00:14:31,020 --> 00:14:33,470
se hapi final, bashkimi.

339
00:14:33,470 --> 00:14:37,190
Kjo ide e thjeshtë vetëm për bashkimin e dy
gjërat, kjo është ajo që po ndodh në fund të fundit

340
00:14:37,190 --> 00:14:40,920
për të na lejuar për të zgjidhur një sërë,
le të themi, tetë elemente.

341
00:14:40,920 --> 00:14:44,410
Pra, unë kam tetë më shumë topa stresit up
këtu, tetë copa të letrës, dhe një

342
00:14:44,410 --> 00:14:45,500
Google Glass -

343
00:14:45,500 --> 00:14:46,140
që unë të marrë për të mbajtur.

344
00:14:46,140 --> 00:14:46,960
>> [Qeshura]

345
00:14:46,960 --> 00:14:48,970
>> DAVID Malan: Nëse ne mund të marrë tetë
vullnetarë, dhe le të shohim nëse ne mund të

346
00:14:48,970 --> 00:14:51,430
luajë këtë jashtë, kështu.

347
00:14:51,430 --> 00:14:52,500
Wow, OK.

348
00:14:52,500 --> 00:14:53,565
Shkenca kompjuterike është duke fun.

349
00:14:53,565 --> 00:14:54,320
Dakord.

350
00:14:54,320 --> 00:14:57,770
Pra, si në lidhje me ju tre,
dora më e madhe deri atje.

351
00:14:57,770 --> 00:14:58,580
Katër në shpinë.

352
00:14:58,580 --> 00:15:02,220
Dhe si për ne do të bëjmë ty
tri në këtë rresht?

353
00:15:02,220 --> 00:15:03,390
Dhe katër në pjesën e përparme.

354
00:15:03,390 --> 00:15:04,920
Pra, ju tetë, vijnë më lart.

355
00:15:04,920 --> 00:15:12,060
>> [Qeshura]

356
00:15:12,060 --> 00:15:13,450
>> DAVID Malan: Unë jam në të vërtetë
nuk jeni të sigurt se çfarë është ajo.

357
00:15:13,450 --> 00:15:14,810
A është kjo topat e stresit?

358
00:15:14,810 --> 00:15:16,510
Llambat tavolinë?

359
00:15:16,510 --> 00:15:18,650
Materiali?

360
00:15:18,650 --> 00:15:19,680
Internet?

361
00:15:19,680 --> 00:15:20,160
>> OK.

362
00:15:20,160 --> 00:15:21,310
Pra, vijnë më lart.

363
00:15:21,310 --> 00:15:22,310
Kush do të donte -

364
00:15:22,310 --> 00:15:23,570
të mbajtur të vijnë deri.

365
00:15:23,570 --> 00:15:24,240
Le të shohim.

366
00:15:24,240 --> 00:15:26,460
Dhe kjo ju vë në vend -

367
00:15:26,460 --> 00:15:27,940
ju jeni në një vend.

368
00:15:27,940 --> 00:15:28,670
Uh-oh, prit një minutë.

369
00:15:28,670 --> 00:15:30,760
1, 2, 3, 4, 5, 6, 7 - Oh, mirë.

370
00:15:30,760 --> 00:15:31,310
Të gjithë të drejtë, ne jemi të mirë.

371
00:15:31,310 --> 00:15:35,130
Të gjithë të drejtë, kështu që të gjithë të kenë një vend,
por jo në gotë Google.

372
00:15:35,130 --> 00:15:36,475
Më lejoni në radhë këto deri.

373
00:15:36,475 --> 00:15:37,115
Cili është emri juaj?

374
00:15:37,115 --> 00:15:37,440
>> MICHELLE: Michelle.

375
00:15:37,440 --> 00:15:38,090
>> DAVID Malan: Michelle?

376
00:15:38,090 --> 00:15:42,000
Të gjithë të drejtë, ju merrni për të duken si
geek, nëse kjo është OK.

377
00:15:42,000 --> 00:15:44,625
E pra, unë bëj shumë, unë mendoj,
për vetëm një moment.

378
00:15:44,625 --> 00:15:45,875
Të gjithë të drejtë, gatishmëri.

379
00:15:45,875 --> 00:15:48,510

380
00:15:48,510 --> 00:15:50,950
Ne kemi qenë duke u përpjekur për të dalë me një
përdorin rastin për Google qelqi, dhe ne

381
00:15:50,950 --> 00:15:53,750
menduar se do të jetë kënaqësi për të vetëm të bëjë
kjo kur njerëzit janë në skenë.

382
00:15:53,750 --> 00:15:57,120
Ne do të regjistrojnë botën
nga perspektiva e tyre.

383
00:15:57,120 --> 00:15:58,410
Dakord.

384
00:15:58,410 --> 00:15:59,830
Ndoshta jo atë që Google menduar.

385
00:15:59,830 --> 00:16:02,260
Të gjithë të drejtë, në qoftë se ju nuk do mend të veshur
kjo për minutat e ardhshme vështirë,

386
00:16:02,260 --> 00:16:03,150
që do të jetë e mrekullueshme.

387
00:16:03,150 --> 00:16:08,620
>> Të gjithë të drejtë, kështu që ne kemi këtu një grup të
elemente, dhe se array, si për

388
00:16:08,620 --> 00:16:11,480
copa të letrës në këto folks '
Duart, është Unsorted aktualisht.

389
00:16:11,480 --> 00:16:12,050
>> MICHELLE: Oh, kjo është aq i çuditshëm.

390
00:16:12,050 --> 00:16:12,810
>> DAVID Malan: Është shumë e shumë të rastit.

391
00:16:12,810 --> 00:16:15,760
Dhe në një moment të vetëm, ne jemi duke shkuar për të përpiqen
për të zbatuar lloj bashkojë së bashku

392
00:16:15,760 --> 00:16:17,950
dhe të shohim se ku Insajt është çelësi.

393
00:16:17,950 --> 00:16:21,970
Dhe Mashtrim këtu me lloj Merge është
diçka që ne nuk kemi marrë ende.

394
00:16:21,970 --> 00:16:24,030
Ne në të vërtetë nevojë për disa
hapësirë ​​shtesë.

395
00:16:24,030 --> 00:16:26,650
Pra, çfarë do të jetë veçanërisht e
interesante në lidhje me këtë është se këto

396
00:16:26,650 --> 00:16:29,270
djema jeni duke shkuar për të lëvizur rreth pak
bit, sepse unë jam duke shkuar për të supozojmë se

397
00:16:29,270 --> 00:16:31,880
ka një grup shtesë e hapësirës,
thonë, e drejtë pas tyre.

398
00:16:31,880 --> 00:16:34,570
>> Pra, nëse ata janë prapa karrige e tyre,
kjo është array mesme.

399
00:16:34,570 --> 00:16:36,960
Nëse ata janë ulur këtu, kjo është
array primar.

400
00:16:36,960 --> 00:16:40,170
Por kjo është një burim që kemi
nuk leveraged deri tani me flluskë

401
00:16:40,170 --> 00:16:42,040
lloj, lloj me përzgjedhjes,
me lloj futje.

402
00:16:42,040 --> 00:16:44,600
Kujtojnë javën e kaluar, të gjithë vetëm
lloj riorganizoi në vend.

403
00:16:44,600 --> 00:16:46,840
Ata nuk përdorin asnjë memorie shtesë.

404
00:16:46,840 --> 00:16:49,310
Ne kemi bërë dhomë për njerëzit nga
lëvizjen e njerëzve përreth.

405
00:16:49,310 --> 00:16:50,580
>> Pra, kjo është një pasqyrë kyç, too.

406
00:16:50,580 --> 00:16:53,410
Ka kjo tregti-off, në përgjithësi në
shkenca kompjuterike, të burimeve.

407
00:16:53,410 --> 00:16:55,800
Nëse ju doni që të përshpejtojë diçka
si kohë, ju do të jeni të

408
00:16:55,800 --> 00:16:56,900
duhet të paguajnë një çmim.

409
00:16:56,900 --> 00:17:00,750
Dhe një nga këto çmime është shumë shpesh
, hapësirë ​​shuma e kujtesës ose të vështirë

410
00:17:00,750 --> 00:17:01,700
disk hapësirë ​​që ju jeni duke përdorur.

411
00:17:01,700 --> 00:17:03,640
Ose, sinqerisht, shuma
e kohës programues.

412
00:17:03,640 --> 00:17:06,700
Sa kohë ju merr, njeriut,
që në fakt të zbatojë disa më shumë

413
00:17:06,700 --> 00:17:07,829
algorithm e komplikuar.

414
00:17:07,829 --> 00:17:09,760
Por, për sot, trade-off
është koha dhe hapësira.

415
00:17:09,760 --> 00:17:11,930
>> Pra, nëse ju djema mund vetëm të mbajë deri tuaj
numrat në mënyrë që ne mund të shohim se ju jeni

416
00:17:11,930 --> 00:17:15,839
në të vërtetë përputhen 4, 2, 6, 1, 3, 7, 8.

417
00:17:15,839 --> 00:17:16,599
Excellent.

418
00:17:16,599 --> 00:17:19,520
Kështu që unë jam duke shkuar për të mundohet të orkestrojë
gjërat, në qoftë se ju djema mund vetëm

419
00:17:19,520 --> 00:17:21,800
ndjekin shembullin tim këtu.

420
00:17:21,800 --> 00:17:26,650
>> Kështu që unë jam duke shkuar për të zbatuar, së pari,
Hapi i parë i pseudokod, e cila është

421
00:17:26,650 --> 00:17:29,440
në informacionin e elementeve n, nëse n është
më pak se 2, pastaj do të ktheheni.

422
00:17:29,440 --> 00:17:31,370
Natyrisht, kjo nuk e bën
zbatohen, kështu që ne të lëvizë.

423
00:17:31,370 --> 00:17:33,340
Pra zgjidhur gjysmën e majtë të elementeve.

424
00:17:33,340 --> 00:17:36,220
Kështu që do të thotë që unë jam duke shkuar për Fokusi im
Vëmendje për një moment të vetëm në këto

425
00:17:36,220 --> 00:17:37,310
katër djema këtu.

426
00:17:37,310 --> 00:17:39,774
Të gjithë të drejtë, çfarë unë bëj më tej?

427
00:17:39,774 --> 00:17:40,570
>> Audienca: Sort gjysmën e majtë.

428
00:17:40,570 --> 00:17:42,780
>> DAVID Malan: Deri tani unë kam për të zgjidhur
gjysma e majtë të këtyre guys.

429
00:17:42,780 --> 00:17:45,580
Sepse përsëri, të marrë për veten e
Qëllimi është për të zgjidhur gjysmën e majtë.

430
00:17:45,580 --> 00:17:46,440
Si do të bëni këtë?

431
00:17:46,440 --> 00:17:49,140
Vetëm ndiqni udhëzimet, madje edhe
edhe pse ne jemi duke bërë atë përsëri.

432
00:17:49,140 --> 00:17:50,160
Pra zgjidhur gjysmën e majtë.

433
00:17:50,160 --> 00:17:52,030
Tani unë jam sorting këto dy djem.

434
00:17:52,030 --> 00:17:53,563
Çfarë vjen më pas?

435
00:17:53,563 --> 00:17:54,510
>> Audienca: Sort gjysmën e majtë.

436
00:17:54,510 --> 00:17:55,460
>> DAVID Malan: Sort gjysmën e majtë.

437
00:17:55,460 --> 00:18:00,680
Deri tani këto, ky vend këtu,
eshte nje lista e madhësisë 1.

438
00:18:00,680 --> 00:18:01,365
Dhe çfarë është emri juaj përsëri?

439
00:18:01,365 --> 00:18:02,390
>> PRINCESS DAISY: Princesha Daisy.

440
00:18:02,390 --> 00:18:03,690
>> DAVID Malan: Princesha Daisy është këtu.

441
00:18:03,690 --> 00:18:07,470
Dhe kështu që ajo është e renditura tashmë, sepse
lista është e madhësisë 1.

442
00:18:07,470 --> 00:18:09,490
Çfarë unë bëj tjetër?

443
00:18:09,490 --> 00:18:13,680
OK, të kthehen, për shkak se lista është e
madhësi 1, e cila është më pak se 2.

444
00:18:13,680 --> 00:18:14,320
Atëherë çfarë është hapi tjetër?

445
00:18:14,320 --> 00:18:17,490
Dhe tani ju duhet të lloj
backtrack në mendjen tuaj.

446
00:18:17,490 --> 00:18:19,340
>> Sort gjysmën e drejtë, e cila është -

447
00:18:19,340 --> 00:18:19,570
çfarë është emri juaj?

448
00:18:19,570 --> 00:18:20,220
>> LINDA: Linda.

449
00:18:20,220 --> 00:18:20,980
>> DAVID Malan: Linda.

450
00:18:20,980 --> 00:18:23,210
Dhe kështu që çfarë të bëjmë tani që
ne kemi një listë të madhësisë 1?

451
00:18:23,210 --> 00:18:24,440
>> Audienca: Kthimi.

452
00:18:24,440 --> 00:18:24,760
>> DAVID Malan: Kujdes.

453
00:18:24,760 --> 00:18:29,540
Ne kthim parë, dhe tani e treta
hap - dhe në qoftë se unë lloj i përshkruaj atë duke

454
00:18:29,540 --> 00:18:33,490
përqafuar dy vende tani, tani unë
duhet të bashkojë këto dy elemente.

455
00:18:33,490 --> 00:18:35,530
Deri tani për fat të keq, elementet
janë jashtë funksionit.

456
00:18:35,530 --> 00:18:39,920
Por kjo është ajo ku procesi i bashkimit
fillon të marrë imponues.

457
00:18:39,920 --> 00:18:42,410
>> Pra, nëse ju djema mund të ngriteni për vetëm
një moment, unë jam duke shkuar për nevojë për ty, në një

458
00:18:42,410 --> 00:18:44,170
moment, që të hap prapa karrige tuaj.

459
00:18:44,170 --> 00:18:46,480
Dhe në qoftë se Linda, 2 sepse është
vogël se 4, pse nuk e bëjnë

460
00:18:46,480 --> 00:18:48,130
keni ardhur rreth e parë?

461
00:18:48,130 --> 00:18:48,690
Qëndro aty.

462
00:18:48,690 --> 00:18:50,520
Pra Linda, ju vijnë rreth e parë.

463
00:18:50,520 --> 00:18:53,820
>> Tani në realitet në qoftë se ajo është vetëm një koleksion
Ne vetëm mund të lëvizin atë në kohë reale

464
00:18:53,820 --> 00:18:55,360
nga kjo karrige në këtë vend.

465
00:18:55,360 --> 00:18:57,770
Pra, imagjinoni se mori disa konstante
Numri i hapa 1.

466
00:18:57,770 --> 00:18:58,480
Dhe tani -

467
00:18:58,480 --> 00:19:01,490
por ne kemi nevojë për të vënë ju në
vendndodhja e parë këtu.

468
00:19:01,490 --> 00:19:03,930
>> Dhe tani, nëse ju mund të vijnë rreth,
si dhe, ne jemi duke shkuar për

469
00:19:03,930 --> 00:19:06,300
të jetë në vend të dy.

470
00:19:06,300 --> 00:19:09,120
Dhe, edhe pse kjo ndjehet si ajo është
marrjen e një kohë, se çfarë është e bukur tani është

471
00:19:09,120 --> 00:19:14,710
se gjysma e majtë e
gjysma e majtë është renditur tani.

472
00:19:14,710 --> 00:19:18,010
Pra, çfarë ishte hapi i ardhshëm, në qoftë se ne tani
Rewind më tej në histori?

473
00:19:18,010 --> 00:19:18,980
>> Audienca: gjysma e drejta.

474
00:19:18,980 --> 00:19:19,900
>> DAVID Malan: Sort gjysmën e duhur.

475
00:19:19,900 --> 00:19:21,320
Pra, ju djema keni për të bërë këtë, po ashtu.

476
00:19:21,320 --> 00:19:23,510
Pra, nëse ju mund të qëndrojnë deri
për vetëm një çast?

477
00:19:23,510 --> 00:19:25,192
Dhe çfarë është emri juaj?

478
00:19:25,192 --> 00:19:25,540
>> Jess: Jess.

479
00:19:25,540 --> 00:19:25,870
>> DAVID Malan: Jess.

480
00:19:25,870 --> 00:19:29,720
OK, kështu që tani është Jess majtë
gjysma e pjesës së djathtë.

481
00:19:29,720 --> 00:19:31,400
Dhe kështu që ajo është një listë e madhësisë 1.

482
00:19:31,400 --> 00:19:32,380
Ajo renditura qartë.

483
00:19:32,380 --> 00:19:33,070
Dhe emri juaj përsëri?

484
00:19:33,070 --> 00:19:33,630
>> MICHELLE: Michelle.

485
00:19:33,630 --> 00:19:35,340
>> DAVID Malan: Michelle është padyshim
një listë e madhësisë 1.

486
00:19:35,340 --> 00:19:36,050
Ajo është renditur tashmë.

487
00:19:36,050 --> 00:19:38,690
Deri tani magji ndodh,
Procesi i bashkimit.

488
00:19:38,690 --> 00:19:39,790
Pra, kush do të vijë më parë?

489
00:19:39,790 --> 00:19:41,560
Michelle Natyrisht.

490
00:19:41,560 --> 00:19:43,280
Pra, nëse ju mund të vijnë rreth mbrapa.

491
00:19:43,280 --> 00:19:47,090
Hapësirë ​​ne kemi në dispozicion për të tani
është e drejtë pas kësaj karrige këtu.

492
00:19:47,090 --> 00:19:51,580
Dhe tani, nëse ju mund të vijnë mbrapa, si edhe,
tani ne kemi, të jetë i qartë, dy

493
00:19:51,580 --> 00:19:53,810
gjysmave, secili prej madhësisë së 2 -

494
00:19:53,810 --> 00:19:57,090
dhe vetëm për hir të pikturim, nëse ju
mund të bëjë një grimë të vogël e një hapësire -

495
00:19:57,090 --> 00:19:59,780
lënë një gjysmë këtu, një
gjysma e drejtë këtu.

496
00:19:59,780 --> 00:20:01,160
>> Rewind më tej në histori.

497
00:20:01,160 --> 00:20:02,270
Cili është hapi tjetër?

498
00:20:02,270 --> 00:20:03,030
>> Audienca: Merge.

499
00:20:03,030 --> 00:20:04,160
>> DAVID Malan: Pra tani ne duhet të bashkohen.

500
00:20:04,160 --> 00:20:07,490
Pra, OK, kështu që tani, fatmirësisht, ne
liruar vetëm deri katër karrige.

501
00:20:07,490 --> 00:20:11,480
Pra, ne kemi përdorur dy herë më shumë memorie, por
ne mund të japim flip-flopping mes

502
00:20:11,480 --> 00:20:12,330
të dy vargjeve.

503
00:20:12,330 --> 00:20:14,190
Pra, numri i të cilëve është që të vijë më parë?

504
00:20:14,190 --> 00:20:14,850
Michelle Pra, natyrisht.

505
00:20:14,850 --> 00:20:16,680
Pra, të vijnë përreth dhe të marrë
vendi juaj këtu.

506
00:20:16,680 --> 00:20:19,120
Dhe pastaj numri 2 është padyshim
ardhshëm, kështu që ju vijnë këtu.

507
00:20:19,120 --> 00:20:21,520
Numri 4, numër 6.

508
00:20:21,520 --> 00:20:23,390
Dhe përsëri, edhe pse ka një
pak e përfshirë në këmbë,

509
00:20:23,390 --> 00:20:26,010
me të vërtetë, këto mund të ndodhë menjëherë,
duke lëvizur një -

510
00:20:26,010 --> 00:20:26,880
OK, luajti mirë.

511
00:20:26,880 --> 00:20:28,350
>> [Qeshura]

512
00:20:28,350 --> 00:20:29,680
>> DAVID Malan: Dhe tani ne jemi
në formë mjaft të mirë.

513
00:20:29,680 --> 00:20:34,910
Gjysma e majtë të tërë
input tani është renditura.

514
00:20:34,910 --> 00:20:37,370
Të gjithë të drejtë, kështu që këta njerëz kishin
Përparësia e time -

515
00:20:37,370 --> 00:20:40,340
si e bëri atë të përfundojnë të gjitha vajzat në
la dhe të gjithë djemtë në të djathtë?

516
00:20:40,340 --> 00:20:42,450
>> OK, kështu që djemtë e 'të kthehet tani.

517
00:20:42,450 --> 00:20:44,680
Kështu që unë nuk do të ecin ju nëpërmjet
këto hapa.

518
00:20:44,680 --> 00:20:46,550
Ne do të shohim nëse ne mund të reapply
pseudokod njëjtë.

519
00:20:46,550 --> 00:20:50,050
Nëse ju doni të shkoni përpara dhe të qëndrojë lart,
dhe ju djema, më lejoni t'ju jap mic.

520
00:20:50,050 --> 00:20:52,990
Shih nëse ju nuk mund të përsëris atë që
ne vetëm e bëri këtu në

521
00:20:52,990 --> 00:20:53,880
fund të tjera të listës.

522
00:20:53,880 --> 00:20:59,530
Kush ka nevojë të flasë i pari,
bazuar në algorithm?

523
00:20:59,530 --> 00:21:03,210
Pra, të shpjegojë se çfarë jeni duke bërë para se të
keni bërë ndonjë lëvizje këmbë.

524
00:21:03,210 --> 00:21:05,930
>> Kryetari 1: Të gjithë të drejtë, kështu që
Unë jam gjysmën e majtë të

525
00:21:05,930 --> 00:21:07,790
gjysma majtas, unë të kthehem.

526
00:21:07,790 --> 00:21:08,730
E drejta?

527
00:21:08,730 --> 00:21:09,250
>> DAVID Malan: Mirë.

528
00:21:09,250 --> 00:21:10,350
>> Kryetari 1: Dhe pastaj -

529
00:21:10,350 --> 00:21:11,800
>> DAVID Malan: Kush bën
mic shkoni në e ardhshëm?

530
00:21:11,800 --> 00:21:12,920
>> Kryetari 1: Numri Next.

531
00:21:12,920 --> 00:21:14,720
>> 2 Gjuha: Pra, unë jam gjysma e djathtë
i pjesës majta e

532
00:21:14,720 --> 00:21:17,830
gjysma e majtë, dhe unë kthehem.

533
00:21:17,830 --> 00:21:18,050
>> DAVID Malan: Mirë.

534
00:21:18,050 --> 00:21:18,550
Ju ktheheni.

535
00:21:18,550 --> 00:21:21,855
Pra, çfarë është tani deri të ardhshëm për ju dy?

536
00:21:21,855 --> 00:21:23,740
>> KRYETARI 2: Ne duam të shohim kush është më i vogël.

537
00:21:23,740 --> 00:21:24,200
>> DAVID Malan: Pikërisht.

538
00:21:24,200 --> 00:21:24,940
Ne duam të bashkohen.

539
00:21:24,940 --> 00:21:27,590
Hapësira që ne jemi duke shkuar për të përdorur të bashkojë
në ju, edhe pse ata janë

540
00:21:27,590 --> 00:21:30,250
renditura qartë tashmë, ne jemi duke shkuar
të ndjekin algorithm njëjtë.

541
00:21:30,250 --> 00:21:31,560
Pra, kush shkon prapa në fillim?

542
00:21:31,560 --> 00:21:35,720
Pra, 3, dhe pastaj 7.

543
00:21:35,720 --> 00:21:38,570
Dhe tani mic shkon
për këta njerëz, OK?

544
00:21:38,570 --> 00:21:43,590
>> Kryetari 3: Pra, unë jam gjysma e drejta e
gjysma e majtë, dhe n im është më pak se

545
00:21:43,590 --> 00:21:45,048
1, kështu që unë jam vetëm duke shkuar për të kaluar -

546
00:21:45,048 --> 00:21:46,380
>> DAVID Malan: Mirë.

547
00:21:46,380 --> 00:21:49,450
>> Kryetari 4: Unë jam gjysma e drejta e
gjysma e drejta e gjysmës së djathtë, dhe unë jam

548
00:21:49,450 --> 00:21:51,740
edhe një person, kështu që unë jam
do të kthehen.

549
00:21:51,740 --> 00:21:52,990
Deri tani ne bashkohen.

550
00:21:52,990 --> 00:21:55,140

551
00:21:55,140 --> 00:21:56,150
>> Kryetari 3: Pra, ne kthehemi.

552
00:21:56,150 --> 00:21:57,160
>> DAVID Malan: Pra, ju shkoni në pjesën e prapme.

553
00:21:57,160 --> 00:21:59,200
Pra 5 shkon e parë, atëherë 8.

554
00:21:59,200 --> 00:22:01,240
Dhe tani audienca, e cila është
hap ne kemi tani Rewind

555
00:22:01,240 --> 00:22:02,200
mbështetur në mendjet tona?

556
00:22:02,200 --> 00:22:02,940
>> Audienca: Merge.

557
00:22:02,940 --> 00:22:07,270
>> DAVID Malan: gjysma Bashkimi majtë dhe të djathtë
gjysma e gjysmës origjinal majtë.

558
00:22:07,270 --> 00:22:08,840
Deri tani -

559
00:22:08,840 --> 00:22:10,520
dhe vetëm për të bërë këtë të qartë,
të bëjë një grimë të vogël të hapësirës

560
00:22:10,520 --> 00:22:11,690
mes jush dy djemtë.

561
00:22:11,690 --> 00:22:13,800
Pra, tani që është dy listat,
majtë dhe të djathtë.

562
00:22:13,800 --> 00:22:18,320
Deri sa nuk kemi tani bashkojë ju djema në
radhën e parë të ulëseve përsëri?

563
00:22:18,320 --> 00:22:19,600
>> 3 shkon e parë.

564
00:22:19,600 --> 00:22:20,850
5 Pastaj, natyrisht.

565
00:22:20,850 --> 00:22:23,110

566
00:22:23,110 --> 00:22:27,330
Pastaj 7, dhe tani 8.

567
00:22:27,330 --> 00:22:28,710
OK, dhe tani jemi ne?

568
00:22:28,710 --> 00:22:29,650
>> Audienca: Nuk është bërë.

569
00:22:29,650 --> 00:22:32,440
>> DAVID Malan: Nuk është bërë, për shkak se
Natyrisht, nuk është një hap i mbetur.

570
00:22:32,440 --> 00:22:35,720
Por përsëri, arsyeja që unë jam duke përdorur këtë
zhargon si "Rewind në mendjen tuaj,"

571
00:22:35,720 --> 00:22:37,160
kjo është për shkak se me të vërtetë
çfarë po ndodh.

572
00:22:37,160 --> 00:22:39,610
Ne jemi duke shkuar nëpër të gjitha këto hapa,
por ne jemi lloj i pushuar për një

573
00:22:39,610 --> 00:22:42,480
moment, thellë zhyten në
algorithm, heshti për një çast,

574
00:22:42,480 --> 00:22:45,840
zhyten më thellë në algorithm, dhe
tani ne kemi për të zgjidhur i Rewind në tonë

575
00:22:45,840 --> 00:22:49,430
Mendjet dhe të prish të gjitha këto shtresa
se ne kemi lloj të vihet në pritje.

576
00:22:49,430 --> 00:22:51,790
>> Pra, tani ne kemi dy listat e madhësisë 4.

577
00:22:51,790 --> 00:22:54,790
Nëse ju djema mund të ngriteni për herë të fundit
dhe të bëjë një grimë e hapësirë ​​këtu për

578
00:22:54,790 --> 00:22:57,230
bëjë të qartë se kjo është e majtë
gjysma e, origjinal

579
00:22:57,230 --> 00:22:58,620
gjysma e drejta e origjinalit.

580
00:22:58,620 --> 00:23:01,060
Kush është numri i parë që ne
duhet të tërheqë në anën e pasme?

581
00:23:01,060 --> 00:23:01,870
Michelle, natyrisht.

582
00:23:01,870 --> 00:23:03,230
>> Pra, ne kemi vënë Michelle këtu.

583
00:23:03,230 --> 00:23:05,080
Dhe kush e ka numrin 2?

584
00:23:05,080 --> 00:23:06,440
Numri 2 vjen mbrapa si.

585
00:23:06,440 --> 00:23:07,800
Numri 3?

586
00:23:07,800 --> 00:23:08,510
Excellent.

587
00:23:08,510 --> 00:23:16,570
Numri 4, Numri 5, numër 6,
Numri 7, dhe numri 8.

588
00:23:16,570 --> 00:23:18,850
>> OK, kështu që ai ndjehet si një shumë
i hapave, për sigurt.

589
00:23:18,850 --> 00:23:22,390
Por tani le të shohim nëse ne nuk mund të konfirmojmë
lloj i intuitivisht se ky

590
00:23:22,390 --> 00:23:26,190
algorithm rrënjësisht, veçanërisht si
n merr me të vërtetë e madhe, siç e kemi parë

591
00:23:26,190 --> 00:23:29,170
me animacione, është
rrënjësisht të shpejtë.

592
00:23:29,170 --> 00:23:33,400
Kështu që unë pretendojnë këtë algorithm, në më të keq
rast dhe madje edhe në rastin më të mirë,

593
00:23:33,400 --> 00:23:36,160
është i madh o N n herë log.

594
00:23:36,160 --> 00:23:39,160
Kjo është, ka disa aspekt i kësaj
algorithm që merr hapa n, por

595
00:23:39,160 --> 00:23:43,110
ekziston një aspekt tjetër diku në
se përsëritje, se looping, që

596
00:23:43,110 --> 00:23:44,410
merr hapa log n.

597
00:23:44,410 --> 00:23:49,154
Mund të kemi vënë gishtin tonë në atë që ata
dy numra janë duke iu referuar?

598
00:23:49,154 --> 00:23:51,320
Mirë, ku -

599
00:23:51,320 --> 00:23:54,160
Ku mic shkoni?

600
00:23:54,160 --> 00:23:58,660
>> Kryetari 1: A do të jetë hyni n
na thyer deri në dy -

601
00:23:58,660 --> 00:23:59,630
duke pjesetuar me dy, në thelb.

602
00:23:59,630 --> 00:24:00,120
>> DAVID Malan: Pikërisht.

603
00:24:00,120 --> 00:24:03,000
Çdo herë që ne shohim në çdo algorithm kështu
më tani, nuk ka qenë ky model i

604
00:24:03,000 --> 00:24:04,200
ndarëse, ndarëse, ndarëse.

605
00:24:04,200 --> 00:24:05,700
Dhe kjo është reduktuar në mënyrë tipike
për diçka që është

606
00:24:05,700 --> 00:24:07,100
logaritmike, log bazë 2.

607
00:24:07,100 --> 00:24:10,180
Por kjo mund të vërtetë të jetë çdo gjë,
por hyni bazë 2.

608
00:24:10,180 --> 00:24:11,330
>> Tani çfarë lidhje n?

609
00:24:11,330 --> 00:24:14,550
Unë mund të shihni se ne lloj i ndarë ju
djema - ju ndarë, të ndarë ju,

610
00:24:14,550 --> 00:24:15,910
ndarë ju, të ndarë me ju.

611
00:24:15,910 --> 00:24:18,760
Ku ka ardhur nga fundi?

612
00:24:18,760 --> 00:24:19,810
>> Pra, kjo është bashkimi.

613
00:24:19,810 --> 00:24:20,610
Sepse mendoni rreth saj.

614
00:24:20,610 --> 00:24:25,420
Kur ju të bashkojë tetë njerëz së bashku,
ku gjysma e tyre janë një grup prej katër

615
00:24:25,420 --> 00:24:27,770
dhe gjysma tjetër janë një tjetër
grup i katër, si mendoni ju të shkoni

616
00:24:27,770 --> 00:24:28,820
për të bërë bashkimin?

617
00:24:28,820 --> 00:24:30,830
E pra, ju djema e bëri atë
mjaft intuitive.

618
00:24:30,830 --> 00:24:34,140
>> Por, nëse unë e bëri atë një vend pak më shumë
metodike, unë mund të ketë vuri në

619
00:24:34,140 --> 00:24:38,090
Personi i pari nga e majta e parë me të majtë ime
dora, vuri në personin pari nga e majta

620
00:24:38,090 --> 00:24:42,080
gjysmën e asaj me të djathtën time, dhe të
vetëm më pas ecte nëpër

621
00:24:42,080 --> 00:24:46,990
listë, duke vënë në elementin më të vogël
çdo herë, duke lëvizur gishtin tim mbi dhe

622
00:24:46,990 --> 00:24:48,970
mbi si të nevojshme në të gjithë listës.

623
00:24:48,970 --> 00:24:51,890
Por ajo që është çelësi për këtë shkrirja
Procesi është Unë jam i krahasojmë këto çifte

624
00:24:51,890 --> 00:24:53,460
i elementeve.

625
00:24:53,460 --> 00:24:57,270
Nga gjysma e djathtë dhe nga e majta
gjysma, unë kurrë nuk jam dikur backtracking.

626
00:24:57,270 --> 00:25:00,570
>> Pra, shkrihen në vetvete është duke marrë
jo më shumë se n hapa.

627
00:25:00,570 --> 00:25:03,250
Dhe sa herë e bëri kam
për të bërë që shkrirja?

628
00:25:03,250 --> 00:25:07,150
E pra, jo më shumë se n, dhe ne vetëm
panë se me bashkimin përfundimtar.

629
00:25:07,150 --> 00:25:13,120
Dhe kështu që nëse ju bëni diçka që merr
hyni hapa N n herë, ose anasjelltas,

630
00:25:13,120 --> 00:25:15,210
ajo do të na japë hyni Ñ Ñ herë.

631
00:25:15,210 --> 00:25:16,310
>> Dhe pse është kjo më mirë?

632
00:25:16,310 --> 00:25:19,600
E pra, në qoftë se ne tashmë e dimë se log
n është më e mirë se n - e drejtë?

633
00:25:19,600 --> 00:25:22,590
Ne pamë në kërkim binar, librin e telefonit
shembull, log n ishte patjetër

634
00:25:22,590 --> 00:25:23,760
mirë se linear.

635
00:25:23,760 --> 00:25:28,420
Kështu që do të thotë herë n log n është
definitivisht më të mirë se sa herë një tjetër n

636
00:25:28,420 --> 00:25:30,390
n, AKA n katror.

637
00:25:30,390 --> 00:25:32,400
Dhe kjo është ajo që ne në fund të fundit të ndjehen.

638
00:25:32,400 --> 00:25:34,928
>> Raundi i madh i duartrokitje Pra, në qoftë se
ne mund të, për këto guys.

639
00:25:34,928 --> 00:25:38,920
>> [Duartrokitje]

640
00:25:38,920 --> 00:25:41,550
>> DAVID Malan: Dhe dhuratat tuaja ikje -
ju mund të mbani numrat,

641
00:25:41,550 --> 00:25:44,010
në qoftë se ju do të donte.

642
00:25:44,010 --> 00:25:45,620
Dhe dhurata juaj lamtumire, si zakonisht.

643
00:25:45,620 --> 00:25:47,290
Oh, dhe ne do të ju dërgojnë
Videoja, Michelle.

644
00:25:47,290 --> 00:25:48,343
Falemnderit.

645
00:25:48,343 --> 00:25:49,250
Dakord.

646
00:25:49,250 --> 00:25:50,400
Ndihmë veten me një top stresit.

647
00:25:50,400 --> 00:25:54,110
>> Dhe më lejoni të tërheq lart, në ndërkohë,
pershendetje Rob Bowden tonë për të ofruar

648
00:25:54,110 --> 00:25:59,520
Perspektiva disi ndryshe në këtë,
që ju mund të mendoni në lidhje me këto

649
00:25:59,520 --> 00:26:01,280
hapa të ndodhin në një disi
mënyrë të ndryshme.

650
00:26:01,280 --> 00:26:04,750
Në fakt, set-up për atë që është në lidhje me Rob
për të na treguar supozon se ne kemi

651
00:26:04,750 --> 00:26:09,030
bërë tashmë deri ndarjen e
lista e madhe në tetë listave të vogla,

652
00:26:09,030 --> 00:26:10,570
secili prej Siperfaqja 1.

653
00:26:10,570 --> 00:26:13,350
>> Pra, ne jemi duke ndryshuar një pseudokod
pak vetëm për të zgjidhur të marrë në

654
00:26:13,350 --> 00:26:15,320
Ideja kryesore e se si shkrirja veprat.

655
00:26:15,320 --> 00:26:17,600
Por koha drejtimin e asaj
ai është gati për të bërë është ende

656
00:26:17,600 --> 00:26:19,110
do të jetë e njëjtë.

657
00:26:19,110 --> 00:26:23,540
Dhe përsëri, set-up këtu është se ai është
filluar me tetë listat e madhësisë 1.

658
00:26:23,540 --> 00:26:27,730
Pra, ju keni humbur pjesën ku ai është
bërë në fakt, log n log n log n,

659
00:26:27,730 --> 00:26:31,205
ndarja e dhëna.

660
00:26:31,205 --> 00:26:32,120
>> [Video playback]

661
00:26:32,120 --> 00:26:33,615
>> -Kjo është ajo për një hap.

662
00:26:33,615 --> 00:26:38,270
Për hap dy në mënyrë të përsëritur
bashkojë palë e listave.

663
00:26:38,270 --> 00:26:39,210
>> DAVID Malan: Hm.

664
00:26:39,210 --> 00:26:41,270
Audio Vetëm po vjen
jashtë kompjuterin tim.

665
00:26:41,270 --> 00:26:42,520
Le të provoni këtë përsëri.

666
00:26:42,520 --> 00:26:45,330

667
00:26:45,330 --> 00:26:48,310
>> -Vetëm të marr në mënyrë arbitrare e cila -
tani ne kemi katër listat.

668
00:26:48,310 --> 00:26:51,590

669
00:26:51,590 --> 00:26:52,120
Mësoni më parë.

670
00:26:52,120 --> 00:26:53,040
>> DAVID Malan: Nuk shkojmë.

671
00:26:53,040 --> 00:27:00,510
>> Bashkimi-108 dhe 15, ne fund
deri me lista 15, 108.

672
00:27:00,510 --> 00:27:07,170
Bashkimi 50 dhe 4, ne
përfundojnë me 4, 50.

673
00:27:07,170 --> 00:27:12,990
Bashkimi 8 dhe 42, ne
të përfundojë me 8, 42.

674
00:27:12,990 --> 00:27:19,970
Dhe bashkimi 23 dhe 16, ne
të përfundojë me 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Tani të gjitha listat tona janë të madhësisë 2.

676
00:27:23,270 --> 00:27:26,690
Njoftim që secili prej
katër listat e renditura.

677
00:27:26,690 --> 00:27:29,450
Pra, ne mund të fillojë shkrirja
palë e listave përsëri.

678
00:27:29,450 --> 00:27:38,420
Bashkimi 15 dhe 108 dhe 4 dhe 50, ne
së pari të marrë 4, pastaj 15, pastaj

679
00:27:38,420 --> 00:27:41,500
50, pastaj 108.

680
00:27:41,500 --> 00:27:50,610
Bashkimi 8, 42 dhe 16, 23, ne së pari të marrë
8, pastaj 16, pastaj 23,

681
00:27:50,610 --> 00:27:52,700
pastaj 42.

682
00:27:52,700 --> 00:27:57,600
>> Pra, tani ne kemi vetëm dy listat e madhësisë
4, secila prej të cilave është zgjidhet.

683
00:27:57,600 --> 00:28:01,170
Deri tani ne bashkojë këto dy lista.

684
00:28:01,170 --> 00:28:11,835
Së pari, ne kemi marrë 4, atëherë ne marrim
8, atëherë ne do të marrim 15, pastaj 16, pastaj

685
00:28:11,835 --> 00:28:19,456
23, pastaj 42, pastaj 50, pastaj 108.

686
00:28:19,456 --> 00:28:19,872
>> [VIDEO END rishikim]

687
00:28:19,872 --> 00:28:23,430
>> DAVID Malan: Përsëri, njoftim, ai kurrë nuk
preku një filxhan i dhënë më shumë se një herë

688
00:28:23,430 --> 00:28:24,860
pas avancimin e përtej tij.

689
00:28:24,860 --> 00:28:26,200
Kështu që ai kurrë nuk e përsëritur.

690
00:28:26,200 --> 00:28:29,850
Pra, ai është gjithmonë duke lëvizur në krah,
dhe kjo është ajo ku kemi marrë n tonë.

691
00:28:29,850 --> 00:28:33,290
>> Pse nuk lejoni të tërheq lart një animacion
që pamë më herët, por këtë herë

692
00:28:33,290 --> 00:28:35,110
duke u përqendruar vetëm në lloj bashkohen.

693
00:28:35,110 --> 00:28:38,030
Më lejoni të shkojnë përpara dhe zoom
në për këtë këtu.

694
00:28:38,030 --> 00:28:42,530
Së pari më lejoni të zgjedhin një input të rastit,
lartësoj këtë, dhe ju mund të lloj të shihni

695
00:28:42,530 --> 00:28:46,600
ajo që ne e mori për të dhënë, më herët,
bashkojë lloj është në të vërtetë duke bërë.

696
00:28:46,600 --> 00:28:50,330
>> Pra, vëreni që ju të merrni këto gjysmave apo
këto të katërtat ose këto eighths e

697
00:28:50,330 --> 00:28:53,140
Problemi se të gjitha një e papritur
të fillojë të marrë formë të mirë.

698
00:28:53,140 --> 00:28:57,070
Dhe pastaj në fund, që ju shihni në
Fundi shumë se bam,

699
00:28:57,070 --> 00:28:58,860
çdo gjë është shkrirë së bashku.

700
00:28:58,860 --> 00:29:01,690
>> Pra, këto janë vetëm tre të ndryshme
merr në të njëjtën ide.

701
00:29:01,690 --> 00:29:05,980
Por depërtim kyç, ashtu si divide
pushtuar dhe në klasë të parë,

702
00:29:05,980 --> 00:29:10,640
ishte se ne kemi vendosur që të ndajë disi
Problemi në diçka të madhe, në

703
00:29:10,640 --> 00:29:14,760
lloj diçka e njëjtë në frymë,
por më të vogla dhe të vogla dhe të vogla

704
00:29:14,760 --> 00:29:15,660
dhe të vogla.

705
00:29:15,660 --> 00:29:18,420
>> Tani një tjetër rrugë zbavitëse për lloj të mendojnë
në lidhje me këto, edhe pse kjo nuk është

706
00:29:18,420 --> 00:29:20,520
do të ju jap intuitiv njëjtë
të kuptuarit, është

707
00:29:20,520 --> 00:29:21,640
animacion vijim.

708
00:29:21,640 --> 00:29:25,400
Pra, kjo është një dikush video të vënë së bashku
që shoqërohet ndryshme

709
00:29:25,400 --> 00:29:29,970
Dashuri me operacione të ndryshme për
lloj futje, për lloj shkrihen, dhe

710
00:29:29,970 --> 00:29:31,150
për një çift të tjerëve.

711
00:29:31,150 --> 00:29:32,330
Pra, në një moment, unë jam duke shkuar për të goditur Luaj.

712
00:29:32,330 --> 00:29:33,600
Kjo është rreth një minutë të gjata.

713
00:29:33,600 --> 00:29:37,410
Dhe, edhe pse ju mund të shohin ende
modelet ndodh, këtë herë ju mund të

714
00:29:37,410 --> 00:29:41,420
gjithashtu dëgjuar se si këto algoritme janë
kryerjen ndryshe dhe me

715
00:29:41,420 --> 00:29:43,950
modelet disi të ndryshme.

716
00:29:43,950 --> 00:29:45,830
>> Kjo është lloj futje.

717
00:29:45,830 --> 00:29:50,400
>> [Tones PLAYING]

718
00:29:50,400 --> 00:29:52,400
>> DAVID Malan: Kjo përsëri është duke u përpjekur
për të futur çdo element

719
00:29:52,400 --> 00:29:52,900
në aty ku i takon.

720
00:29:52,900 --> 00:29:54,628
Kjo është lloj flluskë.

721
00:29:54,628 --> 00:30:10,097
>> [Tones PLAYING]

722
00:30:10,097 --> 00:30:13,630
>> DAVID Malan: Dhe ju mund të lloj të ndjehen
si relativisht pak punë është e bërë

723
00:30:13,630 --> 00:30:15,834
në çdo hap.

724
00:30:15,834 --> 00:30:20,470
Kjo është ajo që tingëllon si tediousness.

725
00:30:20,470 --> 00:30:21,472
>> [Tones PLAYING]

726
00:30:21,472 --> 00:30:25,222
>> DAVID Malan: Kjo është lloj përzgjedhje,
ku ne selekto element ne duam nga

727
00:30:25,222 --> 00:30:28,845
duke shkuar nëpër përsëri dhe përsëri dhe përsëri
dhe duke i vënë atë në fillim.

728
00:30:28,845 --> 00:30:37,674
>> [Tones PLAYING]

729
00:30:37,674 --> 00:30:43,970
>> DAVID Malan: Kjo është lloj bashkojë, të cilat
ju mund të vërtetë të fillojë të ndjehen.

730
00:30:43,970 --> 00:30:51,810
>> [Tones PLAYING]

731
00:30:51,810 --> 00:30:54,770
>> [Qeshura]

732
00:30:54,770 --> 00:30:58,395
>> DAVID Malan: Diçka e quajtur gnome
lloj, të cilën ne nuk e kemi shikuar.

733
00:30:58,395 --> 00:31:13,630
>> [Tones PLAYING]

734
00:31:13,630 --> 00:31:17,910
>> DAVID Malan: Pra më lejoni të shohim, tani,
hutuar si ju janë shpresë nga

735
00:31:17,910 --> 00:31:21,110
music, në qoftë se unë mund të kaloj pak
bit e math në këtu.

736
00:31:21,110 --> 00:31:24,850
Pra, nuk është një mënyrë e katërt që ne mund
mendoni se çfarë do të thotë këto

737
00:31:24,850 --> 00:31:29,210
Funksione të jetë më shpejt se ato të
që ne kemi parë më parë.

738
00:31:29,210 --> 00:31:32,470
Dhe në qoftë se ju jeni të vijnë në kurs nga
një sfond matematikë, ju

739
00:31:32,470 --> 00:31:36,030
në fakt ndoshta tashmë e dini që ju
mund të godasin një mandat në këtë teknikë -

740
00:31:36,030 --> 00:31:40,400
domethënë recursion, një funksion
që në njëfarë mënyre e quan veten.

741
00:31:40,400 --> 00:31:44,780
>> Dhe përsëri, kujtojnë atë lloj bashkojë
pseudokod ishte recursive në kuptimin

742
00:31:44,780 --> 00:31:48,460
se një nga hapat e Rendit Merge
ishte për të thirrur lloj -

743
00:31:48,460 --> 00:31:49,740
që është, në vetvete.

744
00:31:49,740 --> 00:31:52,480
Por fatmirësisht, sepse ne kemi mbajtur
lloj thirrje, ose të bashkohen lloj,

745
00:31:52,480 --> 00:31:55,880
konkretisht, në një të vogla dhe të vogla
dhe lista të vogla, ne përfundimisht

746
00:31:55,880 --> 00:32:00,005
në sajë ndal në atë që ne do të thërrasë
një rast bazë, hard-coded rasti që

747
00:32:00,005 --> 00:32:04,270
tha se nëse lista është e vogël, më pak se 2
në atë rast, vetëm të kthehet menjëherë.

748
00:32:04,270 --> 00:32:07,550
Nëse ne nuk kemi atë rast të veçantë,
algorithm kurrë nuk do të poshtme jashtë,

749
00:32:07,550 --> 00:32:11,010
dhe ju do të vërtetë të marrë në një
loop pafund të vërtetë përgjithmonë.

750
00:32:11,010 --> 00:32:14,330
>> Por mendoj se ne të kërkuar për të vënë tani
disa numra në këtë, përsëri, duke përdorur n

751
00:32:14,330 --> 00:32:15,660
si me përmasat e dhëna.

752
00:32:15,660 --> 00:32:18,680
Dhe unë të kërkuar për të ju pyes, çfarë është
Koha totale e përfshirë në

753
00:32:18,680 --> 00:32:19,800
running lloj shkrihet?

754
00:32:19,800 --> 00:32:22,960
Ose më në përgjithësi, çfarë është
Kostoja e saj në kohë?

755
00:32:22,960 --> 00:32:24,730
>> E pra kjo është goxha e lehtë për të matur atë.

756
00:32:24,730 --> 00:32:29,010
Nëse n është më pak se 2, koha të përfshirë
në klasifikim n elemente,

757
00:32:29,010 --> 00:32:30,480
ku n eshte 2, eshte 0.

758
00:32:30,480 --> 00:32:31,410
Sepse ne vetëm të kthehen.

759
00:32:31,410 --> 00:32:32,510
Nuk ka punë për t'u bërë.

760
00:32:32,510 --> 00:32:35,660
Tani ndoshta, ndoshta kjo është një hap ose dy
Hapa të gjej shumën e

761
00:32:35,660 --> 00:32:38,420
të punojnë, por është mjaft afër se 0
Unë jam vetëm duke shkuar për të thonë se nuk ka punë

762
00:32:38,420 --> 00:32:40,940
nevojshme nëse lista është aq i vogël
për t'u jointeresant.

763
00:32:40,940 --> 00:32:42,580
>> Por, ky rast është interesant.

764
00:32:42,580 --> 00:32:47,320
Rasti recursive ishte dega e
pseudokod që tha tjetër, lloj

765
00:32:47,320 --> 00:32:52,000
gjysma e majtë, lloj drejtën
gjysma, shkrihen dy gjysmave.

766
00:32:52,000 --> 00:32:55,530
Tani pse e bën këtë shprehje
përfaqësojnë atë shpenzim?

767
00:32:55,530 --> 00:32:58,690
E pra, n T i vetëm do të thotë
Koha për të zgjidhur elementet n.

768
00:32:58,690 --> 00:33:03,070
Dhe pastaj në anën e djathtë të
barabartë shenjë atje, n T i ndarë

769
00:33:03,070 --> 00:33:06,600
nga 2 është duke iu referuar kostos së çfarë?

770
00:33:06,600 --> 00:33:07,570
Sorting gjysmën e majtë.

771
00:33:07,570 --> 00:33:10,990
T e tjera të n ndarë nga 2 është
me sa duket duke iu referuar kostos për

772
00:33:10,990 --> 00:33:12,390
lloj gjysmën e duhur.

773
00:33:12,390 --> 00:33:14,590
>> Dhe pastaj plus n?

774
00:33:14,590 --> 00:33:15,420
Është bashkimi.

775
00:33:15,420 --> 00:33:19,120
Sepse në qoftë se ju keni dy lista, një nga
n madhësia mbi 2 dhe një tjetër i madhësisë n

776
00:33:19,120 --> 00:33:22,580
mbi 2, ju duhet të në thelb prek
secili prej këtyre elementeve, ashtu si Rob

777
00:33:22,580 --> 00:33:24,990
preku secilin nga gota, dhe vetëm
si ne theksuar në secilin prej

778
00:33:24,990 --> 00:33:26,310
Vullnetarët në skenë.

779
00:33:26,310 --> 00:33:28,790
Kështu n eshte shpenzimeve të bashkimit.

780
00:33:28,790 --> 00:33:31,780
>> Tani për fat të keq, kjo formulë
është edhe vetë rekursive.

781
00:33:31,780 --> 00:33:36,390
Pra, nëse pyetjen, nëse n është, të themi,
16, në qoftë se ka 16 njerëz në skenë

782
00:33:36,390 --> 00:33:40,670
ose 16 gota në video, sa përgjithshëm
hapa nuk është marrë për të zgjidhur ato

783
00:33:40,670 --> 00:33:41,550
me lloj bashkojë?

784
00:33:41,550 --> 00:33:45,790
Kjo nuk është në fakt një përgjigje e qartë,
sepse tani ju keni për të zgjidhur të

785
00:33:45,790 --> 00:33:48,500
Recursively të përgjigjem në këtë formulë.

786
00:33:48,500 --> 00:33:51,190
>> Por kjo është në rregull, sepse më lejoni të propozojnë
që ne bëjmë në vijim.

787
00:33:51,190 --> 00:33:56,670
Ora përfshira për të zgjidhur 16 persona ose
16 gota do të jenë të përfaqësuara

788
00:33:56,670 --> 00:33:58,020
përgjithësisht si T i 16.

789
00:33:58,020 --> 00:34:01,400
Por që është e barabartë, sipas tonë
Formula e mëparshme, 2 herë shumën

790
00:34:01,400 --> 00:34:04,780
e kohës që duhet për të zgjidhur
8 gota plus 16.

791
00:34:04,780 --> 00:34:08,590
Dhe përsëri, plus 16 është koha që të bashkojë,
dhe dy herë T e 8 eshte

792
00:34:08,590 --> 00:34:10,790
Koha për të zgjidhur gjysmën e majtë dhe gjysmë të drejtë.

793
00:34:10,790 --> 00:34:11,989
>> Por përsëri, kjo nuk është e mjaftueshme.

794
00:34:11,989 --> 00:34:13,210
Ne kemi të zhyten në të thellë.

795
00:34:13,210 --> 00:34:16,409
Kjo do të thotë që ne duhet të përgjigjen
pyetja, çfarë është T e 8?

796
00:34:16,409 --> 00:34:19,610
Well T i 8 është vetëm 2
T herë nga 4 plus 8.

797
00:34:19,610 --> 00:34:20,520
E pra, ajo që është e T 4?

798
00:34:20,520 --> 00:34:23,780
T i 4 është vetëm 2 herë T e 2 plus 4.

799
00:34:23,780 --> 00:34:25,489
E pra, ajo që është e T 2?

800
00:34:25,489 --> 00:34:29,030
T e 2 është vetëm 2 herë T e 1 plus 2.

801
00:34:29,030 --> 00:34:31,940
>> Dhe përsëri, ne jemi lloj i gjetjes
mbërthyer në këtë cikël.

802
00:34:31,940 --> 00:34:34,790
Por kjo është gati për të goditur se
ashtuquajturit rasti bazë.

803
00:34:34,790 --> 00:34:37,310
Sepse çfarë është e T 1, nuk kemi pretendojnë?

804
00:34:37,310 --> 00:34:37,810
0.

805
00:34:37,810 --> 00:34:39,730
Deri tani në fund, ne mund të punojnë prapa.

806
00:34:39,730 --> 00:34:44,290
>> Nëse T e 1 është 0, unë tani mund të shkojë mbrapa deri një
përputhje me këtë djalë këtu, dhe unë mund të

807
00:34:44,290 --> 00:34:46,330
plug në për T 0 e 1.

808
00:34:46,330 --> 00:34:51,770
Pra, do të thotë se ajo është e barabartë me 2 herë zero,
i njohur ndryshe si 0, plus 2.

809
00:34:51,770 --> 00:34:53,739
Dhe kështu që shprehja e tërë është 2.

810
00:34:53,739 --> 00:34:58,740
>> Tani, nëse unë të marrë T e 2, të cilit përgjigje
është 2, plug it në vijën e mesme, T

811
00:34:58,740 --> 00:35:02,740
e 4, që i jep më 2 herë
2 plus 4, kështu 8.

812
00:35:02,740 --> 00:35:07,080
Nëse unë pastaj plug në 8 për paraardhëse
line, që më jep 2 herë në 8, 16.

813
00:35:07,080 --> 00:35:12,470
Dhe në qoftë se ne vazhdojmë pastaj se me
24, duke shtuar në 16, ne fund merrni një

814
00:35:12,470 --> 00:35:13,820
Vlera e 64.

815
00:35:13,820 --> 00:35:18,480
>> Tani që në vetvete lloj i flet
gjë që e simbol n,

816
00:35:18,480 --> 00:35:20,700
O i madh, omega që ne kemi
qenë duke folur rreth.

817
00:35:20,700 --> 00:35:24,890
Por kjo rezulton se 64 është me të vërtetë
16, madhësia e input,

818
00:35:24,890 --> 00:35:27,110
hyni bazë 2 prej 16.

819
00:35:27,110 --> 00:35:30,200
Dhe në qoftë se kjo është një pak të panjohura, vetëm
mendoj se mbrapa, dhe ajo do të kthehet

820
00:35:30,200 --> 00:35:30,700
për ju përfundimisht.

821
00:35:30,700 --> 00:35:33,775
Nëse kjo është bazë log 2, kjo është si 2
ngritur në ajo që ju jep 16?

822
00:35:33,775 --> 00:35:36,380
Oh, kjo është 4, kështu që është 16 herë 4.

823
00:35:36,380 --> 00:35:39,380
>> Dhe përsëri, kjo nuk është një punë e madhe nëse kjo
është lloj i një kujtim i mjegullt tani.

824
00:35:39,380 --> 00:35:43,720
Por tani për tani, të marrë besimin
se 16 log 16 është 64.

825
00:35:43,720 --> 00:35:46,590
Dhe kështu me të vërtetë, me këtë mendje e shëndoshë të thjeshtë
kontrolloni, ne kemi konfirmuar -

826
00:35:46,590 --> 00:35:48,250
por nuk provohet zyrtarisht -

827
00:35:48,250 --> 00:35:52,800
se koha drejtimin e bashkimin
Rendit është me të vërtetë n log n.

828
00:35:52,800 --> 00:35:53,790
>> Pra, jo i keq.

829
00:35:53,790 --> 00:35:57,260
Është patjetër më mirë se
Algoritmet e kemi parë deri tani, dhe

830
00:35:57,260 --> 00:36:00,710
kjo është për shkak se ne kemi leveraged, një,
një teknikë të quajtur recursion.

831
00:36:00,710 --> 00:36:03,880
Por më interesant se kaq, se
nocioni i ndarjes dhe pushtues.

832
00:36:03,880 --> 00:36:07,460
Përsëri, në të vërtetë javën 0 sende që
edhe tani është përsëritur në një

833
00:36:07,460 --> 00:36:08,740
mënyrë më bindëse.

834
00:36:08,740 --> 00:36:11,750
>> Tani një ushtrim fun pak, në qoftë se ju keni
bërë kurrë këtë - dhe ju ndoshta

835
00:36:11,750 --> 00:36:14,660
nuk do të ketë, sepse lloj normale
njerëzit nuk mendojnë për të bërë këtë.

836
00:36:14,660 --> 00:36:20,650
Por në qoftë se unë po shkoj tek google.com dhe nëse
Unë dua të mësojnë diçka rreth

837
00:36:20,650 --> 00:36:22,356
recursion, Enter.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [Qeshura]

840
00:36:29,058 --> 00:36:32,030
[Qeshura MORE]

841
00:36:32,030 --> 00:36:33,385
DAVID Malan: shaka e keqe përhapur ngadalë.

842
00:36:33,385 --> 00:36:34,450
[Qeshura]

843
00:36:34,450 --> 00:36:36,970
DAVID Malan: Vetëm në rast, ajo është aty.

844
00:36:36,970 --> 00:36:38,710
Unë nuk shkruhet gabim,
dhe nuk ka shaka.

845
00:36:38,710 --> 00:36:40,810
Dakord.

846
00:36:40,810 --> 00:36:42,950
Shpjegojnë atë njerëzve ardhshme për ju nëse
ajo nuk ka klikuar mjaft vetëm ende.

847
00:36:42,950 --> 00:36:47,650
Por recursion, më në përgjithësi, i referohet
në procesin e një funksioni të quajtur

848
00:36:47,650 --> 00:36:51,430
vetë, ose më në përgjithësi, duke e ndarë një
Problemi në diçka që mund të jetë

849
00:36:51,430 --> 00:36:56,220
zgjidhen pak nga pak duke zgjidhur identike
Problemet përfaqësuese.

850
00:36:56,220 --> 00:36:58,400
>> Ingranazhet pra, le të ndryshim
për vetëm një moment.

851
00:36:58,400 --> 00:37:00,840
Ne të doja të përfundojë më cliffhangers të caktuara,
kështu që le të fillojë për të vendosur

852
00:37:00,840 --> 00:37:05,870
fazë, për disa minuta,
në një ide shumë të thjeshtë -

853
00:37:05,870 --> 00:37:07,620
që i shkëmbejnë dy elemente, e drejtë?

854
00:37:07,620 --> 00:37:10,040
Të gjitha këto algoritme ne kemi qenë
duke folur rreth dy viteve të

855
00:37:10,040 --> 00:37:12,420
ligjërata të përfshijë disa
lloj i shkëmbejnë.

856
00:37:12,420 --> 00:37:14,630
Sot ajo është visualized nga ata duke
dorë nga karriget e tyre dhe

857
00:37:14,630 --> 00:37:18,570
ecin përreth, por në kod, ne do të
marrë vetëm një element nga një grup

858
00:37:18,570 --> 00:37:20,370
dhe pllum atë në një tjetër.

859
00:37:20,370 --> 00:37:21,880
>> Pra, si do të shkojmë për të bërë këtë?

860
00:37:21,880 --> 00:37:24,850
E pra, më lejoni të shkoj përpara dhe të shkruajnë
një program të shpejtë këtu.

861
00:37:24,850 --> 00:37:31,600
Unë jam duke shkuar për të shkuar përpara dhe të bëjë
kjo si në vijim.

862
00:37:31,600 --> 00:37:33,910
Le ta quajmë këtë -

863
00:37:33,910 --> 00:37:38,070
çfarë ne duam ta quajmë këtë një të tillë?

864
00:37:38,070 --> 00:37:38,650
>> Në fakt, nuk ka.

865
00:37:38,650 --> 00:37:39,420
Më lejoni të Rewind.

866
00:37:39,420 --> 00:37:41,220
Unë nuk dua të bëj që
cliffhanger ende.

867
00:37:41,220 --> 00:37:42,270
Ajo do të prishin fun.

868
00:37:42,270 --> 00:37:43,600
Le ta bëjmë këtë vend.

869
00:37:43,600 --> 00:37:47,430
>> Le të supozojmë se unë dua të shkruaj pak
Programi dhe se tani përqafon këtë

870
00:37:47,430 --> 00:37:48,700
Ideja e recursion.

871
00:37:48,700 --> 00:37:50,370
Unë lloj i marrë përpara veten time atje.

872
00:37:50,370 --> 00:37:51,420
Unë jam duke shkuar për të bërë në vijim.

873
00:37:51,420 --> 00:38:00,220
>> Së pari, të përfshijë një të shpejtë të standardit io.h,
si edhe një përfshijnë të cs50.h.

874
00:38:00,220 --> 00:38:03,200
Dhe atëherë unë jam duke shkuar për të shkuar përpara
dhe e shpall të pavlefshme kryesore int

875
00:38:03,200 --> 00:38:04,360
në mënyrë të zakonshme.

876
00:38:04,360 --> 00:38:07,920
Kuptova unë kam sot quhet dosjen, kështu që
më lejoni të vetëm të shtoni një zgjatje. c këtu në mënyrë

877
00:38:07,920 --> 00:38:09,510
që ne mund të përpilojnë atë siç duhet.

878
00:38:09,510 --> 00:38:10,970
Filloni këtë funksion off.

879
00:38:10,970 --> 00:38:13,290
>> Dhe funksioni unë dua të shkruaj, mjaft
thjesht, eshte njeri qe kerkon

880
00:38:13,290 --> 00:38:16,210
shfrytëzues për një numër dhe pastaj shton deri
të gjitha numrat që mes

881
00:38:16,210 --> 00:38:19,920
Numri dhe, të themi, 0.

882
00:38:19,920 --> 00:38:22,510
Pra, së pari unë jam duke shkuar për të shkuar përpara
dhe të deklarojë n int.

883
00:38:22,510 --> 00:38:24,760
Pastaj unë kopjoni kodin që disa
ne kemi përdorur për një kohë.

884
00:38:24,760 --> 00:38:26,660
Ndërsa diçka është e vërtetë.

885
00:38:26,660 --> 00:38:28,000
Unë do të kthehem në se në një moment.

886
00:38:28,000 --> 00:38:29,010
>> Çfarë doni të bëni?

887
00:38:29,010 --> 00:38:33,460
Unë dua të them printf pozitive
integer ju lutem.

888
00:38:33,460 --> 00:38:36,130
Dhe atëherë unë jam duke shkuar për të
thonë n merr merrni int.

889
00:38:36,130 --> 00:38:38,800
Pra, përsëri, disa kodin Boilerplate
që ne kemi përdorur më parë.

890
00:38:38,800 --> 00:38:40,810
Dhe unë jam duke shkuar për të bërë këtë
ndërsa n është më pak se 1.

891
00:38:40,810 --> 00:38:44,120
Pra, kjo do të sigurojë që përdoruesi
më jep një numër i plotë pozitiv.

892
00:38:44,120 --> 00:38:45,490
>> Dhe tani unë jam duke shkuar për të bërë në vijim.

893
00:38:45,490 --> 00:38:51,020
Unë dua të shtoni deri të gjithë numrat e
midis 1 dhe dhe n, ose 0 dhe n,

894
00:38:51,020 --> 00:38:52,570
ekuivalente, për të marrë shumën totale.

895
00:38:52,570 --> 00:38:55,100
Pra, simbol i madh sigma
që ju mund të kujtojnë.

896
00:38:55,100 --> 00:38:59,050
Kështu që unë jam duke shkuar për të bërë këtë duke thirrur parë
një funksion të quajtur sigma,

897
00:38:59,050 --> 00:39:06,030
duke kaluar atë në n, dhe pastaj unë jam duke shkuar për
printf thonë, përgjigja është e drejtë atje.

898
00:39:06,030 --> 00:39:08,180
>> Pra me pak fjalë, unë të marrë dhe
int nga përdoruesi.

899
00:39:08,180 --> 00:39:09,280
I siguruar se ajo është pozitive.

900
00:39:09,280 --> 00:39:12,700
Unë deklaroj një përgjigje të ndryshueshme të quajtur
int lloji dhe dyqan në atë kthim

901
00:39:12,700 --> 00:39:15,610
Vlera e Sigma-n, duke kaluar n si input.

902
00:39:15,610 --> 00:39:17,060
Dhe pastaj unë të shtypura nga se përgjigje.

903
00:39:17,060 --> 00:39:19,550
>> Për fat të keq, edhe pse tingëllon sigma
si diçka që mund të jetë në

904
00:39:19,550 --> 00:39:24,040
fotografi math.h, deklaratën e saj,
kjo nuk është e vërtetë.

905
00:39:24,040 --> 00:39:24,690
Pra, kjo është OK.

906
00:39:24,690 --> 00:39:26,170
Unë mund të zbatojë këtë veten.

907
00:39:26,170 --> 00:39:29,160
Unë jam duke shkuar për të zbatuar një funksion të quajtur
SIGMA, dhe ajo do të marrë një

908
00:39:29,160 --> 00:39:29,900
parametri -

909
00:39:29,900 --> 00:39:32,100
le të vetëm e quajti atë m, vetëm
kështu që është e ndryshme.

910
00:39:32,100 --> 00:39:35,910
Dhe pastaj deri këtu, unë jam duke shkuar për të thënë,
dhe, nëse M është më pak se 1 - ky eshte nje

911
00:39:35,910 --> 00:39:38,180
shumë jointeresant programin.

912
00:39:38,180 --> 00:39:41,700
Kështu që unë jam duke shkuar për të shkuar përpara dhe
kthehen menjëherë 0.

913
00:39:41,700 --> 00:39:45,920
Ajo thjesht nuk ka kuptim që të shtoni deri gjitha
numrat midis 1 dhe m nëse këtë m

914
00:39:45,920 --> 00:39:48,470
në vetvete është 0 ose negative.

915
00:39:48,470 --> 00:39:50,900
>> Dhe atëherë unë jam duke shkuar për të shkuar përpara
dhe të bëjë këtë shumë iteratively.

916
00:39:50,900 --> 00:39:53,090
Unë jam duke shkuar për të bërë këtë lloj të vjetër-shkollën,
dhe unë jam duke shkuar për të shkuar përpara

917
00:39:53,090 --> 00:39:57,150
dhe të them se unë jam duke shkuar për të
deklarojë një shumë të jetë 0.

918
00:39:57,150 --> 00:39:59,630
Pastaj unë jam do të ketë
një për lak e int -

919
00:39:59,630 --> 00:40:02,820
dhe më lejoni të bëjë atë për ndeshjen tonë
Kodi shpërndarjes, kështu që ju keni një kopje

920
00:40:02,820 --> 00:40:07,500
në shtëpi. int I merr 1 on deri tek
Unë është më pak se ose e barabartë me m.

921
00:40:07,500 --> 00:40:09,430
Unë plus plus.

922
00:40:09,430 --> 00:40:11,430
Dhe pastaj brenda kësaj për lak -

923
00:40:11,430 --> 00:40:12,440
ne jemi pothuajse atje -

924
00:40:12,440 --> 00:40:15,810
Shuma merr shumën plus 1.

925
00:40:15,810 --> 00:40:17,670
Dhe atëherë unë jam duke shkuar për të kthyer shumën.

926
00:40:17,670 --> 00:40:19,420
>> Kështu që unë e bëri këtë shpejt,
mjaft dyshim.

927
00:40:19,420 --> 00:40:22,775
Por përsëri, funksioni kryesor është goxha
drejtpërdrejtë, në bazë të kodit që kemi

928
00:40:22,775 --> 00:40:23,190
shkruar deri tani.

929
00:40:23,190 --> 00:40:25,610
Përdor lak të dyfishtë për të marrë një pozitiv
int nga përdoruesi.

930
00:40:25,610 --> 00:40:29,870
Unë pastaj të kalojë atë int për një funksion të ri
quhet sigma, duke e quajtur atë, përsëri, n.

931
00:40:29,870 --> 00:40:33,100
Dhe unë të ruajë vlerën e kthimit, përgjigje
nga kutia e zezë aktualisht

932
00:40:33,100 --> 00:40:35,460
njohur si Sigma-n, në një variabël
quajtur përgjigje.

933
00:40:35,460 --> 00:40:36,580
Pastaj unë të shtypura atë.

934
00:40:36,580 --> 00:40:39,090
>> Nëse ne tani vazhdojmë tregimin,
si është zbatuar sigma?

935
00:40:39,090 --> 00:40:40,840
Unë propozoj për të zbatuar si më poshtë.

936
00:40:40,840 --> 00:40:43,560
Së pari, pak e gabimit-checking
për të siguruar që përdoruesi nuk është

937
00:40:43,560 --> 00:40:46,480
messing me mua dhe kalimin në
disa vlera negative ose 0.

938
00:40:46,480 --> 00:40:49,710
Pastaj unë të deklarojë një ndryshore të quajtur
përmbledhur dhe e vendosi atë në 0.

939
00:40:49,710 --> 00:40:55,910
>> Dhe tani kam filluar të lëvizin nga i barabartë
1 të gjitha rrugën deri në dhe duke përfshirë m,

940
00:40:55,910 --> 00:41:00,130
sepse unë dua që të përfshijë të gjithë
numrat nga njëra anë m, përfshirëse.

941
00:41:00,130 --> 00:41:04,350
Dhe brenda kësaj për lak, unë vetëm bëj
Shuma merr çfarëdo qoftë ajo është tani, plus

942
00:41:04,350 --> 00:41:08,900
Vlera e i.

943
00:41:08,900 --> 00:41:10,370
Plus vlera e i.

944
00:41:10,370 --> 00:41:14,090
>> Si një mënjanë, në qoftë se ju nuk e keni parë këtë
më parë, ka disa sheqeri sintaktik

945
00:41:14,090 --> 00:41:14,870
për këtë linjë.

946
00:41:14,870 --> 00:41:21,120
Unë mund të ndryshonin këtë si plus i barabartë,
vetëm për të shpëtuar veten disa tasteve

947
00:41:21,120 --> 00:41:22,570
dhe për të kërkuar një pije freskuese pak.

948
00:41:22,570 --> 00:41:23,140
Por kjo është e gjitha.

949
00:41:23,140 --> 00:41:24,660
Kjo është funksionalisht e njëjta gjë.

950
00:41:24,660 --> 00:41:26,710
>> Për fat të keq, ky kod të
nuk shkojnë për të hartuar ende.

951
00:41:26,710 --> 00:41:31,600
Nëse unë drejtuar bëjë SIGMA 0, Sa jam
Unë do të merrni yelled at?

952
00:41:31,600 --> 00:41:33,473
Çfarë është ajo për të shkuar nuk i pëlqen?

953
00:41:33,473 --> 00:41:35,740
>> Audienca: [padëgjueshme].

954
00:41:35,740 --> 00:41:37,800
>> DAVID Malan: Yeah, unë nuk e kanë deklaruar
funksion deri të lartë, e drejtë?

955
00:41:37,800 --> 00:41:40,590
C eshte lloj i trashë, ne se ajo vetëm
bën atë që ju them se për të bërë, dhe ju

956
00:41:40,590 --> 00:41:41,880
duhet të bëjë atë në atë mënyrë.

957
00:41:41,880 --> 00:41:45,910
Dhe kështu që nëse unë hit Enter këtu, unë jam duke shkuar për
merrni një paralajmërim në lidhje me Sigma implicit

958
00:41:45,910 --> 00:41:46,860
Deklarata.

959
00:41:46,860 --> 00:41:48,120
>> Oh, nuk është një problem.

960
00:41:48,120 --> 00:41:50,370
I mund shkojnë deri në majë, dhe I mund
thonë, të gjithë të drejtë, prit një minutë.

961
00:41:50,370 --> 00:41:54,240
Sigma është një funksion që kthen
një int dhe ajo pret një

962
00:41:54,240 --> 00:41:56,620
int, pikëpresje si input.

963
00:41:56,620 --> 00:41:59,550
Ose unë mund të vënë në funksion të tërë
më sipër kryesore, por në përgjithësi, unë do të

964
00:41:59,550 --> 00:42:02,260
rekomandoj kundër kësaj, sepse kjo është
bukur që gjithmonë të ketë kryesor në krye kështu

965
00:42:02,260 --> 00:42:06,310
ju mund të zhyten në të drejtë dhe e di se çfarë një
Programi është bërë nga leximi i parë kryesor.

966
00:42:06,310 --> 00:42:07,930
>> Pra, tani më lejoni të qartë në ekran.

967
00:42:07,930 --> 00:42:09,330
Remake SIGMA 0.

968
00:42:09,330 --> 00:42:10,340
Të gjitha duket të shikoni.

969
00:42:10,340 --> 00:42:11,970
Më lejoni të kandidojë SIGMA 0.

970
00:42:11,970 --> 00:42:12,770
Inter pozitive.

971
00:42:12,770 --> 00:42:15,580
Unë do të të jap numrin
3 për të mbajtur atë të thjeshtë.

972
00:42:15,580 --> 00:42:18,710
Kështu që duhet të jepni 3
plus 2 plus 1, pra 6.

973
00:42:18,710 --> 00:42:20,750
Enter, dhe me të vërtetë kam marrë 6.

974
00:42:20,750 --> 00:42:21,820
>> Unë mund të bëj diçka më të madhe -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Ashtu si një tangente, unë jam duke shkuar për të bërë
diçka qesharake si një të vërtetë të madhe

977
00:42:27,690 --> 00:42:30,375
numrin, Oh, që në fakt ka punuar jashtë -

978
00:42:30,375 --> 00:42:31,600
eh, unë nuk mendoj se është e drejtë.

979
00:42:31,600 --> 00:42:32,810
Le të shohim.

980
00:42:32,810 --> 00:42:34,060
Le të vërtetë bela me të.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> Kjo është një problem.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
Çfarë po ndodh?

985
00:42:44,970 --> 00:42:46,050
Kodi nuk është edhe aq keq.

986
00:42:46,050 --> 00:42:48,470
Është ende lineare.

987
00:42:48,470 --> 00:42:50,810
Fishkëllimë është një efekt i mirë, pse.

988
00:42:50,810 --> 00:42:52,060
Çfarë po ndodh?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> Nuk jam i sigurt nëse kam dëgjuar atë.

991
00:42:55,620 --> 00:42:57,620
Pra, ajo rezulton jashtë - dhe
kjo është si një mënjanë.

992
00:42:57,620 --> 00:42:59,400
Kjo nuk është thelbësore për të
Ideja e recursion.

993
00:42:59,400 --> 00:43:02,480
Ajo rezulton, sepse unë jam duke u përpjekur për të
përfaqësojnë një numër kaq të madh, më të

994
00:43:02,480 --> 00:43:06,980
ngjarë se është duke u keqinterpretuar
nga C si një numër jo pozitiv,

995
00:43:06,980 --> 00:43:09,980
por numër negativ.

996
00:43:09,980 --> 00:43:12,690
>> Ne nuk kemi biseduar në lidhje me këtë, por ajo
rezulton atje janë numra negative

997
00:43:12,690 --> 00:43:14,210
në botë përveç
të numrave pozitiv.

998
00:43:14,210 --> 00:43:16,290
Dhe mjetet me të cilat ju mund të
përfaqësojnë një numër negativ

999
00:43:16,290 --> 00:43:19,530
në thelb është, ju përdorni një
bit të veçantë për të treguar

1000
00:43:19,530 --> 00:43:20,400
pozitiv mbi negativ.

1001
00:43:20,400 --> 00:43:22,950
Kjo është pak më komplekse se kaq,
por kjo është ideja themelore.

1002
00:43:22,950 --> 00:43:26,740
>> Pra, për fat të keq, në qoftë se C është konfuze njërin
nga ato copa si në të vërtetë do të thotë,

1003
00:43:26,740 --> 00:43:30,790
oh, ky është një numër negativ, loop ime
këtu, për shembull, nuk është në të vërtetë

1004
00:43:30,790 --> 00:43:31,740
do të përfundojë.

1005
00:43:31,740 --> 00:43:33,850
Pra, në qoftë se unë ishin në fakt shtypje diçka
përsëri dhe përsëri, ne do të

1006
00:43:33,850 --> 00:43:34,650
shoh një shumë të gjithë.

1007
00:43:34,650 --> 00:43:36,220
Por përsëri, kjo është përveç pikë.

1008
00:43:36,220 --> 00:43:38,590
Kjo është me të vërtetë vetëm një lloj i
kuriozitet intelektual që ne do të vijë

1009
00:43:38,590 --> 00:43:39,550
për të mbështetur përfundimisht.

1010
00:43:39,550 --> 00:43:43,400
Por tani për tani, kjo është një e saktë
Zbatimi në qoftë se ne supozojmë se

1011
00:43:43,400 --> 00:43:45,970
përdoruesi do të sigurojë ints
që i përshtatet brenda ints.

1012
00:43:45,970 --> 00:43:49,370
>> Por unë pohojnë se ky kod, sinqerisht,
mund të bëhet shumë më shumë thjesht.

1013
00:43:49,370 --> 00:43:54,060
Nëse qëllimi në dorë është për të marrë një numër të
si m dhe të shtoni deri gjitha

1014
00:43:54,060 --> 00:43:59,510
Numrat midis saj dhe 1, ose anasjelltas
në mes të 1 dhe kjo, unë pretendojnë

1015
00:43:59,510 --> 00:44:03,380
që unë mund të marrë hua këtë ide se bashkuar
Rendit pasur, i cili ishte duke marrë një problem

1016
00:44:03,380 --> 00:44:05,660
i këtij madhësisë dhe ndarë atë
në diçka të vogël.

1017
00:44:05,660 --> 00:44:09,875
Ndoshta jo gjysma, por më të vogla, por
reprezentative njëjtë.

1018
00:44:09,875 --> 00:44:12,130
Njëjtën ide, por një problem i vogël.

1019
00:44:12,130 --> 00:44:15,470
>> Kështu që unë jam në të vërtetë - më lejoni të ruani këtë file
me një numër të ndryshëm version.

1020
00:44:15,470 --> 00:44:17,670
Ne do të quajmë këtë version
1 vend të 0.

1021
00:44:17,670 --> 00:44:20,790
Dhe unë pretendojnë se unë në fakt mund të
reimplement këtë në këtë lloj të

1022
00:44:20,790 --> 00:44:22,160
mendje-bending mënyrë.

1023
00:44:22,160 --> 00:44:23,710
>> Unë jam duke shkuar për të lënë pjesë e saj vetëm.

1024
00:44:23,710 --> 00:44:27,710
Unë jam duke shkuar për të thonë se nëse është më pak m
se, ose të barabartë edhe në 0 -

1025
00:44:27,710 --> 00:44:29,280
Unë jam vetëm do të jetë pak
më shumë anal këtë herë

1026
00:44:29,280 --> 00:44:30,520
me kontrollin tim gabim -

1027
00:44:30,520 --> 00:44:33,190
Unë jam duke shkuar për të shkuar përpara dhe të kthehen 0.

1028
00:44:33,190 --> 00:44:34,490
Kjo është arbitrar.

1029
00:44:34,490 --> 00:44:37,500
Unë jam vetëm thjesht të vendosë nëse përdoruesi
më jep një numër negativ, unë jam

1030
00:44:37,500 --> 00:44:41,490
0 kthehen, dhe ata duhet të kenë lexuar
Dokumentacioni më nga afër.

1031
00:44:41,490 --> 00:44:42,170
>> Else -

1032
00:44:42,170 --> 00:44:44,070
njoftim se çfarë unë jam duke shkuar për të bërë.

1033
00:44:44,070 --> 00:44:49,260
Tjetër unë jam duke shkuar për t'u kthyer m plus -

1034
00:44:49,260 --> 00:44:51,010
çfarë është sigma i m?

1035
00:44:51,010 --> 00:44:56,710
E pra, sigma i m m plus minus 1,
plus minus 2 m, plus minus 3 m.

1036
00:44:56,710 --> 00:44:58,030
Unë nuk dua të shkruaj të gjithë se nga.

1037
00:44:58,030 --> 00:44:59,120
Pse nuk e bëjnë vetëm unë vë bast?

1038
00:44:59,120 --> 00:45:05,080
Recursively quajnë veten me një pak më të
Problemi më i vogël, pikëpresje,

1039
00:45:05,080 --> 00:45:06,840
dhe e quajti atë një ditë?

1040
00:45:06,840 --> 00:45:07,040
>> E drejta?

1041
00:45:07,040 --> 00:45:10,980
Tani këtu, gjithashtu, ju mund të ndjeni apo merak
se kjo është një loop pafund që unë jam

1042
00:45:10,980 --> 00:45:15,450
inducing, ku unë jam zbatimin e
sigma duke telefonuar Sigma.

1043
00:45:15,450 --> 00:45:20,342
Por kjo është në rregull të përkryer, sepse unë
menduar përpara një shtohet cilat linja?

1044
00:45:20,342 --> 00:45:22,600
>> Audienca: [padëgjueshme].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID Malan 23 në 26, i cili
është kusht, nëse im.

1046
00:45:25,430 --> 00:45:28,390
Sepse çfarë është e bukur për
zbritja këtu, sepse unë mbaj

1047
00:45:28,390 --> 00:45:31,180
dorëzimin SIGMA probleme të vogla, të vogla
Problemet, më të vogla - kjo nuk është

1048
00:45:31,180 --> 00:45:31,870
gjysma e madhësisë.

1049
00:45:31,870 --> 00:45:34,380
Kjo është vetëm një hap i vogël fëmija,
por kjo është OK.

1050
00:45:34,380 --> 00:45:38,050
Sepse përfundimisht, ne do të punojmë
rruga jonë deri në 1 ose 0.

1051
00:45:38,050 --> 00:45:41,630
Dhe dikur ne hit 0, sigma nuk
do të thërrasë veten anymore.

1052
00:45:41,630 --> 00:45:43,590
Ajo do të kthehen menjëherë 0.

1053
00:45:43,590 --> 00:45:47,960
>> Pra efekti, në qoftë se ju lloj i erës kjo
deri në mendjen tuaj, është për të shtuar m plus

1054
00:45:47,960 --> 00:45:52,740
m minus 1, plus minus 2 m, m plus minus
3, plus dot, dot, dot, m minus

1055
00:45:52,740 --> 00:45:57,820
M, eventualisht i dhënë ju 0, dhe
efekti është në fund të fundit për të shtuar të gjithë

1056
00:45:57,820 --> 00:45:59,070
këto gjëra së bashku.

1057
00:45:59,070 --> 00:46:02,380
Pra, ne nuk kemi, me recursion,
zgjidhur problemin që ne

1058
00:46:02,380 --> 00:46:03,470
nuk mund të zgjidhë më parë.

1059
00:46:03,470 --> 00:46:06,840
Në të vërtetë, ky version i 0, dhe çdo
Problemi deri më sot, ka qenë i zgjidhshëm

1060
00:46:06,840 --> 00:46:09,980
me vetëm duke përdorur për sythe ose derisa
unazore apo ndërton ngjashme.

1061
00:46:09,980 --> 00:46:13,150
>> Por recursion, unë guxoj të them, na jep
një mënyrë të ndryshme të të menduarit në lidhje me

1062
00:46:13,150 --> 00:46:17,010
Problemet, të cilit, nëse ne mund të marrë një
Problemi, ndajnë atë nga diçka

1063
00:46:17,010 --> 00:46:22,340
disi i madh në diçka disi
të vogla, unë pretendojnë se ne mund ta zgjidhim atë

1064
00:46:22,340 --> 00:46:26,040
ndoshta pak më elegante në aspektin
i dizajnit, me kodin më pak,

1065
00:46:26,040 --> 00:46:30,980
dhe ndoshta edhe zgjidhjen e problemeve që do të
të jetë e vështirë, si ne përfundimisht do të

1066
00:46:30,980 --> 00:46:33,280
shikoni, zgjidhjen thjesht iteratively.

1067
00:46:33,280 --> 00:46:35,980
>> Por cliffhanger që kam bërë
duan të na lënë në ishte kjo.

1068
00:46:35,980 --> 00:46:40,720
Më lejoni të shkojnë përpara dhe të hapur
deri një skedar nga -

1069
00:46:40,720 --> 00:46:44,300
në fakt, më lejoni të shkoj dhe
bëni këtë të shpejtë të vërtetë.

1070
00:46:44,300 --> 00:46:46,875
Më lejoni të shkojnë përpara dhe të propozojë
në vijim.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Në mesin e kodit të sotëm është këtu këtë fotografi.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Ky këtu, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Pra, kjo është një program pak budalla se
Unë whipped up që pretendon të bëjë

1076
00:47:06,260 --> 00:47:06,940
në vijim.

1077
00:47:06,940 --> 00:47:10,140
Në kryesore, ajo së pari shpall një
int x thirri dhe i cakton atë

1078
00:47:10,140 --> 00:47:11,100
Vlera e 1.

1079
00:47:11,100 --> 00:47:13,520
Pastaj ai deklaron një int y dhe
cakton vlerën 2.

1080
00:47:13,520 --> 00:47:15,310
Pastaj ajo printon se çfarë x dhe y është.

1081
00:47:15,310 --> 00:47:17,781
Pastaj ai thotë, shkëmbejnë, Dot dot dot.

1082
00:47:17,781 --> 00:47:21,670
>> Atëherë ajo pretendon të jetë një funksion të quajtur
quhet swap-in, duke kaluar në x dhe

1083
00:47:21,670 --> 00:47:24,290
y, ideja e së cilës është që shpresojmë se
x dhe y do të kthehen

1084
00:47:24,290 --> 00:47:25,620
të ndryshme, të kundërta.

1085
00:47:25,620 --> 00:47:27,110
Pastaj ai swapped pretendojnë!

1086
00:47:27,110 --> 00:47:28,420
me një pikë thirrje.

1087
00:47:28,420 --> 00:47:30,190
Pastaj ajo printon nga x dhe y.

1088
00:47:30,190 --> 00:47:33,480
>> Por kjo rezulton se kjo shumë
Demonstrata e thjeshtë poshtë

1089
00:47:33,480 --> 00:47:35,570
këtu është në të vërtetë buggy.

1090
00:47:35,570 --> 00:47:38,870
Edhe pse unë jam deklaruar një të përkohshme
ndryshueshme dhe vënien përkohësisht në një

1091
00:47:38,870 --> 00:47:42,010
kjo, atëherë unë jam ricaktimin
një vlerë e B -

1092
00:47:42,010 --> 00:47:45,080
e cila ndihet e arsyeshme, sepse unë kam
ruajtur nje kopje te nje ne temp.

1093
00:47:45,080 --> 00:47:48,410
Pastaj unë Përditëso b të barabartë
çdo gjë ishte në temp.

1094
00:47:48,410 --> 00:47:51,610
Ky lloj i lojës lëviz një shell të
në b dhe b ne nje duke përdorur këtë

1095
00:47:51,610 --> 00:47:54,360
mesme-njeri i quajtur temp ndjen
krejtësisht e arsyeshme.

1096
00:47:54,360 --> 00:47:57,270
>> Por unë pretendojnë se kur kam drejtuar këtë
Kodi, si unë do të bëj tani -

1097
00:47:57,270 --> 00:47:59,490
më lejoni të shkoj përpara dhe ngjitur atë në këtu.

1098
00:47:59,490 --> 00:48:01,995
Unë do të thërrasë këtë noswap.c.

1099
00:48:01,995 --> 00:48:05,630
Dhe, si emri sugjeron, kjo nuk është
do të jetë një program i saktë.

1100
00:48:05,630 --> 00:48:09,460
Bëni noswap. / Jo swap.

1101
00:48:09,460 --> 00:48:12,110
x eshte 1, y eshte 2, shkëmbimi, swapped.

1102
00:48:12,110 --> 00:48:14,220
x eshte 1, y eshte 2.

1103
00:48:14,220 --> 00:48:16,920
Kjo është krejtësisht e gabuar, madje edhe
edhe pse kjo duket të përkryer

1104
00:48:16,920 --> 00:48:17,730
arsyeshme për mua.

1105
00:48:17,730 --> 00:48:21,330
Dhe ka një arsye, por ne nuk jemi
do të zbulojë arsyen vetëm ende.

1106
00:48:21,330 --> 00:48:24,610
>> Tani për tani të cliffhanger dytë kam kërkuar
të largohet nga ju me këtë është, një

1107
00:48:24,610 --> 00:48:27,120
Shpallja e terezi të kodeve kupon.

1108
00:48:27,120 --> 00:48:31,590
Risi jonë me ditët e vona këtë vit
ka provokuar një numër jo të parëndësishëm

1109
00:48:31,590 --> 00:48:33,830
e pyetjeve, e cila ishte
nuk është qëllimi ynë.

1110
00:48:33,830 --> 00:48:36,590
Synimi i këtyre kodeve kupon,
të cilit, nëse ju bëni një pjesë e problemit

1111
00:48:36,590 --> 00:48:39,850
vendosur në fillim, duke marrë një ditë shtesë,
ishte me të vërtetë për të ndihmuar ju djema ndihmoni

1112
00:48:39,850 --> 00:48:42,420
veten të fillojë herët lloj,
i incentivizing nga ju.

1113
00:48:42,420 --> 00:48:44,880
Na ndihmon për të shpërndarë ngarkesën nëpër
zyra orë më mirë kështu se

1114
00:48:44,880 --> 00:48:45,740
kjo është lloj i fitojë të fitojë.

1115
00:48:45,740 --> 00:48:48,860
>> Për fat të keq, unë mendoj se udhëzimet e mia
nuk kanë qenë, deri më sot, shumë i qartë, kështu që

1116
00:48:48,860 --> 00:48:52,230
Unë shkova përsëri këtë fundjavë dhe të përditësuar
spekulim në tekstin e mëdha, të guximshme në

1117
00:48:52,230 --> 00:48:53,600
shpjegojë plumba si këto.

1118
00:48:53,600 --> 00:48:56,900
Dhe vetëm për të thënë atë më shumë publikisht, duke
, vendos parazgjedhura problemit janë pasojë e enjte

1119
00:48:56,900 --> 00:48:58,400
në mesditë, në planin mësimor.

1120
00:48:58,400 --> 00:49:02,030
Nëse ju filloni herët, duke përfunduar një pjesë të
Problemi vendosur deri të mërkurën në ora 12:00

1121
00:49:02,030 --> 00:49:05,170
PD, pjesa që ka të bëjë me një kupon
Kodi, ideja është se ju mund të zgjasë

1122
00:49:05,170 --> 00:49:07,710
Afati i juaj për
P vendosur deri të premten.

1123
00:49:07,710 --> 00:49:10,890
Kjo është, pak off një pjesë e vogël e P
të vendosur në lidhje me atë që është në mënyrë tipike

1124
00:49:10,890 --> 00:49:13,200
Problemi më i madh, dhe ju blej
veten një ditë shtesë.

1125
00:49:13,200 --> 00:49:15,190
Përsëri, ajo ju merr të menduarit në lidhje
set problem, ju merr në

1126
00:49:15,190 --> 00:49:16,380
zyra orë më herët.

1127
00:49:16,380 --> 00:49:20,670
Por kodin kupon problemi është ende
nevojshme, edhe në qoftë se ju nuk e dorëzon atë.

1128
00:49:20,670 --> 00:49:23,340
>> Por më shumë compellingly është kjo.

1129
00:49:23,340 --> 00:49:26,520
(Whisper FAZA) dhe ata folks duke lënë
herët janë gonna zhgenjeheni.

1130
00:49:26,520 --> 00:49:28,620
Si janë folks në ballkon.

1131
00:49:28,620 --> 00:49:32,510
Unë kërkoj falje paraprakisht folks në
ballkon për arsye që do të jenë

1132
00:49:32,510 --> 00:49:33,920
qartë në një moment të vetëm.

1133
00:49:33,920 --> 00:49:37,050
>> Pra, ne jemi me fat që të ketë njërin prej
Bursistët ish CS50 e mësimdhënies në kokë

1134
00:49:37,050 --> 00:49:39,302
një kompani e quajtur dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
Ata kanë shumë bujarisht dhuruar një
Kodi kupon këtu për këtë më shumë hapësirë,

1136
00:49:45,500 --> 00:49:48,180
cili eshte lart nga
zakonshme 2 gigabajt.

1137
00:49:48,180 --> 00:49:51,740
Pra, ajo që unë mendova që ne do të bëjmë në këtë
shënim i fundit është bërë një grimë e një dhuroj,

1138
00:49:51,740 --> 00:49:55,380
ku në një moment të vetëm, ne do të zbulojë
fitues dhe i cili ka një kupon

1139
00:49:55,380 --> 00:49:57,980
kodin që atëherë ju mund të shkoni në e tyre
Faqja e internetit, shkruani atë në, dhe voila, të merrni një

1140
00:49:57,980 --> 00:50:01,370
tërësi shumë më tepër hapësirë ​​për Dropbox tuaj
për aplikim dhe dosjet tuaja personale.

1141
00:50:01,370 --> 00:50:05,690
>> Dhe së pari, që do të donte për të marrë pjesë
në këtë vizatim?

1142
00:50:05,690 --> 00:50:09,630
OK, tani që e bën atë edhe më shumë argëtim.

1143
00:50:09,630 --> 00:50:14,010
Personi i cili merr këtë 25-Gigabyte
Kodi kupon - e cila është larg

1144
00:50:14,010 --> 00:50:16,150
më bindëse se vonë
ditë tani, ndoshta -

1145
00:50:16,150 --> 00:50:20,620
është ai i cili është ulur në majë të një
jastëk vend nëpër të cilin ka

1146
00:50:20,620 --> 00:50:21,620
se kodi kupon.

1147
00:50:21,620 --> 00:50:23,480
Ju tani mund të duket nën
jastëk tuaj vend.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [Video playback]

1150
00:50:29,680 --> 00:50:31,620
>> -Një, dy, tre.

1151
00:50:31,620 --> 00:50:35,015
>> [Ulëritës]

1152
00:50:35,015 --> 00:50:35,985
>> -Ju merrni një makinë!

1153
00:50:35,985 --> 00:50:36,670
Ju merrni një makinë!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID Malan: Ne do të shohim
ju të mërkurën.

1155
00:50:37,970 --> 00:50:38,904
>> -Ju merrni një makinë!

1156
00:50:38,904 --> 00:50:39,371
Ju merrni një makinë!

1157
00:50:39,371 --> 00:50:40,305
Ju merrni një makinë!

1158
00:50:40,305 --> 00:50:41,706
Ju merrni një makinë!

1159
00:50:41,706 --> 00:50:43,107
Ju merrni një makinë!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID Malan: folks Ballkon, vijnë
këtu poshtë në pjesën e përparme,

1161
00:50:45,530 --> 00:50:46,866
ku ne kemi ekstra.

1162
00:50:46,866 --> 00:50:50,282
>> -Gjithkush merr një makinë!

1163
00:50:50,282 --> 00:50:52,234
Gjithkush merr një makinë!

1164
00:50:52,234 --> 00:50:52,722
>> [VIDEO END rishikim]

1165
00:50:52,722 --> 00:50:54,590
>> Transmetuesi: Në CS50 e ardhshëm -

1166
00:50:54,590 --> 00:51:00,374
>> 5 Gjuha: Oh my gosh gosh gosh gosh
gosh gosh gosh gosh gosh gosh -

1167
00:51:00,374 --> 00:51:02,106
>> [Luan UKELELE]