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

2
00:00:00,488 --> 00:00:10,800
>> [Mūzikas atskaņošanas]

3
00:00:10,800 --> 00:00:13,500
DAVID Malan: Nu labi.

4
00:00:13,500 --> 00:00:14,670
Visas tiesības, welcome atpakaļ.

5
00:00:14,670 --> 00:00:18,120
Tātad šī ir nedēļa 4, sākums
pantu, jau ir.

6
00:00:18,120 --> 00:00:21,320
Un jums atgādināt, ka pagājušajā nedēļā, mēs liekam
kodu malā, lai tikai mazliet

7
00:00:21,320 --> 00:00:24,240
un mēs sākām runāt nedaudz vairāk
augsta līmeņa, par lietām, piemēram,

8
00:00:24,240 --> 00:00:28,130
meklēšanu un kārtošanu, kas gan
nedaudz vienkāršas idejas, ir

9
00:00:28,130 --> 00:00:31,840
pārstāvis klases problēmas
jūs varēsiet atrisināt īpaši

10
00:00:31,840 --> 00:00:34,820
kā jūs sākat domāt par galīgo
projekti un interesanti risinājumi jums

11
00:00:34,820 --> 00:00:36,760
varētu būt reālās pasaules problēmas.

12
00:00:36,760 --> 00:00:39,490
Tagad burbulis veida bija viens no vienkāršākajiem
šie algoritmi, un tas

13
00:00:39,490 --> 00:00:42,900
strādāja, ņemot šos nelielu skaitu
sarakstā vai masīva veida

14
00:00:42,900 --> 00:00:46,530
burbulis savu ceļu uz augšu uz augšu, un
lielos skaitļus pārvietot savu ceļu uz leju, lai

15
00:00:46,530 --> 00:00:47,930
beigās šajā sarakstā.

16
00:00:47,930 --> 00:00:50,650
>> Un atcerēties, ka mēs varētu iztēloties
burbulis šķirot nedaudz

17
00:00:50,650 --> 00:00:52,310
kaut kas līdzīgs šim.

18
00:00:52,310 --> 00:00:53,640
Tātad, ļaujiet man iet uz priekšu un noklikšķiniet uz Sākt.

19
00:00:53,640 --> 00:00:55,350
Esmu iepriekš izvēlēta burbulis šķirot.

20
00:00:55,350 --> 00:00:58,920
Un, ja jūs atceraties, ka augstāks zila
līnijas veido lielos skaitļus, mazs

21
00:00:58,920 --> 00:01:03,300
zilās līnijas veido nelielu skaitu, jo
mēs iet caur šo atkal un atkal, un

22
00:01:03,300 --> 00:01:07,680
atkal, salīdzinot divas joslas blakus viens
otru sarkanu, mēs ejam, lai mijmaiņas

23
00:01:07,680 --> 00:01:11,010
lielākais un mazākais, ja
tās ir bojātas.

24
00:01:11,010 --> 00:01:14,150
>> Tātad tas iet un iet un iet
gada, un jūs redzēsiet, ka lielāks

25
00:01:14,150 --> 00:01:16,700
elementi ir padarīt savu ceļu uz
pa labi, un mazākās elementi ir

26
00:01:16,700 --> 00:01:17,900
padarot savu ceļu pa kreisi.

27
00:01:17,900 --> 00:01:21,380
Bet mēs sākām kvantitatīvi
efektivitāte,

28
00:01:21,380 --> 00:01:22,970
kvalitāte šī algoritma.

29
00:01:22,970 --> 00:01:25,200
Un mēs teicām, ka sliktākajā
gadījumā, šis algoritms bija

30
00:01:25,200 --> 00:01:27,940
aptuveni cik soļus?

31
00:01:27,940 --> 00:01:28,980
>> Tātad n kvadrātā.

32
00:01:28,980 --> 00:01:30,402
Un kāda bija n?

33
00:01:30,402 --> 00:01:31,650
>> Mērķauditorija: Elementu skaits.

34
00:01:31,650 --> 00:01:32,790
>> DAVID Malan: Tātad n bija
elementu skaits.

35
00:01:32,790 --> 00:01:33,730
Un tā mēs darīsim to bieži.

36
00:01:33,730 --> 00:01:36,650
Katru reizi, kad mēs vēlamies runāt par lielumu
par problēmu vai izmēru

37
00:01:36,650 --> 00:01:39,140
ievadi, vai laika daudzums, kas nepieciešams
ražot produkciju, mēs vienkārši

38
00:01:39,140 --> 00:01:41,610
ģeneralizētas neatkarīgi
ievade ir kā n.

39
00:01:41,610 --> 00:01:45,970
Tātad atpakaļ 0 nedēļas, numuru lapas
tālruņu katalogā bija n.

40
00:01:45,970 --> 00:01:47,550
Studentu skaits
telpā tika n.

41
00:01:47,550 --> 00:01:49,630
Tātad arī šeit, mēs esam pēc
ka modelis.

42
00:01:49,630 --> 00:01:52,800
>> Tagad n kvadrātā nav īpaši
ātri, tāpēc mēģinājām darīt labāk.

43
00:01:52,800 --> 00:01:55,970
Un tā mēs paskatījās pāris
citi algoritmi, kuru vidū

44
00:01:55,970 --> 00:01:57,690
bija izvēle kārtošanas.

45
00:01:57,690 --> 00:01:59,180
Tātad izvēle kārtošanas bija
nedaudz atšķiras.

46
00:01:59,180 --> 00:02:03,130
Tas bija gandrīz vienkāršāk, es uzdrošinos teikt,
, saskaņā ar kuru es sākās sākumā

47
00:02:03,130 --> 00:02:06,740
mūsu brīvprātīgajiem sarakstu, un es tikko atkal
un atkal un atkal gāja cauri

48
00:02:06,740 --> 00:02:10,060
sarakstā, noplūkšanas no mazākā
laikā elements, un liekot viņam vai

49
00:02:10,060 --> 00:02:13,040
viņas pie saraksta sākumā.

50
00:02:13,040 --> 00:02:16,410
>> Bet tas arī, kad mēs sākām domāt
ar matemātiku un lielāks

51
00:02:16,410 --> 00:02:19,860
attēlu, domāja par to, cik reizes
Man bija iet uz priekšu un atpakaļ un atpakaļ

52
00:02:19,860 --> 00:02:24,090
un atpakaļ, mēs teicām, sliktākajā gadījumā,
atlase kārtot, arī bija tas, ko?

53
00:02:24,090 --> 00:02:24,960
n rūtiņām.

54
00:02:24,960 --> 00:02:27,490
Tagad reālajā pasaulē, tas varētu
patiesībā var būt nedaudz ātrāk.

55
00:02:27,490 --> 00:02:30,620
Jo atkal, man nav, lai saglabātu
atteikšanās kad man bija sakārtoti

56
00:02:30,620 --> 00:02:31,880
Vismazākās elementi.

57
00:02:31,880 --> 00:02:35,090
Bet, ja mēs domājam par ļoti lielu n, un
ja jūs veida jādara norādīts math kā

58
00:02:35,090 --> 00:02:39,170
I did uz kuģa, ar n kvadrātā
mīnus kaut kas, viss pārējais

59
00:02:39,170 --> 00:02:41,850
turklāt n brusas, reizi n
izpaužas patiešām liels, nav

60
00:02:41,850 --> 00:02:42,850
īsti jautājums tik daudz.

61
00:02:42,850 --> 00:02:45,470
Tā kā datorzinātnieku, mums sava veida
pievērt acis uz mazāku

62
00:02:45,470 --> 00:02:49,220
faktori un tikai faktors koncentrēsies
izteiksme, kas notiek, lai

63
00:02:49,220 --> 00:02:50,330
lielākā atšķirība.

64
00:02:50,330 --> 00:02:52,840
>> Nu, visbeidzot, mēs skatījāmies
pēc ievietošanas veida.

65
00:02:52,840 --> 00:02:56,620
Un tas bija līdzīgs garā, bet
nevis iet cauri iteratīvi un

66
00:02:56,620 --> 00:03:01,250
izvēlētos mazāko elementu vienam
laiku, es tā vietā veica roku, ka es

67
00:03:01,250 --> 00:03:04,070
Tika izskatīts, un es nolēmu, visi
labi, jūs piederat šeit.

68
00:03:04,070 --> 00:03:06,160
Tad es pārvietots uz nākamo elementu
un nolēma, ka viņš vai

69
00:03:06,160 --> 00:03:07,470
viņa piederēja šeit.

70
00:03:07,470 --> 00:03:08,810
Un tad es pārcēlos vēl un vēl.

71
00:03:08,810 --> 00:03:11,780
Un es varētu to, pa ceļam,
maiņu šie puiši, lai

72
00:03:11,780 --> 00:03:13,030
padarītu telpu par viņiem.

73
00:03:13,030 --> 00:03:16,880
Tā, ka bija sava veida garīgo maiņu
atlases veida, ka mēs

74
00:03:16,880 --> 00:03:18,630
sauc ievietošanas veida.

75
00:03:18,630 --> 00:03:20,810
>> Tātad šie temati rodas
reālajā pasaulē.

76
00:03:20,810 --> 00:03:23,640
Tikai pirms dažiem gadiem, kad dažas
senators skrēja par prezidentu,

77
00:03:23,640 --> 00:03:27,160
Eric Schmidt, brīdī, kad vadītājs
Google, faktiski bija iespēja

78
00:03:27,160 --> 00:03:28,040
intervēt viņu.

79
00:03:28,040 --> 00:03:32,010
Un mēs domājam, ka mēs gribētu dalīties ar šo YouTube
klipu, lai jūs šeit, ja mēs varētu uzlocīt

80
00:03:32,010 --> 00:03:32,950
tilpums.

81
00:03:32,950 --> 00:03:39,360
>> [VIDEO PLAYBACK]

82
00:03:39,360 --> 00:03:44,620
>> -Tagad, senators, jūs esat šeit Google,
un man patīk domāt par prezidentūras

83
00:03:44,620 --> 00:03:46,042
kā darba interviju.

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

85
00:03:47,770 --> 00:03:50,800
>> -Tagad tas ir grūti iegūt
darbu kā prezidents.

86
00:03:50,800 --> 00:03:52,480
Un jūs iet cauri
drebuļi tagad.

87
00:03:52,480 --> 00:03:54,330
Tas ir arī grūti iegūt darbu pie Google.

88
00:03:54,330 --> 00:03:59,610
Mums ir jautājumi, un mēs lūdzam
Mūsu kandidāti jautājumi.

89
00:03:59,610 --> 00:04:02,250
Un tas viens ir no Larry Schwimmer.

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

91
00:04:05,325 --> 00:04:06,400
-Jūs guys domāju, ka es esmu kidding?

92
00:04:06,400 --> 00:04:08,750
Tas ir labi šeit.

93
00:04:08,750 --> 00:04:12,110
Kāds ir visefektīvākais veids, kā
šķirot miljons divu bitu integers?

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

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

96
00:04:18,260 --> 00:04:19,029
>> -I'm žēl.

97
00:04:19,029 --> 00:04:19,745
Varbūt mums vajadzētu -

98
00:04:19,745 --> 00:04:21,000
>> -Nē, nē, nē, nē, nē.

99
00:04:21,000 --> 00:04:21,470
>> -Tas nav -

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

101
00:04:22,185 --> 00:04:25,328
>> -Es domāju, ka burbuļa kārtošanas būtu
ir nepareizs veids, kā iet.

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

103
00:04:26,792 --> 00:04:28,510
>> [Uzmundrinoša un aplausi]

104
00:04:28,510 --> 00:04:31,211
>> -Nāc, kurš viņam šo?

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

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

107
00:04:33,350 --> 00:04:35,070
>> DAVID Malan: Tātad jums ir tā.

108
00:04:35,070 --> 00:04:39,600
Tāpēc mēs sākām aprēķināt šos darbojas
reizes, tā sakot, ar kaut ko

109
00:04:39,600 --> 00:04:43,480
sauc asimptotiskās apzīmējums, kas ir
tikai, atsaucoties uz mūsu veida pagrieziena

110
00:04:43,480 --> 00:04:47,420
neredzam šos mazākiem faktoriem un
tikai meklē braukšanas laikā,

111
00:04:47,420 --> 00:04:51,250
sniegumu šiem algoritmiem,
kā n izpaužas patiešām liels laika gaitā.

112
00:04:51,250 --> 00:04:55,110
Un tā mēs ieviesām liels O. And Big O
pārstāv kaut kas mēs domājam

113
00:04:55,110 --> 00:04:57,000
no kā augstākā robeža.

114
00:04:57,000 --> 00:04:59,570
Un patiesībā, Barry, mēs varam samazināt
nekā mic maz bitu?

115
00:04:59,570 --> 00:05:01,040
>> Mēs domājām, ka no tā ir augšējā robeža.

116
00:05:01,040 --> 00:05:04,710
Tik liela O no n kvadrātā nozīmē, ka
sliktākajā gadījumā, kaut kas līdzīgs

117
00:05:04,710 --> 00:05:07,780
atlase kārtošanas varētu veikt
n kvadrātā soļus.

118
00:05:07,780 --> 00:05:10,310
Vai kaut kas tamlīdzīgs ievietošanas veida
būtu n kvadrātā soļi.

119
00:05:10,310 --> 00:05:15,150
Tagad kaut ko līdzīgu ievietošanai
kārtošanas, kas bija sliktākais?

120
00:05:15,150 --> 00:05:18,200
Ņemot vērā masīvs, kas ir sliktākais
iespējams scenārijs, ka jūs varētu atrast

121
00:05:18,200 --> 00:05:20,650
sev saskaras ar?

122
00:05:20,650 --> 00:05:21,860
>> Tas ir pilnīgi atpakaļ, vai ne?

123
00:05:21,860 --> 00:05:24,530
Jo, ja tas ir pilnīgi atpakaļ,
jums ir jādara visai daudz darba.

124
00:05:24,530 --> 00:05:26,420
Jo, ja jūs esat pilnīgi atpakaļ,
jūs gatavojas atrast

125
00:05:26,420 --> 00:05:28,840
Lielākā daļa šeit, lai gan
tas pieder tur lejā.

126
00:05:28,840 --> 00:05:31,140
Tātad jūs gatavojas teikt, visas tiesības pēc
šis laika brīdis, jūs piederat šeit,

127
00:05:31,140 --> 00:05:32,310
lai jūs atstāt to atsevišķi.

128
00:05:32,310 --> 00:05:35,425
>> Tad tu saproti, ak, damn, man ir
pārvietot šo nedaudz mazāks elements, lai

129
00:05:35,425 --> 00:05:36,470
kreisi no jums.

130
00:05:36,470 --> 00:05:38,770
Tad man ir jādara, ka atkal
un atkal un atkal.

131
00:05:38,770 --> 00:05:41,410
Un, ja man gāja uz priekšu un atpakaļ, jūs
būtu sava veida justies sniegumu

132
00:05:41,410 --> 00:05:45,540
ka algoritms, jo pastāvīgi esmu es
shuffling visi pārējie noteikti

133
00:05:45,540 --> 00:05:46,510
masīvs, lai atbrīvotu vietu tajā.

134
00:05:46,510 --> 00:05:47,750
Tātad tas ir sliktākajā gadījumā.

135
00:05:47,750 --> 00:05:48,570
>> Turpretī -

136
00:05:48,570 --> 00:05:50,320
un tas bija cliffhanger pēdējo reizi -

137
00:05:50,320 --> 00:05:54,065
mēs teicām, ka ievietošana veida
bija par to, ko omega?

138
00:05:54,065 --> 00:05:57,530
Kas ir labākā lieta iebraukšanu
laiks ievietošanas veida?

139
00:05:57,530 --> 00:05:58,520
Tātad, tas ir patiešām n.

140
00:05:58,520 --> 00:06:00,980
Tas bija tukša, ka mēs pa kreisi
uz kuģa pēdējā reize.

141
00:06:00,980 --> 00:06:03,160
>> Un tas ir omega n jo kāpēc?

142
00:06:03,160 --> 00:06:06,630
Nu, ļoti labākajā gadījumā, kas ir
ievietošanas kārtošanas būs jānodod?

143
00:06:06,630 --> 00:06:09,830
Nu, saraksts, kas ir pilnībā sakārtoti
jau minimāla jāstrādā.

144
00:06:09,830 --> 00:06:12,460
Bet kas ir veikls par ievietošanas veida
ir tas, ka tāpēc, ka tas sākas šeit un

145
00:06:12,460 --> 00:06:15,340
nolemj, ak, jūs esat numuru
viens, jūs piederat šeit.

146
00:06:15,340 --> 00:06:16,970
Ak, kāda laime.

147
00:06:16,970 --> 00:06:17,740
>> Tu esi numur divi.

148
00:06:17,740 --> 00:06:19,030
Jūs arī piederat šeit.

149
00:06:19,030 --> 00:06:21,010
Numurs trīs, vēl labāk,
jūs piederat šeit.

150
00:06:21,010 --> 00:06:25,210
Tiklīdz tā izpaužas uz beigām
sarakstā, par ievietošanas kārtot s pseudocode

151
00:06:25,210 --> 00:06:28,010
ka mēs gājām cauri mutiski
pēdējo reizi, tas ir darīts.

152
00:06:28,010 --> 00:06:32,790
Bet izvēle kārtot, gluži pretēji,
tur dara ko?

153
00:06:32,790 --> 00:06:35,260
>> Tur iet cauri sarakstam
atkal un atkal un atkal.

154
00:06:35,260 --> 00:06:39,160
Jo galvenais ieskats bija tikai
kad jūs esat izskatījās visu veidu

155
00:06:39,160 --> 00:06:42,500
saraksta beigās var jums būt drošs
ka elements izvēlējāties bija

156
00:06:42,500 --> 00:06:45,560
patiešām šobrīd mazākais elements.

157
00:06:45,560 --> 00:06:48,920
Tātad, šīs dažādās garīgās modeļi beigas
līdz iegūstot dažas ļoti reālā pasaule

158
00:06:48,920 --> 00:06:53,130
atšķirības, lai mēs, kā arī šīs
teorētiskās asimptotiskās atšķirības.

159
00:06:53,130 --> 00:06:56,910
>> Tik vienkārši, lai Atgādinājums, tad liela O no n
kvadrātā, mēs esam redzējuši dažas tādas

160
00:06:56,910 --> 00:06:58,350
algoritmi līdz šim.

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

162
00:06:59,580 --> 00:07:02,870
Kas ir algoritms, kas varētu
teikt, ka liels O n?

163
00:07:02,870 --> 00:07:06,930
Sliktākajā gadījumā, tas aizņem
lineāra skaits no soļiem.

164
00:07:06,930 --> 00:07:07,810
>> Labi, lineāra meklēšanu.

165
00:07:07,810 --> 00:07:10,470
Un sliktākajā gadījumā, ja ir
elements, jūs meklējat, kad

166
00:07:10,470 --> 00:07:12,950
piemērojot lineāru meklēt?

167
00:07:12,950 --> 00:07:14,680
>> Labi, sliktākajā gadījumā,
tas nav pat tur.

168
00:07:14,680 --> 00:07:17,000
Vai otrajā sliktākajā gadījumā, tas ir
visu ceļu beigās, kas ir

169
00:07:17,000 --> 00:07:18,880
plus-vai-mīnus vienu soli atšķirība.

170
00:07:18,880 --> 00:07:21,180
Tātad, beigās, dienā,
mēs varam teikt, tas ir lineāra.

171
00:07:21,180 --> 00:07:23,910
Big O n būtu lineāra meklēšanu,
jo sliktākajā gadījumā,

172
00:07:23,910 --> 00:07:26,610
elements nav pat tur, vai tas ir
visu ceļu beigās.

173
00:07:26,610 --> 00:07:29,370
>> Nu, liela O no žurnāla n.

174
00:07:29,370 --> 00:07:32,760
Mēs nerunājām ļoti detalizēti par
, bet mēs esam redzējuši šo pirms.

175
00:07:32,760 --> 00:07:36,840
Kas darbojas ts logaritmiska
laiks, sliktākajā gadījumā?

176
00:07:36,840 --> 00:07:38,500
>> Jā, tā bināro meklēšanu.

177
00:07:38,500 --> 00:07:42,930
Un bināro meklēšanu sliktākajā gadījumā
varētu būt elements kaut kur

178
00:07:42,930 --> 00:07:45,640
vidū, vai kaut kur
iekšpusē masīvs.

179
00:07:45,640 --> 00:07:48,040
Bet jūs tikai atrast to, kad jūs
sadalīt sarakstu, uz pusēm, kas

180
00:07:48,040 --> 00:07:48,940
puse, uz pusēm, uz pusēm.

181
00:07:48,940 --> 00:07:50,200
Un tad voila, tas ir tur.

182
00:07:50,200 --> 00:07:52,500
Vai atkal, sliktākajā gadījumā,
tas nav pat tur.

183
00:07:52,500 --> 00:07:56,770
Bet jūs nezināt, ka tas nav tur
līdz jūs veida sasniegt, ka pagājušajā

184
00:07:56,770 --> 00:08:00,470
bottom-lielākā daļa elementu, uz pusi samazinot
un pusi un pusi.

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

186
00:08:01,400 --> 00:08:03,540
Tātad, mēs varētu Big O 2, lielo O 3.

187
00:08:03,540 --> 00:08:06,260
Anytime jūs vēlaties tikai konstantu skaitli,
mēs vienkārši šķirot, lai tikai vienkāršotu

188
00:08:06,260 --> 00:08:07,280
ka kā liels O no 1.

189
00:08:07,280 --> 00:08:10,440
Kaut gan, ja reāli, tas aizņem
2 vai pat 100 soļus, ja tas ir

190
00:08:10,440 --> 00:08:13,680
pastāvīga virkne pasākumu,
mēs tikai pateikt lielu O gada 1.

191
00:08:13,680 --> 00:08:15,930
Kas ir algoritms, kas ir
lielas O no 1?

192
00:08:15,930 --> 00:08:18,350
>> Mērķauditorija: Meklējot garumu
ir mainīgs.

193
00:08:18,350 --> 00:08:21,090
>> DAVID Malan: Meklējot
garums ir mainīgs?

194
00:08:21,090 --> 00:08:23,870
>> Mērķauditorija: Nē, garums
ja tas jau ir sakārtoti.

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

196
00:08:24,160 --> 00:08:27,850
Labi, tāpēc atrast garumu kaut
ja garums, kas kaut ko, piemēram,

197
00:08:27,850 --> 00:08:30,020
masīvs, tiek glabāti kādā mainīga.

198
00:08:30,020 --> 00:08:33,380
Tāpēc, ka jūs varat vienkārši lasīt mainīgo,
vai izdrukāt mainīgo, vai

199
00:08:33,380 --> 00:08:34,960
tikai parasti piekļūt šo mainīgo.

200
00:08:34,960 --> 00:08:37,299
Un voila, kas prasa pastāvīgu laiku.

201
00:08:37,299 --> 00:08:38,909
>> Turpretī, domāju, ka atpakaļ, lai nesaskrāpētu.

202
00:08:38,909 --> 00:08:42,460
Domāt atpakaļ uz pirmajā nedēļā C,
zvana tikai printf un drukāšana

203
00:08:42,460 --> 00:08:46,240
kaut ko uz ekrāna, ir apstrīdami
pastāvīgu laiku, jo tā vienkārši notiek

204
00:08:46,240 --> 00:08:50,880
daži skaits CPU ciklu, lai parādītu
šis teksts uz ekrāna.

205
00:08:50,880 --> 00:08:52,720
Vai gaidīt - tas?

206
00:08:52,720 --> 00:08:56,430
Kā gan citādi mēs varbūt modelēt
izpilde printf?

207
00:08:56,430 --> 00:09:00,420
Vai kāds gribētu nepiekrist, ka
varbūt tas nav īsti konstante laiks?

208
00:09:00,420 --> 00:09:03,600
Kādā ziņā varētu printf ir palicis
laiks, kas faktiski drukāšanas virkni par

209
00:09:03,600 --> 00:09:05,580
ekrāns, ir kaut
, kas nav konstante.

210
00:09:05,580 --> 00:09:07,860
>> Mērķauditorija: [nedzirdama].

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

212
00:09:08,230 --> 00:09:09,300
Tātad tas ir atkarīgs no mūsu viedokļa.

213
00:09:09,300 --> 00:09:13,390
Ja mēs patiesībā domājam par ieguldījumu
printf kā stīgu, un

214
00:09:13,390 --> 00:09:16,380
tāpēc mēs novērtējam izmēru, kas
ieeja ar savu garumu - tāpēc sauksim

215
00:09:16,380 --> 00:09:17,780
ka garums n kā arī -

216
00:09:17,780 --> 00:09:21,990
varbūt, printf pati liela O no n
tāpēc, ka tas notiek, lai jūs n soļi

217
00:09:21,990 --> 00:09:24,750
izdrukāt katru no tiem n
rakstzīmes, visticamāk.

218
00:09:24,750 --> 00:09:27,730
Vismaz tādā mērā, ka mēs pieņemam
ka varbūt tas ir, izmantojot uz cilpas

219
00:09:27,730 --> 00:09:28,560
zem motora pārsega.

220
00:09:28,560 --> 00:09:30,860
>> Bet mums būtu apskatīt, ka
Kods, lai saprastu labāk.

221
00:09:30,860 --> 00:09:33,650
Un tiešām, kad jūs puiši sāk
analizējot savus algoritmus, jūs

222
00:09:33,650 --> 00:09:34,900
burtiski darīt tieši to.

223
00:09:34,900 --> 00:09:37,765
Kārtot ābola savu kodu, un domāju, ka
par - labi, man ir šī cilpa

224
00:09:37,765 --> 00:09:41,870
šeit vai man ir Nested cilpas šeit,
kas gatavojas darīt n lietas n reizes,

225
00:09:41,870 --> 00:09:46,050
un jūs varat kārtot saprāta savu ceļu
izmantojot kodu, pat ja tas ir

226
00:09:46,050 --> 00:09:47,980
pseudocode un nevis faktiskais kods.

227
00:09:47,980 --> 00:09:49,730
>> Tātad, ko par omega no n kvadrātā?

228
00:09:49,730 --> 00:09:53,582
, Kas bija algoritmu, kas ir vislabāk
gadījumā, vēl bija n kvadrātā soļi?

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

230
00:09:54,014 --> 00:09:54,880
>> Mērķauditorija: [nedzirdama].

231
00:09:54,880 --> 00:09:55,900
>> DAVID Malan: Tātad izvēle kārtošanas.

232
00:09:55,900 --> 00:09:59,150
Jo šo problēmu tiešām ir samazināts
ar to, ka no jauna, es nezinu

233
00:09:59,150 --> 00:10:02,600
Es esmu atradis pašreizējā mazākais līdz
Esmu pārbaudījusi visus darn elementus.

234
00:10:02,600 --> 00:10:08,050
Tā omega no, teiksim, n, mēs
tikko nāca klajā ar vienu.

235
00:10:08,050 --> 00:10:09,300
Ievietošanas kārtošanas.

236
00:10:09,300 --> 00:10:12,370
Ja saraksta notiek, ir sakārtoti
jau ir, labākajā gadījumā mums vienkārši ir

237
00:10:12,370 --> 00:10:15,090
, lai iegūtu vienu iet caur to,
kurā brīdī mēs esam pārliecināti.

238
00:10:15,090 --> 00:10:17,890
Un tad varētu teikt,
ir lineāra, protams.

239
00:10:17,890 --> 00:10:20,570
>> Kas par omega-1?

240
00:10:20,570 --> 00:10:23,790
Kas, labākajā gadījumā, varētu veikt
pastāvīga vairāki soļi?

241
00:10:23,790 --> 00:10:27,220
Tātad lineāra meklēt, ja jūs vienkārši saņemt laimīgs
un elements, jūs meklējat

242
00:10:27,220 --> 00:10:31,000
ir labi pie saraksta sākumā,
ja tas ir, ja jūs, sākot savu

243
00:10:31,000 --> 00:10:33,070
lineāra šķērsošana minētajā sarakstā.

244
00:10:33,070 --> 00:10:35,180
>> Un tā ir taisnība,
vairākas lietas.

245
00:10:35,180 --> 00:10:37,660
Piemēram, pat binārā
meklēšana ir omega gada 1.

246
00:10:37,660 --> 00:10:40,310
Jo ko tad, ja Jums ir patiešām lāpīt
laimīgs un nokrāsa-DAB vidū

247
00:10:40,310 --> 00:10:42,950
Jūsu masīvs ir skaitlis
jūs meklējat?

248
00:10:42,950 --> 00:10:45,730
Tātad jūs varat saņemt laimīgs tur, kā labi.

249
00:10:45,730 --> 00:10:49,190
>> Tas viens, visbeidzot, omega n log n.

250
00:10:49,190 --> 00:10:52,573
Tātad n log n, mēs neesam īsti
runāt par vēl, bet -

251
00:10:52,573 --> 00:10:53,300
>> Mērķauditorija: Apvienot kārtot?

252
00:10:53,300 --> 00:10:53,960
>> DAVID Malan: Apvienot kārtošanas.

253
00:10:53,960 --> 00:10:56,920
Tas bija cliffhanger par pēdējo reizi,
kur mēs ierosinājām, un mēs parādījām

254
00:10:56,920 --> 00:10:58,600
vizuāli, ka tur ir algoritmi.

255
00:10:58,600 --> 00:11:02,470
Un apvienot veida tikai viens šāds
algoritmu, kas ir būtiski ātrāk

256
00:11:02,470 --> 00:11:03,450
kā daži no šiem citiem puišiem.

257
00:11:03,450 --> 00:11:07,800
Faktiski, apvienot īss ir ne tikai
Labākajā gadījumā n log n, jo sliktākajā

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

259
00:11:09,460 --> 00:11:14,540
Un, ja jums ir šāda sakritība
omega un lielo O ir viens un tas pats?

260
00:11:14,540 --> 00:11:17,310
Mēs faktiski var aprakstīt, ka to, kas ir
sauc par teta, lai gan tas ir

261
00:11:17,310 --> 00:11:18,220
nedaudz mazāk izplatīta.

262
00:11:18,220 --> 00:11:21,730
Bet tas tikai nozīmē divas robežas,
šajā gadījumā, ir tas pats.

263
00:11:21,730 --> 00:11:25,770
>> Tātad apvienot veida, ko tas
tiešām vārīties uz leju, lai mums?

264
00:11:25,770 --> 00:11:27,000
Nu, atgādināt motivāciju.

265
00:11:27,000 --> 00:11:30,340
Ļaujiet man uzvilkt citu animāciju, ka
mēs neesam apskatīt pēdējo reizi.

266
00:11:30,340 --> 00:11:33,390
Tas viens, pati ideja, bet
tas ir nedaudz lielāks.

267
00:11:33,390 --> 00:11:36,160
Un es iešu uz priekšu un norādīt
Pirmais - mēs esam ievietošanas secībā

268
00:11:36,160 --> 00:11:39,410
augšējā kreisajā pusē, tad izvēle kārtot,
burbulis kārtot, pāris citu veidu -

269
00:11:39,410 --> 00:11:42,670
čaulas un ātri - ka mēs neesam runājuši
par, un kaudzes un apvienot veida.

270
00:11:42,670 --> 00:11:47,090
>> Tātad vismaz mēģināt koncentrēties acis uz
top trīs pa kreisi un pēc tam

271
00:11:47,090 --> 00:11:49,120
apvienot veida, kad es noklikšķiniet
Šī zaļā bulta.

272
00:11:49,120 --> 00:11:51,900
Bet es let visi no tiem darbojas, tikai
jums sajūtu daudzveidību

273
00:11:51,900 --> 00:11:53,980
algoritmi, kas pastāv pasaulē.

274
00:11:53,980 --> 00:11:56,180
Es esmu gatavojas let šo skrējienu
tikai dažas sekundes.

275
00:11:56,180 --> 00:11:59,640
Un, ja jums koncentrēties jūsu acis - izvēlēties
algoritms, jākoncentrējas uz to, lai tikai

276
00:11:59,640 --> 00:12:02,970
sekundes - jūs sāksiet redzēt
raksts, kas tas ir ieviešanas.

277
00:12:02,970 --> 00:12:04,530
>> Apvienot kārtot, paziņojums, tiek darīts.

278
00:12:04,530 --> 00:12:06,430
Kaudze kārtot, ātri kārtot, apvalks -

279
00:12:06,430 --> 00:12:09,480
tāpēc šķiet, mēs iepazīstināja ar trīs
sliktākajā algoritmi pagājušajā nedēļā.

280
00:12:09,480 --> 00:12:12,960
Bet tas ir labi, ka mēs esam šodien šeit, lai
apskatīt sapludināšanas šķirot, kas ir viens no

281
00:12:12,960 --> 00:12:16,500
jo vieglāk tiem ir aplūkot, pat
lai gan tas, iespējams, būs saliekt jūsu prātā

282
00:12:16,500 --> 00:12:17,490
tikai mazliet.

283
00:12:17,490 --> 00:12:21,130
Šeit mēs varam redzēt, cik daudz
atlases veida sūkā.

284
00:12:21,130 --> 00:12:24,600
>> Bet par Flip pusē, tas ir
ļoti viegli īstenot.

285
00:12:24,600 --> 00:12:28,160
Un varbūt par P Set 3, kas ir viens no
algoritmi izvēlējāties, lai īstenotu

286
00:12:28,160 --> 00:12:28,960
standarta izdevums.

287
00:12:28,960 --> 00:12:30,970
Pilnīgi naudas sodu, pilnīgi pareizi.

288
00:12:30,970 --> 00:12:35,210
>> Bet atkal, jo n kļūst liels, ja jūs
izvēlas īstenot ātrāku algoritmu

289
00:12:35,210 --> 00:12:39,020
patīk apvienot kārtot, izredzes ir lielākas, un
lielāki ieguldījumi, jūsu kods ir tikai

290
00:12:39,020 --> 00:12:39,800
gatavojas palaist ātrāk.

291
00:12:39,800 --> 00:12:41,090
Jūsu mājas lapā ir dodas uz darbu labāk.

292
00:12:41,090 --> 00:12:42,650
Jūsu lietotāji būs laimīgāki.

293
00:12:42,650 --> 00:12:45,280
Un tāpēc ir šie efekti
faktiski dodot

294
00:12:45,280 --> 00:12:47,350
mums daži dziļāk domāja.

295
00:12:47,350 --> 00:12:49,990
>> Tātad, pieņemsim apskatīt to, kas apvienojas
veida ir patiešām visu par.

296
00:12:49,990 --> 00:12:52,992
Cool lieta ir tā, ka apvienot
veida ir tikai to.

297
00:12:52,992 --> 00:12:56,300
Tas ir, atkal, ko mēs esam sauc
pseudocode, pseudocode būtne

298
00:12:56,300 --> 00:12:57,720
Angļu-piemēram, sintakse.

299
00:12:57,720 --> 00:12:59,890
Un vienkāršība ir
veida aizraujošu.

300
00:12:59,890 --> 00:13:02,840
>> Tā par ieejas n elementiem - tā, ka
tikai nozīmē, šeit ir masīvs.

301
00:13:02,840 --> 00:13:04,000
Tas ir ieguvuši n lietas tajā.

302
00:13:04,000 --> 00:13:05,370
Tas ir viss, ko mēs esam sakot tur.

303
00:13:05,370 --> 00:13:07,560
>> Ja n ir mazāks par 2, atgriezties.

304
00:13:07,560 --> 00:13:08,640
Tātad tas ir tikai triviāla lieta.

305
00:13:08,640 --> 00:13:12,580
Ja n ir mazāks par 2, tad protams, tas ir
1 vai 0, un šajā gadījumā lieta

306
00:13:12,580 --> 00:13:14,780
jau ir sakārtoti vai neeksistējošu,
tik vienkārši atgriezties.

307
00:13:14,780 --> 00:13:15,900
Tur neko darīt.

308
00:13:15,900 --> 00:13:18,360
Tātad, tas ir vienkāršs gadījums raut off.

309
00:13:18,360 --> 00:13:20,110
>> Else, mums ir trīs soļus.

310
00:13:20,110 --> 00:13:23,650
Kārtot kreiso pusi no elementiem, kārtot
tiesības puse no elementiem,

311
00:13:23,650 --> 00:13:26,650
un pēc tam apvienot sakārtoti pusītes.

312
00:13:26,650 --> 00:13:29,400
Kas ir interesanti ir tas, ka
Es esmu veida punting, vai ne?

313
00:13:29,400 --> 00:13:32,300
Tur ir sava veida apļveida definīcijas
šo algoritmu.

314
00:13:32,300 --> 00:13:35,986
Kādā ziņā tas ir algoritms ir
definīcija apļveida?

315
00:13:35,986 --> 00:13:37,850
>> Mērķauditorija: [nedzirdama].

316
00:13:37,850 --> 00:13:41,670
>> DAVID Malan: Jā, mans šķirošana algoritms,
divi tās soļiem ir "sava

317
00:13:41,670 --> 00:13:44,640
kaut ko. "Un tā, ka lūdzas
jautājums, labi, ko es esmu gatavojas izmantot

318
00:13:44,640 --> 00:13:46,460
kārtot kreiso pusi
un labajā pusē?

319
00:13:46,460 --> 00:13:49,600
Un skaistums šeit ir tas, ka, lai gan
atkal, tas ir prātā-saliekuma

320
00:13:49,600 --> 00:13:54,030
daļu iespējams, jūs varat izmantot pašu
algoritmu, lai sakārtotu kreiso pusi.

321
00:13:54,030 --> 00:13:54,700
>> Bet pagaidiet minūti.

322
00:13:54,700 --> 00:13:57,070
Kad esat teicis, lai sakārtotu
kreisā puse, kas ir divi

323
00:13:57,070 --> 00:13:58,240
soļi būs nākamais?

324
00:13:58,240 --> 00:14:00,550
Mēs kārtot kreiso pusi
kreiso pusi, un labais

325
00:14:00,550 --> 00:14:01,420
puse no kreisajā pusē.

326
00:14:01,420 --> 00:14:04,430
Sasodīts, kā es varu atrisināt šo divu
pusītes, vai ceturtdaļas, tagad?

327
00:14:04,430 --> 00:14:05,260
>> Bet tas ir OK.

328
00:14:05,260 --> 00:14:07,830
Mums ir šķirošanas algoritmu šeit.

329
00:14:07,830 --> 00:14:10,660
Un, pat ja jūs varētu jāuztraucas
Sākumā tas ir sava veida bezgalīgs

330
00:14:10,660 --> 00:14:12,780
cilpa, tas ir cikls, kas nekad nav
beigsies - tas notiek, lai

331
00:14:12,780 --> 00:14:15,770
beidzas, kad, kas notiek?

332
00:14:15,770 --> 00:14:16,970
Pēc tam, kad n ir mazāks par 2.

333
00:14:16,970 --> 00:14:19,180
Kas galu galā notiks,
jo, ja jūs saglabāt pusi un

334
00:14:19,180 --> 00:14:23,020
uz pusi samazināt uz pusi samazināt šos pusītes, protams,
galu galā jūs gatavojas galu

335
00:14:23,020 --> 00:14:25,350
līdzi tikai 1 vai 0 elementiem.

336
00:14:25,350 --> 00:14:28,500
Un tajā brīdī, šis algoritms
saka, ka jūs esat darīts.

337
00:14:28,500 --> 00:14:31,020
>> Tātad reālā burvju šajā
algoritms, šķiet, ir

338
00:14:31,020 --> 00:14:33,470
ka pēdējais solis, apvienojot.

339
00:14:33,470 --> 00:14:37,190
Šī vienkāršā doma vienkārši apvienojot divas
lietas, tas ir to, kas galu galā notiek

340
00:14:37,190 --> 00:14:40,920
lai ļautu mums, lai sakārtotu masīvu,
teiksim, astoņus elementus.

341
00:14:40,920 --> 00:14:44,410
Tāpēc man ir astoņi vairāk stresa bumbas augšu
šeit, astoņi gabali no papīra, viens un

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

343
00:14:45,500 --> 00:14:46,140
kas man, lai saglabātu.

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

345
00:14:46,960 --> 00:14:48,970
>> DAVID Malan: ja mēs varētu veikt astoņus
brīvprātīgie, un pieņemsim redzēt, ja mēs varam

346
00:14:48,970 --> 00:14:51,430
spēlēt šo out, tā.

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

348
00:14:52,500 --> 00:14:53,565
Datorzinātnes kļūst jautri.

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

350
00:14:54,320 --> 00:14:57,770
Tātad, kā par jums trīs,
Lielākais roku tur.

351
00:14:57,770 --> 00:14:58,580
Četri uz muguras.

352
00:14:58,580 --> 00:15:02,220
Un kā mēs do you
trīs šajā rindā?

353
00:15:02,220 --> 00:15:03,390
Un četri priekšā.

354
00:15:03,390 --> 00:15:04,920
Tātad jūs astoņi, nākt uz augšu.

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

356
00:15:12,060 --> 00:15:13,450
>> DAVID Malan: Es esmu patiešām
nav pārliecināts, kas tas ir.

357
00:15:13,450 --> 00:15:14,810
Vai tas ir stresa bumbas?

358
00:15:14,810 --> 00:15:16,510
Galda lampas?

359
00:15:16,510 --> 00:15:18,650
Materiāls?

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

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

362
00:15:20,160 --> 00:15:21,310
Lai nāk uz augšu.

363
00:15:21,310 --> 00:15:22,310
Kurš gribētu -

364
00:15:22,310 --> 00:15:23,570
glabāt nāk uz augšu.

365
00:15:23,570 --> 00:15:24,240
Let 's redzēt.

366
00:15:24,240 --> 00:15:26,460
Un tas liek jums vietā -

367
00:15:26,460 --> 00:15:27,940
tu esi vienā vietā.

368
00:15:27,940 --> 00:15:28,670
Uh-oh, pagaidiet minūti.

369
00:15:28,670 --> 00:15:30,760
1, 2, 3, 4, 5, 6, 7 - oh, labi.

370
00:15:30,760 --> 00:15:31,310
Labi, mēs esam labi.

371
00:15:31,310 --> 00:15:35,130
Labi, tāpēc ikviens ir vieta,
bet ne uz Google Glass.

372
00:15:35,130 --> 00:15:36,475
Ļaujiet man rindā šos up.

373
00:15:36,475 --> 00:15:37,115
Kāds ir Jūsu vārds?

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
Labi, jums izskatās
geek, ja tas ir OK.

377
00:15:42,000 --> 00:15:44,625
Nu, man arī, es domāju,
tikai brīdi.

378
00:15:44,625 --> 00:15:45,875
Visas tiesības, gaidīšanas režīmā.

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

380
00:15:48,510 --> 00:15:50,950
Mēs esam mēģinājuši nākt klajā ar
lietošanas gadījumu Google Glass, un mēs

381
00:15:50,950 --> 00:15:53,750
domāju, ka būtu jautri, lai tikai darīt
tas, kad cilvēki ir uz skatuves.

382
00:15:53,750 --> 00:15:57,120
Mēs ierakstīt pasaulē
no viņu viedokļa.

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

384
00:15:58,410 --> 00:15:59,830
Nav iespējams, ko Google paredzēti.

385
00:15:59,830 --> 00:16:02,260
Labi, ja jums nav prātā, valkājot
Šī nākamo neveikli minūtes,

386
00:16:02,260 --> 00:16:03,150
tas būtu brīnišķīgi.

387
00:16:03,150 --> 00:16:08,620
>> Labi, tāpēc mēs esam šeit masīvs
elementi, un tas masīvs, kā vienu

388
00:16:08,620 --> 00:16:11,480
papīra gabalus ar šiem ļaudīm "
rokas, pašlaik nešķirotu.

389
00:16:11,480 --> 00:16:12,050
>> MICHELLE: Ak, tas ir tik dīvaini.

390
00:16:12,050 --> 00:16:12,810
>> DAVID Malan: Tas ir diezgan daudz izlases.

391
00:16:12,810 --> 00:16:15,760
Un tikai brīdi, mēs ejam, lai mēģinātu
īstenot apvienot kārtot kopā

392
00:16:15,760 --> 00:16:17,950
un redzēt, kur tas galvenais ieskats ir.

393
00:16:17,950 --> 00:16:21,970
Un triks šeit ar sapludināšanas veida ir
kaut kas, ko mēs neesam pieņemts vēl.

394
00:16:21,970 --> 00:16:24,030
Mums tiešām ir nepieciešams zināms
papildus vieta.

395
00:16:24,030 --> 00:16:26,650
Tātad, kas būs īpaši
interesanti par šo ir tas, ka šie

396
00:16:26,650 --> 00:16:29,270
puiši gatavojas, lai pārvietotos nedaudz
mazliet, jo es esmu gatavojas pieņemt, ka

397
00:16:29,270 --> 00:16:31,880
tur ir papildus masīvs vietas,
teiksim, tieši aiz viņiem.

398
00:16:31,880 --> 00:16:34,570
>> Tātad, ja viņi aiz sava krēsla,
tas ir sekundārais masīvs.

399
00:16:34,570 --> 00:16:36,960
Ja viņi sēž šeit, tas ir
primārā masīvs.

400
00:16:36,960 --> 00:16:40,170
Bet tas ir resurss, kas mums ir
nevar pārvirzīt līdz šim ar burbulis

401
00:16:40,170 --> 00:16:42,040
kārtot, ar atlases veida,
ar ievietošanas veida.

402
00:16:42,040 --> 00:16:44,600
Atsaukt pagājušajā nedēļā, visi tikai
veida iegrozījās vietā.

403
00:16:44,600 --> 00:16:46,840
Viņi neizmantoja nekādas papildu atmiņu.

404
00:16:46,840 --> 00:16:49,310
Mēs veicām telpu cilvēkiem,
pārvietojas cilvēki apkārt.

405
00:16:49,310 --> 00:16:50,580
>> Tātad tas ir galvenais ieskatu, too.

406
00:16:50,580 --> 00:16:53,410
Tur tas ir kompromiss, ka kopumā
datorzinātnes, resursu.

407
00:16:53,410 --> 00:16:55,800
Ja jūs vēlaties, lai paātrinātu kaut ko
piemēram, laiku, jūs gatavojas

408
00:16:55,800 --> 00:16:56,900
ir jāmaksā cenu.

409
00:16:56,900 --> 00:17:00,750
Un viena no tām cenām, ir ļoti bieži
telpa, atmiņas apjomu vai grūti

410
00:17:00,750 --> 00:17:01,700
diska vietas, ka jūs izmantojat.

411
00:17:01,700 --> 00:17:03,640
Vai arī, godīgi sakot, summa
gada programmētājs laika.

412
00:17:03,640 --> 00:17:06,700
Cik daudz laika nepieciešams, jūs, cilvēku,
lai faktiski īstenotu dažas vairāk

413
00:17:06,700 --> 00:17:07,829
sarežģīts algoritms.

414
00:17:07,829 --> 00:17:09,760
Bet šodien, kompromiss
ir laiks un telpa.

415
00:17:09,760 --> 00:17:11,930
>> Tātad, ja jūs puiši varētu tikai turēt uz augšu savu
numurus, lai mēs varam redzēt, ka tu esi

416
00:17:11,930 --> 00:17:15,839
patiešām saskaņojot 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
Tāpēc es esmu gatavojas izmēģināt, lai orķestrēt
lietas, ja jūs guys var tikai

419
00:17:19,520 --> 00:17:21,800
sekot manu svina šeit.

420
00:17:21,800 --> 00:17:26,650
>> Tāpēc es esmu gatavojas īstenot, pirmkārt,
pirmais solis pseudocode, kas ir

421
00:17:26,650 --> 00:17:29,440
par ieejas n elementiem, ja n
mazāk nekā 2, tad atgriezties.

422
00:17:29,440 --> 00:17:31,370
Protams, ka nav
piemērojams, tāpēc mēs virzāmies tālāk.

423
00:17:31,370 --> 00:17:33,340
Tātad šķirot kreiso pusi elementiem.

424
00:17:33,340 --> 00:17:36,220
Tātad tas nozīmē, ka es esmu gatavojas koncentrēties manu
uzmanību tikai brīdi par šo

425
00:17:36,220 --> 00:17:37,310
četri puiši šeit.

426
00:17:37,310 --> 00:17:39,774
Visas tiesības, ko man nākamo darīt?

427
00:17:39,774 --> 00:17:40,570
>> Mērķauditorija: Kārtot kreiso pusi.

428
00:17:40,570 --> 00:17:42,780
>> DAVID Malan: Tāpēc tagad man ir, lai sakārtotu
kreiso pusi no šiem guys.

429
00:17:42,780 --> 00:17:45,580
Jo atkal, uzņemas uz sevi ar
Mērķis ir sakārtot kreiso pusi.

430
00:17:45,580 --> 00:17:46,440
Kā jūs to darīt?

431
00:17:46,440 --> 00:17:49,140
Vienkārši sekojiet instrukcijām, pat
ja mēs darām to vēlreiz.

432
00:17:49,140 --> 00:17:50,160
Tātad šķirot kreiso pusi.

433
00:17:50,160 --> 00:17:52,030
Tagad es esmu šķirošana šie divi puiši.

434
00:17:52,030 --> 00:17:53,563
Kas būs tālāk?

435
00:17:53,563 --> 00:17:54,510
>> Mērķauditorija: Kārtot kreiso pusi.

436
00:17:54,510 --> 00:17:55,460
>> DAVID Malan: kārtot kreiso pusi.

437
00:17:55,460 --> 00:18:00,680
Tāpēc tagad tie, šī vieta šeit,
ir saraksts ar apjomu 1.

438
00:18:00,680 --> 00:18:01,365
Un kāds ir tavs vārds atkal?

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

440
00:18:02,390 --> 00:18:03,690
>> DAVID Malan: Princess Daisy ir šeit.

441
00:18:03,690 --> 00:18:07,470
Un tā viņa jau ir sakārtots, jo
saraksts ir 1 izmēru.

442
00:18:07,470 --> 00:18:09,490
Ko man blakus darīt?

443
00:18:09,490 --> 00:18:13,680
Labi, atpakaļ, jo šis saraksts ir
izmērs 1, kas ir mazāks par 2.

444
00:18:13,680 --> 00:18:14,320
Tad kas ir nākamais solis?

445
00:18:14,320 --> 00:18:17,490
Un tagad jums ir sava veida
backtrack jūsu prātā.

446
00:18:17,490 --> 00:18:19,340
>> Kārtot pareizo pusi, kas ir -

447
00:18:19,340 --> 00:18:19,570
kāds ir tavs vārds?

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
Un tā, ko mēs darām tagad,
mums ir saraksts ar apjomu 1?

451
00:18:23,210 --> 00:18:24,440
>> Mērķauditorija: Atgriešanās.

452
00:18:24,440 --> 00:18:24,760
>> DAVID Malan: uzmanīgi.

453
00:18:24,760 --> 00:18:29,540
Mēs atgriezties pirmais, un tagad trešais
solis - un, ja es veida attēlot to,

454
00:18:29,540 --> 00:18:33,490
aptverot divas vietas tagad, tagad es
ir apvienot šos divus elementus.

455
00:18:33,490 --> 00:18:35,530
Tāpēc tagad, diemžēl, elementi
ir bojātas.

456
00:18:35,530 --> 00:18:39,920
Bet tas ir, ja apvienošanās process
sāk iegūt pārliecinoši.

457
00:18:39,920 --> 00:18:42,410
>> Tātad, ja jūs puiši varētu piecelties, lai tikai
brīdis, es esmu gatavojas nepieciešams, lai jūs, jo

458
00:18:42,410 --> 00:18:44,170
brīdis, lai soli aiz sava krēsla.

459
00:18:44,170 --> 00:18:46,480
Un ja Linda, jo 2 ir
mazāks par 4, kāpēc ne

460
00:18:46,480 --> 00:18:48,130
jūs nākt apkārt vispirms?

461
00:18:48,130 --> 00:18:48,690
Tur uzturēties.

462
00:18:48,690 --> 00:18:50,520
Tātad Linda, jūs nākt apkārt vispirms.

463
00:18:50,520 --> 00:18:53,820
>> Tagad, patiesībā, ja tas ir tikai masīvs
mēs varētu virzīties viņai reālā laikā

464
00:18:53,820 --> 00:18:55,360
no šī krēsla, lai šajā vietā.

465
00:18:55,360 --> 00:18:57,770
Tātad, iedomāties, kas notika dažas konstante
numurs 1 soļiem.

466
00:18:57,770 --> 00:18:58,480
Un tagad -

467
00:18:58,480 --> 00:19:01,490
bet mums ir nepieciešams, lai jums
pirmā vieta šeit.

468
00:19:01,490 --> 00:19:03,930
>> Un tagad, ja jūs varētu nākt apkārt,
, kā arī, mēs ejam, lai

469
00:19:03,930 --> 00:19:06,300
tā sastāv no divām atrašanās vietu.

470
00:19:06,300 --> 00:19:09,120
Un, pat ja tas uzskata, tāpat kā tas ir
ņemot kādu laiku, kas ir jauki, tagad ir

471
00:19:09,120 --> 00:19:14,710
ka kreisā puse no
kreisā puse tagad ir sakārtots.

472
00:19:14,710 --> 00:19:18,010
Tātad, kāds bija nākamais solis, ja mēs tagad
attīt tālāk stāsts?

473
00:19:18,010 --> 00:19:18,980
>> Mērķauditorija: labajā pusē.

474
00:19:18,980 --> 00:19:19,900
>> DAVID Malan: kārtot labo pusi.

475
00:19:19,900 --> 00:19:21,320
Tātad jūs guys to darīt, kā labi.

476
00:19:21,320 --> 00:19:23,510
Tātad, ja jūs varētu piecelties
tikai brīdi?

477
00:19:23,510 --> 00:19:25,192
Un kāds ir tavs vārds?

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
Labi, tāpēc Jess tagad ir pa kreisi
puse no labajā pusē.

481
00:19:29,720 --> 00:19:31,400
Un tāpēc viņa ir saraksts ar apjomu 1.

482
00:19:31,400 --> 00:19:32,380
Viņa acīmredzot sakārtoti.

483
00:19:32,380 --> 00:19:33,070
Un Jūsu vārds atkal?

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

485
00:19:33,630 --> 00:19:35,340
>> DAVID Malan: Michelle ir acīmredzami
sarakstu apjomu 1.

486
00:19:35,340 --> 00:19:36,050
Viņa jau ir sakārtoti.

487
00:19:36,050 --> 00:19:38,690
Tāpēc tagad burvju notiek,
apvienošanās process.

488
00:19:38,690 --> 00:19:39,790
Tātad, kas notiek, lai brauc, tas pirmais?

489
00:19:39,790 --> 00:19:41,560
Acīmredzot Michelle.

490
00:19:41,560 --> 00:19:43,280
Tātad, ja jūs varētu nākt apkārt atpakaļ.

491
00:19:43,280 --> 00:19:47,090
Telpa mums ir pieejams par viņas tagad
tieši aiz šī krēsla šeit.

492
00:19:47,090 --> 00:19:51,580
Un tagad, ja jūs varētu nākt atpakaļ, kā arī,
mums tagad ir, lai būtu skaidrs, divi

493
00:19:51,580 --> 00:19:53,810
pusītes, katrs no 2 izmēru -

494
00:19:53,810 --> 00:19:57,090
un tikai tēlojuma dēļ, ja
varētu mazliet telpā -

495
00:19:57,090 --> 00:19:59,780
viens pa kreisi puse šeit, viens
labajā pusē šeit.

496
00:19:59,780 --> 00:20:01,160
>> Attīt tālāk stāstā.

497
00:20:01,160 --> 00:20:02,270
Kas solis ir nākamais?

498
00:20:02,270 --> 00:20:03,030
>> Mērķauditorija: Apvienot.

499
00:20:03,030 --> 00:20:04,160
>> DAVID Malan: Tāpēc tagad mums ir apvienot.

500
00:20:04,160 --> 00:20:07,490
Tātad Labi, tāpēc tagad, par laimi, mēs
tikko atbrīvojušies četri krēsli.

501
00:20:07,490 --> 00:20:11,480
Tāpēc mēs esam, ko izmanto divreiz tik daudz atmiņu, bet
mēs varam dot flip-flopping starp

502
00:20:11,480 --> 00:20:12,330
divi masīvi.

503
00:20:12,330 --> 00:20:14,190
Tātad, cik daudz ir jānāk vispirms?

504
00:20:14,190 --> 00:20:14,850
Tātad Michelle, protams.

505
00:20:14,850 --> 00:20:16,680
Lai nāk apkārt un veikt
jūsu vieta šeit.

506
00:20:16,680 --> 00:20:19,120
Un tad skaitlis 2 ir acīmredzami
Nākamais, lai jūs nākt šeit.

507
00:20:19,120 --> 00:20:21,520
4 numurs, numurs 6.

508
00:20:21,520 --> 00:20:23,390
Un atkal, lai gan tur ir
Mazliet pastaigas iesaistīts,

509
00:20:23,390 --> 00:20:26,010
tiešām, tas varētu notikt uzreiz,
pārceļot vienu -

510
00:20:26,010 --> 00:20:26,880
Labi, labi spēlēja.

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

512
00:20:28,350 --> 00:20:29,680
>> DAVID Malan: Un tagad mēs esam
diezgan labā formā.

513
00:20:29,680 --> 00:20:34,910
Kreiso pusi no visa
ieeja tagad ir sakārtots.

514
00:20:34,910 --> 00:20:37,370
Labi, tāpēc šie puiši bija
priekšrocība manā -

515
00:20:37,370 --> 00:20:40,340
kā to darīja galu galā visas meitenes uz
pa kreisi un visi par tiesībām zēni?

516
00:20:40,340 --> 00:20:42,450
>> Labi, tāpēc puiši 'savukārt tagad.

517
00:20:42,450 --> 00:20:44,680
Tāpēc es ne staigāt jums caur
šie pasākumi.

518
00:20:44,680 --> 00:20:46,550
Redzēsim, vai mēs varam atkārtoti
pats pseudocode.

519
00:20:46,550 --> 00:20:50,050
Ja jūs vēlaties, lai iet uz priekšu un piecelties,
un jūs guys, ļaujiet man sniegt jums mic.

520
00:20:50,050 --> 00:20:52,990
Skat, ja jūs nevar atkārtot to, ko
mēs tikko izdarījām šeit

521
00:20:52,990 --> 00:20:53,880
otru galu no saraksta.

522
00:20:53,880 --> 00:20:59,530
Kas nepieciešams izteikties vispirms;
balstoties uz algoritmu,?

523
00:20:59,530 --> 00:21:03,210
Tātad, paskaidrot, ko jūs darāt, pirms
veicat jebkādas kāju kustības.

524
00:21:03,210 --> 00:21:05,930
>> SPEAKER 1: Nu labi, tāpēc, ka
Es esmu kreisajā pusē

525
00:21:05,930 --> 00:21:07,790
kreiso pusi, es atgriezties.

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

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

528
00:21:09,250 --> 00:21:10,350
>> SPEAKER 1: Un tad -

529
00:21:10,350 --> 00:21:11,800
>> DAVID Malan: Kam
mic iet uz nākamo?

530
00:21:11,800 --> 00:21:12,920
>> SPEAKER 1: Nākamais numurs.

531
00:21:12,920 --> 00:21:14,720
>> SPEAKER 2: Tāpēc es esmu labajā pusē
no kreisajā pusē

532
00:21:14,720 --> 00:21:17,830
kreiso pusi, un es atgriezties.

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

534
00:21:18,050 --> 00:21:18,550
Jūs atgrieztos.

535
00:21:18,550 --> 00:21:21,855
Tātad, tagad, kas ir nākamais pēc jums abiem?

536
00:21:21,855 --> 00:21:23,740
>> SPEAKER 2: Mēs gribam redzēt, kas ir mazāks.

537
00:21:23,740 --> 00:21:24,200
>> DAVID Malan: Tieši tā.

538
00:21:24,200 --> 00:21:24,940
Mēs vēlamies apvienot.

539
00:21:24,940 --> 00:21:27,590
Kosmosa mēs spēsim izmantot, lai apvienot
tevi, pat ja viņi

540
00:21:27,590 --> 00:21:30,250
protams sakārtoti jau mēs ejam
ievērot tādu pašu algoritmu.

541
00:21:30,250 --> 00:21:31,560
Tātad, kas iet atpakaļ pirmo reizi?

542
00:21:31,560 --> 00:21:35,720
Tātad, 3, 7 un pēc tam.

543
00:21:35,720 --> 00:21:38,570
Un tagad mic iet
lai šie puiši, OK?

544
00:21:38,570 --> 00:21:43,590
>> SPEAKER 3: Tāpēc es esmu labajā pusē no
kreisā puse, un mans n ir mazāks nekā

545
00:21:43,590 --> 00:21:45,048
1, tāpēc es esmu tikai gatavojas iet -

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

547
00:21:46,380 --> 00:21:49,450
>> SPEAKER 4: Es esmu labajā pusē no
labajā pusē no labās puses, un es esmu

548
00:21:49,450 --> 00:21:51,740
arī viens cilvēks, tāpēc es esmu
gatavojas atgriezties.

549
00:21:51,740 --> 00:21:52,990
Tāpēc tagad mums apvienoties.

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

551
00:21:55,140 --> 00:21:56,150
>> SPEAKER 3: Tātad mēs ejam atpakaļ.

552
00:21:56,150 --> 00:21:57,160
>> DAVID Malan: Tātad jūs doties uz muguras.

553
00:21:57,160 --> 00:21:59,200
Tātad 5 iet pirmais, tad 8.

554
00:21:59,200 --> 00:22:01,240
Un tagad audience, kas ir
solis mums ir tagad attīt

555
00:22:01,240 --> 00:22:02,200
atpakaļ uz mūsu prātos?

556
00:22:02,200 --> 00:22:02,940
>> Mērķauditorija: Apvienot.

557
00:22:02,940 --> 00:22:07,270
>> DAVID Malan: apvienošana kreisajā pusē un pa labi
puse no sākotnējā kreisajā pusē.

558
00:22:07,270 --> 00:22:08,840
Tātad tagad -

559
00:22:08,840 --> 00:22:10,520
un tikai, lai tas skaidri,
padarīt mazliet vietas

560
00:22:10,520 --> 00:22:11,690
Starp jums divi puiši.

561
00:22:11,690 --> 00:22:13,800
Tāpēc tagad, ka ir divi saraksti,
pa kreisi un pa labi.

562
00:22:13,800 --> 00:22:18,320
Tātad, kā mēs tagad apvienot jūs guys uz
priekšējo sēdekļu rinda atkal?

563
00:22:18,320 --> 00:22:19,600
>> 3 iet pirmais.

564
00:22:19,600 --> 00:22:20,850
Tad 5, protams.

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

566
00:22:23,110 --> 00:22:27,330
Tad 7, un tagad 8.

567
00:22:27,330 --> 00:22:28,710
Labi, un tagad mēs esam?

568
00:22:28,710 --> 00:22:29,650
>> Mērķauditorija: Nav darīts.

569
00:22:29,650 --> 00:22:32,440
>> DAVID Malan: Nav darīts, jo
protams, tur ir viens solis paliek.

570
00:22:32,440 --> 00:22:35,720
Bet atkal, iemesls, kāpēc es esmu, izmantojot šo
žargons, piemēram, "savā prātā, attīt atpakaļ,"

571
00:22:35,720 --> 00:22:37,160
tas ir tāpēc, ka tas ir patiešām
kas notiek.

572
00:22:37,160 --> 00:22:39,610
Mēs ejam cauri visiem šiem soļiem,
bet mēs esam sava veida pauzes

573
00:22:39,610 --> 00:22:42,480
brīdis, niršana dziļāk
algoritms, pauzes uz brīdi,

574
00:22:42,480 --> 00:22:45,840
niršanas dziļāk algoritmu, un
Tagad mums ir sava veida attīšanas mūsu

575
00:22:45,840 --> 00:22:49,430
prāts un atsaukt visus no šiem slāņiem
ka mēs esam sava veida aizturēts.

576
00:22:49,430 --> 00:22:51,790
>> Tāpēc tagad mums ir divi saraksti 4 izmēru.

577
00:22:51,790 --> 00:22:54,790
Ja jūs puiši varētu piecelties pēdējo reizi
un padarīt daudz vietas šeit

578
00:22:54,790 --> 00:22:57,230
būtu skaidrs, ka tas ir pa kreisi
puse no oriģināla,

579
00:22:57,230 --> 00:22:58,620
labajā pusē no oriģināla.

580
00:22:58,620 --> 00:23:01,060
Kurš ir pirmais skaitlis, kas mums
nepieciešams, lai vilktu uz muguras?

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

582
00:23:01,870 --> 00:23:03,230
>> Tātad mēs ieliekam Michelle šeit.

583
00:23:03,230 --> 00:23:05,080
Un kas ir numurs 2?

584
00:23:05,080 --> 00:23:06,440
Numurs 2 nāk atpakaļ, kā arī.

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

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

587
00:23:08,510 --> 00:23:16,570
Skaits 4, skaits 5, skaits 6,
skaits 7, un numurs 8.

588
00:23:16,570 --> 00:23:18,850
>> Labi, tāpēc jutos kā daudz
pakāpienu, protams.

589
00:23:18,850 --> 00:23:22,390
Bet tagad pieņemsim redzēt, ja mēs nevaram apstiprināt
veida intuitīvi, ka šis

590
00:23:22,390 --> 00:23:26,190
algoritms būtiski, jo īpaši attiecībā
n kļūst patiešām liels, kā mēs esam redzējuši

591
00:23:26,190 --> 00:23:29,170
ar animācijas, ir
būtiski ātrāk.

592
00:23:29,170 --> 00:23:33,400
Tāpēc es saņemt šo algoritmu, kas sliktākajā
lietu un pat labākajā gadījumā,

593
00:23:33,400 --> 00:23:36,160
ir liela O no n reizes log n.

594
00:23:36,160 --> 00:23:39,160
Tas nozīmē, ka tur ir dažas no šis aspekts
algoritms, kas notiek n pasākumus, bet

595
00:23:39,160 --> 00:23:43,110
tur ir vēl viens aspekts, kaut kur
ka atkārtojuma, ka looping, ka

596
00:23:43,110 --> 00:23:44,410
ņem log n pasākumus.

597
00:23:44,410 --> 00:23:49,154
Vai mēs varam nodot mūsu pirkstu uz to, kas tiem
divi skaitļi ir domāta?

598
00:23:49,154 --> 00:23:51,320
Nu, ja -

599
00:23:51,320 --> 00:23:54,160
where'd mic iet?

600
00:23:54,160 --> 00:23:58,660
>> SPEAKER 1: Vai log n ir
sadalīšana mūs divās daļās -

601
00:23:58,660 --> 00:23:59,630
dalot ar divi, būtībā.

602
00:23:59,630 --> 00:24:00,120
>> DAVID Malan: Tieši tā.

603
00:24:00,120 --> 00:24:03,000
Katru reizi, kad mēs redzam kādu algoritmu tādējādi
tālu, tur ir bijis šis modelis

604
00:24:03,000 --> 00:24:04,200
dalot, dalot, dalot.

605
00:24:04,200 --> 00:24:05,700
Un tas parasti ir jāsamazina
uz kaut ko, kas ir

606
00:24:05,700 --> 00:24:07,100
logaritmiska, log bāze 2.

607
00:24:07,100 --> 00:24:10,180
Bet tas tiešām varētu būt kaut kas,
bet pieteikties bāze 2.

608
00:24:10,180 --> 00:24:11,330
>> Tagad to, ko par n?

609
00:24:11,330 --> 00:24:14,550
Es redzu, ka mēs veida sadalīta jums
puiši - sadalīta tevi, sadalīta jums,

610
00:24:14,550 --> 00:24:15,910
sadalīta tevi, sadalīta jums.

611
00:24:15,910 --> 00:24:18,760
Kur gals nāk no?

612
00:24:18,760 --> 00:24:19,810
>> Tātad, tas ir apvienošanās.

613
00:24:19,810 --> 00:24:20,610
Tāpēc, ka domā par to.

614
00:24:20,610 --> 00:24:25,420
Kad jūs apvienot astoņi cilvēki kopā,
, saskaņā ar kuru puse no tiem ir noteikts četru

615
00:24:25,420 --> 00:24:27,770
un otra puse ir vēl viens
komplekts no četriem, kā jūs iet

616
00:24:27,770 --> 00:24:28,820
par darot apvienojas?

617
00:24:28,820 --> 00:24:30,830
Nu, jūs puiši to darīja
diezgan intuitīvi.

618
00:24:30,830 --> 00:24:34,140
>> Bet, ja es tā vietā to darīja nedaudz vairāk
metodiski, es varētu būt norādīja uz

619
00:24:34,140 --> 00:24:38,090
kreisās malas persona pirmo ar manu kreiso
No otras puses, norādīja uz kreisās malas personas

620
00:24:38,090 --> 00:24:42,080
Šī puse ar savu labo roku, un
tikai pēc tam gāja cauri

621
00:24:42,080 --> 00:24:46,990
sarakstu, norādot uz mazāko elementu
katru reizi, pārvietojas manu pirkstu pāri un

622
00:24:46,990 --> 00:24:48,970
vairāk kā nepieciešams visā sarakstā.

623
00:24:48,970 --> 00:24:51,890
Bet kas ir galvenais par šo apvienošanu
Process ir es esmu Salīdzinot šos pārus

624
00:24:51,890 --> 00:24:53,460
no elementiem.

625
00:24:53,460 --> 00:24:57,270
No labajā pusē un no kreisās
pusi, es esmu nekad vienreiz atteikšanās.

626
00:24:57,270 --> 00:25:00,570
>> Tātad sapludināšanas pati, ņemot
ne vairāk nekā N soļus.

627
00:25:00,570 --> 00:25:03,250
Un cik reizes bija man
to darīt apvienojas?

628
00:25:03,250 --> 00:25:07,150
Nu, ne vairāk kā n, un mēs tikko
redzēja, ka ar galīgo sapludināšanu.

629
00:25:07,150 --> 00:25:13,120
Un tā, ja jūs kaut ko darīt, kas ņem
log n soļus n reizes, vai otrādi,

630
00:25:13,120 --> 00:25:15,210
tas notiek, lai dotu mums n reizes log n.

631
00:25:15,210 --> 00:25:16,310
>> Un kāpēc tas ir labāks?

632
00:25:16,310 --> 00:25:19,600
Nu, ja mēs jau zinām, ka žurnālu
n ir labāk nekā n - labi?

633
00:25:19,600 --> 00:25:22,590
Mēs redzējām bināro meklēšanu, tālruņa grāmatu
Piemēram, log n noteikti bija

634
00:25:22,590 --> 00:25:23,760
labāk nekā lineāra.

635
00:25:23,760 --> 00:25:28,420
Tātad, kas nozīmē, n reizes log n ir
noteikti labāk nekā n reizes otru

636
00:25:28,420 --> 00:25:30,390
n, AKA n kvadrātā.

637
00:25:30,390 --> 00:25:32,400
Un tas, ko mēs galu galā jūtas.

638
00:25:32,400 --> 00:25:34,928
>> Tik liels kārta aplausi, ja
mēs varētu, šiem puišiem.

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

640
00:25:38,920 --> 00:25:41,550
>> DAVID Malan: Un jūsu atvadu dāvanas -
Jūs varat saglabāt numurus,

641
00:25:41,550 --> 00:25:44,010
ja jūs vēlētos.

642
00:25:44,010 --> 00:25:45,620
Un jūsu šķiršanās dāvanu, kā parasti.

643
00:25:45,620 --> 00:25:47,290
Ak, un mēs nosūtīsim jums
kadrus, Michelle.

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

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

646
00:25:49,250 --> 00:25:50,400
Palīdzēt sevi stresa bumbu.

647
00:25:50,400 --> 00:25:54,110
>> Un ļaujiet man uzvilkt, pa to laiku,
mūsu draugs Rob Bowden piedāvāt

648
00:25:54,110 --> 00:25:59,520
nedaudz atšķirīgs skatījums uz to,
jo jūs varat domāt par šiem

649
00:25:59,520 --> 00:26:01,280
pasākumi notiek nedaudz
citādā veidā.

650
00:26:01,280 --> 00:26:04,750
Faktiski, set-up par to, kas Rob ir par
lai parādītu mums, tiek pieņemts, ka mēs esam

651
00:26:04,750 --> 00:26:09,030
jau izdarīts dalot up
liels saraksts astoņās mazos sarakstos,

652
00:26:09,030 --> 00:26:10,570
katrs no 1 izmēru.

653
00:26:10,570 --> 00:26:13,350
>> Tātad, mēs esam mainās pseudocode
mazliet tikai, lai kārtotu, kas nokļūt pie

654
00:26:13,350 --> 00:26:15,320
galvenā ideja par to, kā apvienot darbu.

655
00:26:15,320 --> 00:26:17,600
Bet darba laiks par to, ko
viņš gatavojas darīt, ir vēl

656
00:26:17,600 --> 00:26:19,110
būs tāds pats.

657
00:26:19,110 --> 00:26:23,540
Un atkal, set-up, šeit ir tas, ka viņš ir
sākās ar astoņiem sarakstiem apjomu 1.

658
00:26:23,540 --> 00:26:27,730
Tātad jūs esat neatbildētos daļa, kur viņš ir
faktiski izdarīts log n, log n, log n

659
00:26:27,730 --> 00:26:31,205
izdalot no ieejas.

660
00:26:31,205 --> 00:26:32,120
>> [VIDEO PLAYBACK]

661
00:26:32,120 --> 00:26:33,615
>> -Tas ir tas par vienu soli.

662
00:26:33,615 --> 00:26:38,270
Par soli diviem, atkārtoti
apvienot pārus sarakstos.

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

664
00:26:39,210 --> 00:26:41,270
Tikai audio nāk
no mana datora.

665
00:26:41,270 --> 00:26:42,520
Mēģināsim to atkal.

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

667
00:26:45,330 --> 00:26:48,310
>> -Tikai patvaļīgi izvēlēties, kuras -
tagad mums ir četri saraksti.

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

669
00:26:51,590 --> 00:26:52,120
Uzziniet pirms tam.

670
00:26:52,120 --> 00:26:53,040
>> DAVID Malan: Tur mēs ejam.

671
00:26:53,040 --> 00:27:00,510
>> -Apvienošana 108 un 15, mēs galu
up ar sarakstu 15, 108.

672
00:27:00,510 --> 00:27:07,170
Apvienojas 50 un 4, mēs
galu galā ar 4, 50.

673
00:27:07,170 --> 00:27:12,990
Apvienojas 8 un 42, mēs
galu galā ar 8, 42.

674
00:27:12,990 --> 00:27:19,970
Un apvienojot 23 un 16, mēs
galu galā ar 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Tagad visi mūsu saraksti ir 2 izmēru.

676
00:27:23,270 --> 00:27:26,690
Ievērojiet, ka katram
četri saraksti ir sakārtoti.

677
00:27:26,690 --> 00:27:29,450
Tātad, mēs varam sākt apvienojas
pāru sarakstu vēlreiz.

678
00:27:29,450 --> 00:27:38,420
Apvienojas 15 un 108 un 4 un 50, mēs
vispirms veic 4, tad 15, tad

679
00:27:38,420 --> 00:27:41,500
50, pēc tam 108.

680
00:27:41,500 --> 00:27:50,610
Apvienojas, 8, 42 un 16, 23, mēs vispirms veikt
8, tad 16, tad 23,

681
00:27:50,610 --> 00:27:52,700
pēc tam 42.

682
00:27:52,700 --> 00:27:57,600
>> Tāpēc tagad mums ir tikai divi saraksti izmēra
4, katrs no kuriem ir sakārtots.

683
00:27:57,600 --> 00:28:01,170
Tāpēc tagad mums apvienot šos divus sarakstus.

684
00:28:01,170 --> 00:28:11,835
Pirmkārt, mēs ņemam 4, tad mēs
8, tad mēs to 15, tad 16, tad

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

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

687
00:28:19,872 --> 00:28:23,430
>> DAVID Malan: Atkal, paziņojums, viņš nekad
pieskārās doto tasi vairāk nekā vienu reizi

688
00:28:23,430 --> 00:28:24,860
Pēc virzās ārpus tās.

689
00:28:24,860 --> 00:28:26,200
Tāpēc viņš nekad atkārtot.

690
00:28:26,200 --> 00:28:29,850
Tāpēc viņš vienmēr virzās uz sāniem,
un tas, kur mēs saņēmām mūsu n.

691
00:28:29,850 --> 00:28:33,290
>> Kāpēc ne man uzvilkt vienu animāciju
ka mēs redzējām agrāk, bet šoreiz

692
00:28:33,290 --> 00:28:35,110
koncentrējoties tikai sapludināšanas kārtošanas.

693
00:28:35,110 --> 00:28:38,030
Ļaujiet man iet uz priekšu un tuvinātu
kas par šo šeit.

694
00:28:38,030 --> 00:28:42,530
Vispirms ļaujiet man izvēlēties izlases ievadi,
pārspīlēt to, un jūs varat kārtot no redzēt

695
00:28:42,530 --> 00:28:46,600
ko mēs ņēmām par pašsaprotamu, agrāk,
apvienot veida ir faktiski dara.

696
00:28:46,600 --> 00:28:50,330
>> Tātad ievēroju, ka jūs saņemtu šos pusītes vai
šie ceturtdaļas vai tie astotdaļas

697
00:28:50,330 --> 00:28:53,140
problēma, ka visi pēkšņi
sāk veikt labu formu.

698
00:28:53,140 --> 00:28:57,070
Un tad beidzot, jūs redzat
pašām beigām, ka bam,

699
00:28:57,070 --> 00:28:58,860
viss ir apvienots kopā.

700
00:28:58,860 --> 00:29:01,690
>> Tātad šie ir tikai trīs dažādi
uzņemas to pašu ideju.

701
00:29:01,690 --> 00:29:05,980
Bet galvenais ieskatu, tāpat kā plaisa
un iekarot jau pirmajā klasē,

702
00:29:05,980 --> 00:29:10,640
bija tas, ka mēs nolēmām kaut kā sadalīt
problēma par kaut ko lielu, stājās

703
00:29:10,640 --> 00:29:14,760
kaut veida identisks garā,
bet mazākas un mazākas un mazākas

704
00:29:14,760 --> 00:29:15,660
un mazākas.

705
00:29:15,660 --> 00:29:18,420
>> Tagad cita jautri veids, kā sakārtot of domāt
par šiem, pat ja tas nav

706
00:29:18,420 --> 00:29:20,520
gatavojas sniegt jums pašu intuitīvi
izpratne, ir

707
00:29:20,520 --> 00:29:21,640
šādas animācija.

708
00:29:21,640 --> 00:29:25,400
Tātad šis ir video kāds salikt kopā
kas saistīti dažādi

709
00:29:25,400 --> 00:29:29,970
skaņas ar dažādām darbībām, lai
ievietošanas kārtot, lai sapludināšanas kārtot, un

710
00:29:29,970 --> 00:29:31,150
par pāris citiem.

711
00:29:31,150 --> 00:29:32,330
Tātad brīdī, es esmu gatavojas hit Atskaņot.

712
00:29:32,330 --> 00:29:33,600
Tas ir par minūti garš.

713
00:29:33,600 --> 00:29:37,410
Un, pat ja jūs varat redzēt
modeļi notiek, šoreiz jūs varat

714
00:29:37,410 --> 00:29:41,420
arī dzirdēt, kā šie algoritmi
veicot atšķirīgi un ar

715
00:29:41,420 --> 00:29:43,950
nedaudz atšķirīgus.

716
00:29:43,950 --> 00:29:45,830
>> Tas ir ievietošanas veida.

717
00:29:45,830 --> 00:29:50,400
>> [TONES SPēLES]

718
00:29:50,400 --> 00:29:52,400
>> DAVID Malan: Tas atkal mēģina
ievietot katrs elements

719
00:29:52,400 --> 00:29:52,900
vērā, ja tā pieder.

720
00:29:52,900 --> 00:29:54,628
Tas ir burbulis veida.

721
00:29:54,628 --> 00:30:10,097
>> [TONES SPēLES]

722
00:30:10,097 --> 00:30:13,630
>> DAVID Malan: Un jūs varat kārtot ar jūtas
cik salīdzinoši maz darba, ka tas dara

723
00:30:13,630 --> 00:30:15,834
uz katra soļa.

724
00:30:15,834 --> 00:30:20,470
Tas ir tas, ko garlaicības izklausās.

725
00:30:20,470 --> 00:30:21,472
>> [TONES SPēLES]

726
00:30:21,472 --> 00:30:25,222
>> DAVID Malan: Šī ir izvēle kārtot,
kur mēs izvēlētos elementu, ko mēs gribam, ko

727
00:30:25,222 --> 00:30:28,845
iet cauri atkal un atkal, un atkal
un nodot to sākumā.

728
00:30:28,845 --> 00:30:37,674
>> [TONES SPēLES]

729
00:30:37,674 --> 00:30:43,970
>> DAVID Malan: Tas ir apvienot veida, kas
Jūs tiešām var sākt justies.

730
00:30:43,970 --> 00:30:51,810
>> [TONES SPēLES]

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

732
00:30:54,770 --> 00:30:58,395
>> DAVID Malan: Kaut ko sauc rūķis
kārtot, ko mēs neesam paskatījās.

733
00:30:58,395 --> 00:31:13,630
>> [TONES SPēLES]

734
00:31:13,630 --> 00:31:17,910
>> DAVID Malan: Tātad, ļaujiet man redzēt, tagad,
apjucis kā jūs cerams, jau pēc

735
00:31:17,910 --> 00:31:21,110
mūzika, ja es varētu paslīdēt nedaudz
mazliet math šeit.

736
00:31:21,110 --> 00:31:24,850
Tātad tur ir Ceturtais veids, ka mēs varam
domāt par to, ko nozīmē šie

737
00:31:24,850 --> 00:31:29,210
funkcijas, ir ātrāk, nekā tie,
ka mēs esam redzējuši iepriekš.

738
00:31:29,210 --> 00:31:32,470
Un, ja jūs nāk pie kursu no
matemātikas fona, jūs

739
00:31:32,470 --> 00:31:36,030
zina, varbūt jau ka tu
var iepļaukāt termiņu par šo tehniku ​​-

740
00:31:36,030 --> 00:31:40,400
proti rekursijas, funkcija
ka kaut sauc sevi.

741
00:31:40,400 --> 00:31:44,780
>> Un atkal, atgādinām, ka sapludināšanas veida
pseudocode bija rekursīvs tādā ziņā,

742
00:31:44,780 --> 00:31:48,460
ka viens no sapludināšanas kārtot s soļiem
bija zvanīt veida -

743
00:31:48,460 --> 00:31:49,740
kas ir, pats par sevi.

744
00:31:49,740 --> 00:31:52,480
Bet par laimi, jo mēs tur
zvana veida, vai apvienot kārtot,

745
00:31:52,480 --> 00:31:55,880
konkrēti, uz mazākas un mazākas
un mazāku sarakstu, mēs galu galā

746
00:31:55,880 --> 00:32:00,005
dibenu, pateicoties to, ko mēs saucam
bāzes scenārijs, iekodēts lieta, ka

747
00:32:00,005 --> 00:32:04,270
teica, ja saraksts ir neliels, mazāk nekā 2
šajā gadījumā, tikai atpakaļ nekavējoties.

748
00:32:04,270 --> 00:32:07,550
Ja mums nebūtu šo īpašo gadījumu
algoritms nekad jākrītas,

749
00:32:07,550 --> 00:32:11,010
un jūs tiešām nokļūt
bezgalīga cilpa patiesi uz visiem laikiem.

750
00:32:11,010 --> 00:32:14,330
>> Bet pieņemsim, ka mēs vēlējāmies tagad nodot
daži par šo numuru, atkal, izmantojot n

751
00:32:14,330 --> 00:32:15,660
kā lielums ievadi.

752
00:32:15,660 --> 00:32:18,680
Un es gribēju jautāt jums, kas ir
kopējais laiks iesaistīts

753
00:32:18,680 --> 00:32:19,800
darbojas sapludināšanas kārtot?

754
00:32:19,800 --> 00:32:22,960
Vai, plašākā nozīmē, kas ir
izmaksas par to laiku?

755
00:32:22,960 --> 00:32:24,730
>> Nu tas ir diezgan viegli noteikt, ka.

756
00:32:24,730 --> 00:32:29,010
Ja n ir mazāks par 2, laiks iesaistīts
šķirošanas n elementus,

757
00:32:29,010 --> 00:32:30,480
kur n ir 2, ir 0.

758
00:32:30,480 --> 00:32:31,410
Tāpēc, ka mēs vienkārši atgriezties.

759
00:32:31,410 --> 00:32:32,510
Nav darāmā.

760
00:32:32,510 --> 00:32:35,660
Tagad varbūt, varbūt tas ir viens solis vai divas
soļi, lai noskaidrotu apjomu

761
00:32:35,660 --> 00:32:38,420
strādāt, bet tas ir pietiekami tuvu 0, ka
Es esmu tikai gatavojas teikt darbs nav

762
00:32:38,420 --> 00:32:40,940
nepieciešams, ja saraksts ir tik mazs
, kas neinteresantas.

763
00:32:40,940 --> 00:32:42,580
>> Bet šī lieta ir interesanta.

764
00:32:42,580 --> 00:32:47,320
Rekursīvas gadījums bija filiāle
pseudocode kas teica cits, kārtot

765
00:32:47,320 --> 00:32:52,000
kreiso pusi, šķirot tiesības
pusi, apvienot abas pusītes.

766
00:32:52,000 --> 00:32:55,530
Tagad, kāpēc šī izteiksme
pārstāv ka izdevumi?

767
00:32:55,530 --> 00:32:58,690
Nu, T n tikai nozīmē,
laiks, lai sakārtotu n elementiem.

768
00:32:58,690 --> 00:33:03,070
Un pēc tam uz labajā pusē
vienādības zīme tur, no n T dala

769
00:33:03,070 --> 00:33:06,600
ar 2 atsaucas uz izmaksām, ko?

770
00:33:06,600 --> 00:33:07,570
Šķirošana kreiso pusi.

771
00:33:07,570 --> 00:33:10,990
Otru n T dalīts ar 2 ir
iespējams, atsaucoties uz izmaksām

772
00:33:10,990 --> 00:33:12,390
šķirot labo pusi.

773
00:33:12,390 --> 00:33:14,590
>> Un pēc tam, kā arī n?

774
00:33:14,590 --> 00:33:15,420
Vai apvienojas.

775
00:33:15,420 --> 00:33:19,120
Jo, ja jums ir divi saraksti, kas ir viens no
izmēru vairāk nekā 2 n un citu lieluma n

776
00:33:19,120 --> 00:33:22,580
vairāk nekā 2, jums ir būtībā pieskarties
katram no šiem elementiem, tāpat kā Rob

777
00:33:22,580 --> 00:33:24,990
pieskārās katram bļodiņu, un tikai
kā mēs norādīja uz katru no

778
00:33:24,990 --> 00:33:26,310
brīvprātīgie uz skatuves.

779
00:33:26,310 --> 00:33:28,790
Tātad n ir rēķina apvienošanu.

780
00:33:28,790 --> 00:33:31,780
>> Tagad diemžēl, šī formula
ir arī pati rekursīvs.

781
00:33:31,780 --> 00:33:36,390
Tātad, ja uzdeva jautājumu, ja n ir, teiksim,
16, ja tur ir 16 cilvēki uz skatuves

782
00:33:36,390 --> 00:33:40,670
vai 16 kausi video, cik kopā
soļi tas veic, lai sakārtotu tos

783
00:33:40,670 --> 00:33:41,550
ar sapludināšanas veida?

784
00:33:41,550 --> 00:33:45,790
Tas tiešām nav skaidra risinājuma,
jo tagad jums ir sava veida

785
00:33:45,790 --> 00:33:48,500
rekursīvi atbildēt uz šo formulu.

786
00:33:48,500 --> 00:33:51,190
>> Bet tas ir OK, tāpēc ļaujiet man piedāvāt
ka mēs šādi.

787
00:33:51,190 --> 00:33:56,670
Laiks iesaistīties, lai sakārtotu 16 cilvēkiem vai
16 kausi būs pārstāvētas

788
00:33:56,670 --> 00:33:58,020
parasti kā T gada 16.

789
00:33:58,020 --> 00:34:01,400
Bet tas ir vienāds, saskaņā ar mūsu
Iepriekšējā formula, 2 reizes summu

790
00:34:01,400 --> 00:34:04,780
laiku, kas nepieciešams, lai kārtotu
8 glāzes plus 16.

791
00:34:04,780 --> 00:34:08,590
Un atkal, 16 plus ir laiks apvienoties,
un divas reizes T no 8 ir

792
00:34:08,590 --> 00:34:10,790
laiks, lai sakārtotu kreiso pusi un labo pusi.

793
00:34:10,790 --> 00:34:11,989
>> Bet atkal, tas nav pietiekami.

794
00:34:11,989 --> 00:34:13,210
Mums ir ienirt dziļāk.

795
00:34:13,210 --> 00:34:16,409
Tas nozīmē, ka mums ir jāatbild
Jautājums, kas ir T gada 8?

796
00:34:16,409 --> 00:34:19,610
Nu T gada 8 ir tikai 2
reizes T no 4 plus 8.

797
00:34:19,610 --> 00:34:20,520
Nu, kas ir T 4?

798
00:34:20,520 --> 00:34:23,780
T no 4 ir tikai 2 reizes T no 2 plus 4.

799
00:34:23,780 --> 00:34:25,489
Nu, kas ir T 2?

800
00:34:25,489 --> 00:34:29,030
T 2 ir tikai 2 reizes T 1 plus 2.

801
00:34:29,030 --> 00:34:31,940
>> Un atkal mēs esam veida, kā iegūt
iestrēdzis šajā ciklā.

802
00:34:31,940 --> 00:34:34,790
Bet tas ir par hit, ka
tā saukto vispārējo gadījumu.

803
00:34:34,790 --> 00:34:37,310
Jo kas ir T 1, vai mēs apgalvot?

804
00:34:37,310 --> 00:34:37,810
0.

805
00:34:37,810 --> 00:34:39,730
Tātad beidzot, mēs varam strādāt atpakaļ.

806
00:34:39,730 --> 00:34:44,290
>> Ja T no 1 ir 0, es tagad var iet atpakaļ uz augšu viens
rindā uz šo puisis šeit, un es varu

807
00:34:44,290 --> 00:34:46,330
iespraudiet 0 t 1.

808
00:34:46,330 --> 00:34:51,770
Tātad tas nozīmē, ka tā atbilst 2 reizes nulles,
citādi pazīstams kā 0, 2 plus.

809
00:34:51,770 --> 00:34:53,739
Un tā, ka visa izteiksme ir 2.

810
00:34:53,739 --> 00:34:58,740
>> Tagad, ja es ņemtu T 2, kura atbilde
ir 2, plug to viduslīnijas, T

811
00:34:58,740 --> 00:35:02,740
gada 4, kas dod man 2 reizes
2 plus 4, tā 8.

812
00:35:02,740 --> 00:35:07,080
Ja es pēc tam plug 8 līdz iepriekšējā
līnija, kas dod man 2 reizes 8, 16.

813
00:35:07,080 --> 00:35:12,470
Un, ja mēs pēc tam turpināt, ka ar
24, pievienojot 16, mēs beidzot nokļūt

814
00:35:12,470 --> 00:35:13,820
vērtība no 64.

815
00:35:13,820 --> 00:35:18,480
>> Tagad, ka pati par sevi veida runā
nekas līdz n apzīmējums,

816
00:35:18,480 --> 00:35:20,700
Big O, omega, ka mēs esam
runājam par.

817
00:35:20,700 --> 00:35:24,890
Bet izrādās, ka 64 ir patiešām
16, izmērs no ieejas,

818
00:35:24,890 --> 00:35:27,110
log no 16 2 bāzi.

819
00:35:27,110 --> 00:35:30,200
Un, ja tas ir mazliet svešs, tikai
domāju, ka atpakaļ, un tas būs nāk atpakaļ

820
00:35:30,200 --> 00:35:30,700
jums galu galā.

821
00:35:30,700 --> 00:35:33,775
Ja tas ir log bāze 2, tas ir tāpat kā 2
izvirzīts uz ko jums dod 16?

822
00:35:33,775 --> 00:35:36,380
Ak, tas ir 4, tāpēc tas ir 16 reizes 4.

823
00:35:36,380 --> 00:35:39,380
>> Un atkal, tas nav liels galā, ja tas
ir sava veida miglaina atmiņas tagad.

824
00:35:39,380 --> 00:35:43,720
Bet tagad, ņem uz ticību
ka 16 log 16 ir 64.

825
00:35:43,720 --> 00:35:46,590
Un tik tiešām, ar šo vienkāršo veselība
pārbauda, ​​mēs esam apstiprināta -

826
00:35:46,590 --> 00:35:48,250
bet izrādījās formāli -

827
00:35:48,250 --> 00:35:52,800
ka darbības laiks sapludināšanas
veida ir patiešām n log n.

828
00:35:52,800 --> 00:35:53,790
>> Tātad nav slikti.

829
00:35:53,790 --> 00:35:57,260
Tas noteikti ir labāk nekā
algoritmi mēs esam redzējuši līdz šim, un

830
00:35:57,260 --> 00:36:00,710
tas ir tāpēc, ka mēs esam parādi, viens,
tehniku, ko sauc rekursija.

831
00:36:00,710 --> 00:36:03,880
Bet vēl interesantāka nekā tas, ka
jēdziens dalot un iekarošana.

832
00:36:03,880 --> 00:36:07,460
Atkal, patiesi nedēļa 0 sīkumi, ka
pat tagad ir atkārtošanos

833
00:36:07,460 --> 00:36:08,740
vairāk pārliecinoša veidā.

834
00:36:08,740 --> 00:36:11,750
>> Tagad fun maz izmantot, ja jūs esat
nekad nav izdarījusi - un jūs, iespējams,

835
00:36:11,750 --> 00:36:14,660
nebūtu, jo sava veida normāli
cilvēki nedomā to darīt.

836
00:36:14,660 --> 00:36:20,650
Bet, ja es eju uz google.com un, ja
Es gribu, lai uzzinātu kaut ko par

837
00:36:20,650 --> 00:36:22,356
rekursijas, Enter.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [Smiekli]

840
00:36:29,058 --> 00:36:32,030
[Vairāk smiekli]

841
00:36:32,030 --> 00:36:33,385
DAVID Malan: Slikti joks lēnām izplatās.

842
00:36:33,385 --> 00:36:34,450
[Smiekli]

843
00:36:34,450 --> 00:36:36,970
DAVID Malan: Tikai gadījumā, tas ir tur.

844
00:36:36,970 --> 00:36:38,710
Man nav izskaidrot to nepareizi,
un tur ir joks.

845
00:36:38,710 --> 00:36:40,810
Labi.

846
00:36:40,810 --> 00:36:42,950
Izskaidrot to, lai cilvēki blakus jums, ja
tas nav gluži uzklikšķināt tikai yet.

847
00:36:42,950 --> 00:36:47,650
Bet rekursijas, plašākā nozīmē, attiecas
procesam funkciju zvana

848
00:36:47,650 --> 00:36:51,430
pats, vai, plašākā nozīmē, dalot
problēma, par kaut ko, kas var būt

849
00:36:51,430 --> 00:36:56,220
atrisināt savstarpēji nesaistīti, risinot identiskas
pārstāvis problēmas.

850
00:36:56,220 --> 00:36:58,400
>> Nu, pieņemsim mainīt rīkiem
tikai brīdi.

851
00:36:58,400 --> 00:37:00,840
Mēs vēlētos, lai izbeigtu par dažiem cliffhangers,
tāpēc sāksim uzstādīt

852
00:37:00,840 --> 00:37:05,870
posms, vairākas minūtes,
uz ļoti vienkāršu ideju -

853
00:37:05,870 --> 00:37:07,620
ka pārnešana diviem elementiem, vai ne?

854
00:37:07,620 --> 00:37:10,040
Visi šie algoritmiem, mēs esam bijuši
runājot par pēdējo pāris

855
00:37:10,040 --> 00:37:12,420
lekcijas ietver dažus
veida pārnešana.

856
00:37:12,420 --> 00:37:14,630
Šodien tā ir vizualizēta ar viņiem kļūst
up no saviem krēsliem un

857
00:37:14,630 --> 00:37:18,570
staigā, bet kodu, mēs būtu
tikai ņemt elements no viena masīva

858
00:37:18,570 --> 00:37:20,370
un plunkšķis to uz citu.

859
00:37:20,370 --> 00:37:21,880
>> Tātad, kā mēs iet par to izdarīt?

860
00:37:21,880 --> 00:37:24,850
Nu, ļaujiet man iet uz priekšu un rakstīt
ātrs programma šeit.

861
00:37:24,850 --> 00:37:31,600
Es iešu uz priekšu un darīt
Tas kā tālāk.

862
00:37:31,600 --> 00:37:33,910
Sauksim šo -

863
00:37:33,910 --> 00:37:38,070
Ko mēs gribam, lai izsauktu šo vienu?

864
00:37:38,070 --> 00:37:38,650
>> Patiesībā, nē.

865
00:37:38,650 --> 00:37:39,420
Ļaujiet man attīt.

866
00:37:39,420 --> 00:37:41,220
Es nevēlos to darīt
cliffhanger vēl.

867
00:37:41,220 --> 00:37:42,270
Tas būs sabojāt fun.

868
00:37:42,270 --> 00:37:43,600
Darīsim to vietā.

869
00:37:43,600 --> 00:37:47,430
>> Pieņemsim, ka es gribu uzrakstīt nedaudz
programma, un ka tagad aptver šis

870
00:37:47,430 --> 00:37:48,700
Ideja par rekursijas.

871
00:37:48,700 --> 00:37:50,370
I veida got priekšā sevi tur.

872
00:37:50,370 --> 00:37:51,420
Es esmu gatavojas veikt šādas darbības.

873
00:37:51,420 --> 00:38:00,220
>> Pirmkārt, ātrs ietver standarta io.h,
kā arī ietvert cs50.h.

874
00:38:00,220 --> 00:38:03,200
Un tad es iešu uz priekšu
un atzīt int galvenais spēkā neesošu

875
00:38:03,200 --> 00:38:04,360
parastajā veidā.

876
00:38:04,360 --> 00:38:07,920
Es sapratu, ka es esmu misnamed failu, tāpēc
ļaujiet man vienkārši pievienojiet. c pagarinājumu šeit, lai

877
00:38:07,920 --> 00:38:09,510
ka mēs varam apkopot to pareizi.

878
00:38:09,510 --> 00:38:10,970
Sākt šo funkciju off.

879
00:38:10,970 --> 00:38:13,290
>> Un funkcija es gribu rakstīt, gluži
vienkārši, ir viens, kas prasa

880
00:38:13,290 --> 00:38:16,210
par vairākiem lietotāju un pēc tam pievieno uz augšu
visi skaitļi starp ka

881
00:38:16,210 --> 00:38:19,920
numuru un, teiksim, 0.

882
00:38:19,920 --> 00:38:22,510
Tātad vispirms es iešu uz priekšu
un atzīt int n.

883
00:38:22,510 --> 00:38:24,760
Tad es kopēt kādu kodu, kas
mēs esam, ko izmanto uz brīdi.

884
00:38:24,760 --> 00:38:26,660
Kamēr kaut kas ir patiess.

885
00:38:26,660 --> 00:38:28,000
Es atnākšu atpakaļ, ka brīdi.

886
00:38:28,000 --> 00:38:29,010
>> Ko es gribu darīt?

887
00:38:29,010 --> 00:38:33,460
Es gribu teikt printf pozitīvu
skaitlis lūdzu.

888
00:38:33,460 --> 00:38:36,130
Un tad es esmu gatavojas
saka n izpaužas saņemt int.

889
00:38:36,130 --> 00:38:38,800
Tātad vēlreiz, daži tekstveidnes kodu
ka mēs esam, ko izmanto iepriekš.

890
00:38:38,800 --> 00:38:40,810
Un es esmu gatavojas darīt
bet n ir mazāk nekā 1.

891
00:38:40,810 --> 00:38:44,120
Tātad, tas nodrošinās, ka lietotājs
dod man vesels pozitīvs skaitlis.

892
00:38:44,120 --> 00:38:45,490
>> Un tagad es esmu gatavojas darīt šādi.

893
00:38:45,490 --> 00:38:51,020
Es gribu, lai saskaitītu visus numurus
starp 1 un un n, 0 vai un n,

894
00:38:51,020 --> 00:38:52,570
līdzvērtīgi, lai iegūtu kopējo summu.

895
00:38:52,570 --> 00:38:55,100
Tik liels sigma simbolu
ka jūs varētu atcerēties.

896
00:38:55,100 --> 00:38:59,050
Tāpēc es esmu gatavojas darīt to pēc pirmā zvana
funkcija sauc sigma,

897
00:38:59,050 --> 00:39:06,030
iet to n, un tad es esmu gatavojas
saka printf, atbilde ir tiesības tur.

898
00:39:06,030 --> 00:39:08,180
>> Tātad, īsi sakot, man un
int no lietotāja.

899
00:39:08,180 --> 00:39:09,280
Es nodrošinātu, ka tā ir pozitīva.

900
00:39:09,280 --> 00:39:12,700
Es apliecinu, mainīgo sauc atbildi
tipa int un uzglabāt tajā atgriešanās

901
00:39:12,700 --> 00:39:15,610
vērtība sigma, garāmejot n kā priekšnodokli.

902
00:39:15,610 --> 00:39:17,060
Un tad es izdrukāt šo atbildi.

903
00:39:17,060 --> 00:39:19,550
>> Diemžēl, lai gan sigma izklausās
kā kaut kas varētu būt

904
00:39:19,550 --> 00:39:24,040
math.h failu, savu deklarāciju,
tas faktiski nav.

905
00:39:24,040 --> 00:39:24,690
Tātad tas ir OK.

906
00:39:24,690 --> 00:39:26,170
Es varu īstenot šo sevi.

907
00:39:26,170 --> 00:39:29,160
Es esmu gatavojas īstenot sauc funkciju
sigma, un tas notiek, lai

908
00:39:29,160 --> 00:39:29,900
parametrs -

909
00:39:29,900 --> 00:39:32,100
pieņemsim tikai sauc to m, tikai
tāpēc tas ir atšķirīgs.

910
00:39:32,100 --> 00:39:35,910
Un tad šeit, es esmu gatavojas teikt,
labi, ja m ir mazāk nekā 1 - tas ir

911
00:39:35,910 --> 00:39:38,180
ļoti neinteresanti programmu.

912
00:39:38,180 --> 00:39:41,700
Tāpēc es esmu gatavojas iet uz priekšu un
nekavējoties atdod 0.

913
00:39:41,700 --> 00:39:45,920
Tas vienkārši nav jēgas, lai pievienotu up visu
skaitļi no 1 līdz m, ja m

914
00:39:45,920 --> 00:39:48,470
pati ir 0 vai negatīvs.

915
00:39:48,470 --> 00:39:50,900
>> Un tad es iešu uz priekšu
un darīt to ļoti iteratīvi.

916
00:39:50,900 --> 00:39:53,090
Es esmu gatavojas darīt šāda veida vecās skolas,
un es iešu uz priekšu

917
00:39:53,090 --> 00:39:57,150
un teikt, ka es esmu gatavojas
atzīt kāda summa ir 0.

918
00:39:57,150 --> 00:39:59,630
Tad es esmu nāksies
lai cilpa int -

919
00:39:59,630 --> 00:40:02,820
un ļaujiet man darīt to, kas atbilst mūsu
sadales kodu, tāpēc jums ir kopiju

920
00:40:02,820 --> 00:40:07,500
mājās. int i izpaužas 1 gada līdz
i ir mazāks par vai vienāds ar m.

921
00:40:07,500 --> 00:40:09,430
i plus plus.

922
00:40:09,430 --> 00:40:11,430
Un tad iekšpusē tā, lai cilpa -

923
00:40:11,430 --> 00:40:12,440
mēs esam gandrīz tur -

924
00:40:12,440 --> 00:40:15,810
Summa izpaužas summu plus 1.

925
00:40:15,810 --> 00:40:17,670
Un tad es esmu gatavojas atgriezties summu.

926
00:40:17,670 --> 00:40:19,420
>> Tāpēc es darīju to ātri,
diezgan protams.

927
00:40:19,420 --> 00:40:22,775
Bet atkal, galvenā funkcija ir diezgan
vienkārši, pamatojoties uz kodu, kuru mēs esam

928
00:40:22,775 --> 00:40:23,190
rakstīts līdz šim.

929
00:40:23,190 --> 00:40:25,610
Izmanto dubulto cilpu, lai iegūtu pozitīvu
int no lietotāja.

930
00:40:25,610 --> 00:40:29,870
Es tad iet, ka int uz jaunu funkciju
sauc sigma, aicinot to, atkal, n.

931
00:40:29,870 --> 00:40:33,100
Un es glabāt atgriezto vērtību, atbilde
No melnās kastes patlaban

932
00:40:33,100 --> 00:40:35,460
pazīstams kā sigma, jo mainīgo
sauc par atbildi.

933
00:40:35,460 --> 00:40:36,580
Tad es to izdrukāt.

934
00:40:36,580 --> 00:40:39,090
>> Ja mēs tagad turpināt stāstu,
cik ir sigma īstenots?

935
00:40:39,090 --> 00:40:40,840
Es ierosinu, lai īstenotu šādi.

936
00:40:40,840 --> 00:40:43,560
Pirmkārt, mazliet kļūdas kontrolpārbaudes
lai pārliecinātos, ka lietotājs nav

937
00:40:43,560 --> 00:40:46,480
messing ar mani un garāmejot
daži negatīvs vai 0 vērtības.

938
00:40:46,480 --> 00:40:49,710
Tad es deklarēt sauc mainīgo
Apkopojot un noteikt to līdz 0.

939
00:40:49,710 --> 00:40:55,910
>> Un tagad man sāk pāriet no i vienāds
1 visu ceļu līdz pat un ieskaitot m,

940
00:40:55,910 --> 00:41:00,130
jo es gribu, lai iekļautu visus
skaitu no viena līdz m, ieskaitot.

941
00:41:00,130 --> 00:41:04,350
Un iekšpusē šis cilpas, es tikai darīt
Summa izpaužas kāds tas ir tagad, plus

942
00:41:04,350 --> 00:41:08,900
I vērtība.

943
00:41:08,900 --> 00:41:10,370
Plus vērtība no i.

944
00:41:10,370 --> 00:41:14,090
>> Kā malā, ja jūs esat nav redzējis šo
pirms, tur ir dažas sintaktisko cukura

945
00:41:14,090 --> 00:41:14,870
uz šīs līnijas.

946
00:41:14,870 --> 00:41:21,120
Es varu pārrakstīt šo kā arī vienāds i,
tikai, lai saglabātu sev dažus taustiņsitienus

947
00:41:21,120 --> 00:41:22,570
un izskatās mazliet vēsākas.

948
00:41:22,570 --> 00:41:23,140
Bet tas arī viss.

949
00:41:23,140 --> 00:41:24,660
Tas ir funkcionāli pats.

950
00:41:24,660 --> 00:41:26,710
>> Diemžēl, šis kods ir
nav gatavojas sastādīt vēl.

951
00:41:26,710 --> 00:41:31,600
Ja es palaist darīt sigma 0, cik am
Es gatavojas saņemt kliedza uz?

952
00:41:31,600 --> 00:41:33,473
Kas tas būs nepatīk?

953
00:41:33,473 --> 00:41:35,740
>> Mērķauditorija: [nedzirdama].

954
00:41:35,740 --> 00:41:37,800
>> DAVID Malan: Jā, man nav deklarējis
funkcija up top, labi?

955
00:41:37,800 --> 00:41:40,590
C ir sava veida stulba, ar to, ka tā tikai
dara to, ko jums pateikt to, ko darīt, un jūs

956
00:41:40,590 --> 00:41:41,880
ir darīt to šādā secībā.

957
00:41:41,880 --> 00:41:45,910
Un tāpēc, ja es hit Enter šeit, es esmu gatavojas
saņemt par sigma brīdinājums netieši

958
00:41:45,910 --> 00:41:46,860
deklarācija.

959
00:41:46,860 --> 00:41:48,120
>> Ak, nav problēmu.

960
00:41:48,120 --> 00:41:50,370
Es var iet uz augšu uz augšu, un es var
saka, labi, pagaidiet minūti.

961
00:41:50,370 --> 00:41:54,240
Sigma ir funkcija, kas atgriež
int un tā sagaida,

962
00:41:54,240 --> 00:41:56,620
int kā ievade, semikolu.

963
00:41:56,620 --> 00:41:59,550
Vai es varētu likt visu funkciju
Iepriekš galvenais, bet kopumā, es gribētu

964
00:41:59,550 --> 00:42:02,260
iesaka pret to, jo tas ir
jauki, vienmēr ir galvenais augšā tā

965
00:42:02,260 --> 00:42:06,310
Jūs varat nirt tiesības un zina, ko
Programma dara, lasot galveno pirmās.

966
00:42:06,310 --> 00:42:07,930
>> Tātad, tagad ļaujiet man notīrītu ekrānu.

967
00:42:07,930 --> 00:42:09,330
Pārtaisīt sigma 0.

968
00:42:09,330 --> 00:42:10,340
Viss, šķiet, lai pārbaudītu out.

969
00:42:10,340 --> 00:42:11,970
Ļaujiet man palaist sigma 0.

970
00:42:11,970 --> 00:42:12,770
Pozitīva cita.

971
00:42:12,770 --> 00:42:15,580
Es došu to skaitu
3, lai saglabātu tā vienkārši.

972
00:42:15,580 --> 00:42:18,710
Tā, ka vajadzētu dot man 3
plus 2 plus 1, tā 6.

973
00:42:18,710 --> 00:42:20,750
Enter, un patiešām man 6.

974
00:42:20,750 --> 00:42:21,820
>> Es varu darīt kaut ko lielāku -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Tāpat kā pieskari, es esmu gatavojas darīt
kaut ko smieklīgu, piemēram, ļoti liels

977
00:42:27,690 --> 00:42:30,375
numuru, Ak, kas faktiski izstrādāta -

978
00:42:30,375 --> 00:42:31,600
eh, es nedomāju, ka ir labi.

979
00:42:31,600 --> 00:42:32,810
Let 's redzēt.

980
00:42:32,810 --> 00:42:34,060
Let 's tiešām sajaukt ar to.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> Tas ir problēma.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
Kas notiek?

985
00:42:44,970 --> 00:42:46,050
Kods nav tik slikti.

986
00:42:46,050 --> 00:42:48,470
Tas joprojām ir lineāra.

987
00:42:48,470 --> 00:42:50,810
Whistling ir labs efekts, lai gan.

988
00:42:50,810 --> 00:42:52,060
Kas notiek?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> Nav pārliecināts, vai es dzirdēju to.

991
00:42:55,620 --> 00:42:57,620
Tātad izrādās, - un
tas ir kā malā.

992
00:42:57,620 --> 00:42:59,400
Tas ir ne kodols, lai
Ideja par rekursijas.

993
00:42:59,400 --> 00:43:02,480
Izrādās, jo es cenšos
pārstāvēt tik liels skaits, lielākā daļa

994
00:43:02,480 --> 00:43:06,980
iespējams, tas tiek nepareizi
ar C kā nav pozitīvu skaitli,

995
00:43:06,980 --> 00:43:09,980
bet negatīvs skaitlis.

996
00:43:09,980 --> 00:43:12,690
>> Mēs esam nav runājuši, bet tas
Izrādās, tur ir negatīvie skaitļi

997
00:43:12,690 --> 00:43:14,210
pasaulē papildus
uz pozitīviem skaitļiem.

998
00:43:14,210 --> 00:43:16,290
Un līdzekļus, ar kuriem jūs varat
pārstāvēt negatīvu skaitli

999
00:43:16,290 --> 00:43:19,530
būtībā ir, jūs izmantojat vienu
īpašu bit norādīt

1000
00:43:19,530 --> 00:43:20,400
pozitīvi nekā negatīvi.

1001
00:43:20,400 --> 00:43:22,950
Tas ir nedaudz sarežģītāka nekā,
bet tas ir pamata ideja.

1002
00:43:22,950 --> 00:43:26,740
>> Tātad, diemžēl, ja C ir mulsinoši vienu
no tiem kā reāli nozīmē biti,

1003
00:43:26,740 --> 00:43:30,790
ak, tas ir negatīvs skaitlis, mana cilpa
Šeit, piemēram, ir faktiski nekad nav

1004
00:43:30,790 --> 00:43:31,740
gatavojas pārtraukt.

1005
00:43:31,740 --> 00:43:33,850
Tātad, ja es faktiski drukāšanas kaut
atkal un atkal, mēs būtu

1006
00:43:33,850 --> 00:43:34,650
redzēt visai daudz.

1007
00:43:34,650 --> 00:43:36,220
Bet atkal, tas ir papildus punktu.

1008
00:43:36,220 --> 00:43:38,590
Tas ir patiešām vienkārši veida
zinātkāres, ka mēs nāksim

1009
00:43:38,590 --> 00:43:39,550
atpakaļ beidzot.

1010
00:43:39,550 --> 00:43:43,400
Bet tagad, tas ir pareizs
īstenošanu, ja mēs pieņemam, ka

1011
00:43:43,400 --> 00:43:45,970
lietotājs sniegs Ints
kas iederas ints.

1012
00:43:45,970 --> 00:43:49,370
>> Bet es apgalvo, ka šis kods, atklāti sakot,
varētu izdarīt tik daudz vienkāršāk.

1013
00:43:49,370 --> 00:43:54,060
Ja pie rokas mērķis ir veikt vairākus
, piemēram, m un pievienot up visi no

1014
00:43:54,060 --> 00:43:59,510
skaitļi starp to un 1 vai otrādi
starp 1 un tas, es pretenziju

1015
00:43:59,510 --> 00:44:03,380
ka es varētu aizņemties šo ideju, kas apvienojas
kārtot bija, kas ir lietojis problēmu

1016
00:44:03,380 --> 00:44:05,660
Šāda izmēra un dalot to
uz kaut ko mazāku.

1017
00:44:05,660 --> 00:44:09,875
Varbūt ne pusi, bet mazāks, bet
reprezentatīva pats.

1018
00:44:09,875 --> 00:44:12,130
Pati ideja, bet mazāka problēma.

1019
00:44:12,130 --> 00:44:15,470
>> Tāpēc es esmu faktiski - ļaujiet man ietaupīt šo failu
ar atšķirīgu versijas numuru.

1020
00:44:15,470 --> 00:44:17,670
Mēs saucam šo versiju
1, nevis 0.

1021
00:44:17,670 --> 00:44:20,790
Un es apgalvot, ka es faktiski var
reimplement tas šāda veida

1022
00:44:20,790 --> 00:44:22,160
prātā saliekuma veidā.

1023
00:44:22,160 --> 00:44:23,710
>> Es esmu gatavojas atstāt daļu no tā vien.

1024
00:44:23,710 --> 00:44:27,710
Es esmu gatavojas teikt, ja m ir mazāks
par vai pat vienāds ar 0 -

1025
00:44:27,710 --> 00:44:29,280
Es esmu tikai būs nedaudz
vairāk anālais šoreiz

1026
00:44:29,280 --> 00:44:30,520
ar manu kļūdu pārbaudi -

1027
00:44:30,520 --> 00:44:33,190
Es iešu uz priekšu un atpakaļ 0.

1028
00:44:33,190 --> 00:44:34,490
Šī ir patvaļīga.

1029
00:44:34,490 --> 00:44:37,500
Es esmu vienkārši izlemt, ja lietotājs
dod man negatīvu skaitli, es esmu

1030
00:44:37,500 --> 00:44:41,490
atgriežoties 0, un tie būtu jālasa
dokumentāciju ciešāk.

1031
00:44:41,490 --> 00:44:42,170
>> Pārējais -

1032
00:44:42,170 --> 00:44:44,070
paziņojums, ko es esmu gatavojas darīt.

1033
00:44:44,070 --> 00:44:49,260
Vēl es esmu gatavojas atgriezties m plus -

1034
00:44:49,260 --> 00:44:51,010
kas ir sigma no m?

1035
00:44:51,010 --> 00:44:56,710
Nu, sigma no m plus m mīnus 1,
plus m mīnus 2, plus m mīnus 3.

1036
00:44:56,710 --> 00:44:58,030
Es nevēlos rakstīt visu šo out.

1037
00:44:58,030 --> 00:44:59,120
Kāpēc ne es tikai punt?

1038
00:44:59,120 --> 00:45:05,080
Rekursīvi zvanu sevi ar nedaudz
mazāka problēma, semikols,

1039
00:45:05,080 --> 00:45:06,840
un sauc to dienu?

1040
00:45:06,840 --> 00:45:07,040
>> Labi?

1041
00:45:07,040 --> 00:45:10,980
Tagad arī šeit, jūs varētu justies, vai jāuztraucas
ka tas ir bezgalīga cilpa, kas es esmu

1042
00:45:10,980 --> 00:45:15,450
pamudināt, kuru es esmu ieviešanas
sigma, izsaucot Sigma.

1043
00:45:15,450 --> 00:45:20,342
Bet tas ir pilnīgi OK, jo es
domāju uz priekšu, pievieno kuras pozīcijas?

1044
00:45:20,342 --> 00:45:22,600
>> Mērķauditorija: [nedzirdama].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID Malan: 23.-26, kas
ir mana ja nosacījums.

1046
00:45:25,430 --> 00:45:28,390
Jo to, kas ir jauka par
atņemšanu šeit, jo es glabāt

1047
00:45:28,390 --> 00:45:31,180
pasniegtas sigma mazākas problēmas, mazākas
problēmas, mazākas - tas nav

1048
00:45:31,180 --> 00:45:31,870
uz pusi mazāks.

1049
00:45:31,870 --> 00:45:34,380
Tas ir tikai bērns solis mazāks,
bet tas ir OK.

1050
00:45:34,380 --> 00:45:38,050
Jo galu galā, mēs darbu
mūsu ceļu uz leju, uz 1 vai 0.

1051
00:45:38,050 --> 00:45:41,630
Un, kad mēs hit 0, sigma nav
saukšu sevi vairs.

1052
00:45:41,630 --> 00:45:43,590
Tas notiek, lai uzreiz atgrieztos 0.

1053
00:45:43,590 --> 00:45:47,960
>> Tātad efekts, ja jūs veida vēja šis
up jūsu prātā, ir pievienot m plus

1054
00:45:47,960 --> 00:45:52,740
m mīnus 1, plus m mīnus 2, plus m mīnus
3, kā arī dot, dot, dot, m mīnus

1055
00:45:52,740 --> 00:45:57,820
m, beidzot sniedzot jums 0, un
efekts ir galu galā pievienot visus

1056
00:45:57,820 --> 00:45:59,070
šīs lietas kopā.

1057
00:45:59,070 --> 00:46:02,380
Tāpēc mums nav, ar rekursijas,
atrisināt problēmu, ka mēs

1058
00:46:02,380 --> 00:46:03,470
nevarētu atrisināt agrāk.

1059
00:46:03,470 --> 00:46:06,840
Patiešām, versija 0 par šo, un ik
problēma līdz šim ir bijusi atrisināmas

1060
00:46:06,840 --> 00:46:09,980
ar tikai izmantojot, cilpas vai kamēr
cilpas vai līdzīgas konstrukcijas.

1061
00:46:09,980 --> 00:46:13,150
>> Bet rekursijas, es daresay, dod mums
atšķirīgs veids, kā domāt par

1062
00:46:13,150 --> 00:46:17,010
problēmas, kuru, ja mēs varam veikt
Problēma, sadalīt to no kaut kā

1063
00:46:17,010 --> 00:46:22,340
diezgan liela kaut gan ierobežota
mazāks, es apgalvot, ka mēs varam atrisināt

1064
00:46:22,340 --> 00:46:26,040
varbūt nedaudz vairāk eleganti ziņā
no dizaina, ar mazāk kodu,

1065
00:46:26,040 --> 00:46:30,980
un varbūt pat novērst problēmas, kas varētu
būt grūtāk, jo mēs galu galā

1066
00:46:30,980 --> 00:46:33,280
skat, risinot tīri iteratīvi.

1067
00:46:33,280 --> 00:46:35,980
>> Bet cliffhanger, ka es to darīju
vēlaties atstāt mums bija šī.

1068
00:46:35,980 --> 00:46:40,720
Ļaujiet man iet uz priekšu un atvērt
up failu no -

1069
00:46:40,720 --> 00:46:44,300
faktiski, ļaujiet man iet un
izdarītu reālu ātri.

1070
00:46:44,300 --> 00:46:46,875
Ļaujiet man iet uz priekšu un ierosināt
punktu.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Starp šodienas kods ir šo failu šeit.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Tas viens šeit, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Tātad šī ir stulba maz programmu, kas
Es saputota up, kas apgalvo, ka darīt

1076
00:47:06,260 --> 00:47:06,940
punktu.

1077
00:47:06,940 --> 00:47:10,140
Jo galvenais, tā pirmo reizi paziņo
int sauc x un piešķir tai

1078
00:47:10,140 --> 00:47:11,100
vērtība no 1.

1079
00:47:11,100 --> 00:47:13,520
Tad tas paziņo, int y un
piešķir tam vērtību 2.

1080
00:47:13,520 --> 00:47:15,310
Tad tas izdrukā kādi x un y ir.

1081
00:47:15,310 --> 00:47:17,781
Tad tas saka, pārnešana, dot dot dot.

1082
00:47:17,781 --> 00:47:21,670
>> Tad tas apgalvo, ka ir zvana funkciju
sauc swap, iet uz x un

1083
00:47:21,670 --> 00:47:24,290
y, ideja, kas ir kas, cerams,
x un y nāks atpakaļ

1084
00:47:24,290 --> 00:47:25,620
atšķirīgs, pretī.

1085
00:47:25,620 --> 00:47:27,110
Tad tas apgalvo nomainīju!

1086
00:47:27,110 --> 00:47:28,420
ar izsaukuma zīmi.

1087
00:47:28,420 --> 00:47:30,190
Tad tas izdrukā x un y.

1088
00:47:30,190 --> 00:47:33,480
>> Bet izrādās, ka tas ir ļoti
vienkārši demonstrācija uz leju

1089
00:47:33,480 --> 00:47:35,570
šeit ir faktiski buggy.

1090
00:47:35,570 --> 00:47:38,870
Kaut arī es esmu atzīts pagaidu
mainīga un īslaicīgi liekot uz

1091
00:47:38,870 --> 00:47:42,010
tā, tad es esmu pārcelšanu citā amatā
vērtība, b -

1092
00:47:42,010 --> 00:47:45,080
kas jūtas pamatoti, jo es esmu
saglabāts kopiju, kas temp.

1093
00:47:45,080 --> 00:47:48,410
Tad es atjaunināt b uz vienlīdzīgu
kāds bija temp.

1094
00:47:48,410 --> 00:47:51,610
Šī veida čaulu spēli pārvietojas
uz b un b vērā, izmantojot šo

1095
00:47:51,610 --> 00:47:54,360
vidējā cilvēks sauc temp jūtas
pilnīgi pamatota.

1096
00:47:54,360 --> 00:47:57,270
>> Bet es apgalvo, ka tad, kad es palaist šo
kods, kā es darīšu tagad -

1097
00:47:57,270 --> 00:47:59,490
ļaujiet man iet uz priekšu un ielīmēt to šeit.

1098
00:47:59,490 --> 00:48:01,995
Es aicinu šo noswap.c.

1099
00:48:01,995 --> 00:48:05,630
Un, kā liecina nosaukums, tas nav
būs pareizs programmu.

1100
00:48:05,630 --> 00:48:09,460
Padarīt noswap / nē mijmaiņas..

1101
00:48:09,460 --> 00:48:12,110
x ir 1, y ir 2, pārnešana, samainās.

1102
00:48:12,110 --> 00:48:14,220
x ir 1, y ir 2.

1103
00:48:14,220 --> 00:48:16,920
Tas ir pilnīgi nepareizi, pat
lai gan tas šķiet pilnīgi

1104
00:48:16,920 --> 00:48:17,730
saprātīgi mani.

1105
00:48:17,730 --> 00:48:21,330
Un tur ir iemesls, bet mēs neesam
gatavojas atklāt iemeslu tikai yet.

1106
00:48:21,330 --> 00:48:24,610
>> Tagad otro cliffhanger es gribēju
atstāt jūs ar ir tas,

1107
00:48:24,610 --> 00:48:27,120
paziņojums par veidu par kupona kodu.

1108
00:48:27,120 --> 00:48:31,590
Mūsu inovācija vēlu dienu šogad
ir izraisījusi ne-triviāls numuru

1109
00:48:31,590 --> 00:48:33,830
jautājumu, kas bija
nav mūsu mērķis.

1110
00:48:33,830 --> 00:48:36,590
Nodoms šo kuponu kodiem,
saskaņā ar kuru, ja jums ir daļa no problēmas

1111
00:48:36,590 --> 00:48:39,850
noteikti agri, tādējādi iegūt papildus dienu,
bija patiešām palīdzēt jums guys palīdzēt

1112
00:48:39,850 --> 00:48:42,420
pats sāk agri, kārtot
par ko incentivizing jums.

1113
00:48:42,420 --> 00:48:44,880
Mums palīdz sadalīt slodzi starp
darba laiks labāk tā, ka

1114
00:48:44,880 --> 00:48:45,740
tas ir sava veida win-win.

1115
00:48:45,740 --> 00:48:48,860
>> Diemžēl, es domāju, ka manas instrukcijas
nav bijuši līdz šim, ļoti skaidrs, tāpēc

1116
00:48:48,860 --> 00:48:52,230
Es devos atpakaļ šīs nedēļas nogalē, un atjaunināts
spec lielāks, drosmīgāki tekstu

1117
00:48:52,230 --> 00:48:53,600
izskaidrot lodes, piemēram, šo.

1118
00:48:53,600 --> 00:48:56,900
Un tikai teikt to vēl publiski, ar
noklusējuma, problēmu kopas ir saistīts ceturtdiena

1119
00:48:56,900 --> 00:48:58,400
pusdienlaikā, par mācību programmu.

1120
00:48:58,400 --> 00:49:02,030
Ja jūs sākat agri, apdares daļa
problēma, kas līdz trešdienai pulksten 12:00

1121
00:49:02,030 --> 00:49:05,170
PM, daļu, kas attiecas uz kuponu
kods, ideja ir, ka jūs varat paplašināt

1122
00:49:05,170 --> 00:49:07,710
Jūsu termiņš
P noteikts līdz piektdienai.

1123
00:49:07,710 --> 00:49:10,890
Kas ir, mazliet off tiny daļu no P
noteikts, salīdzinot ar to, kas parasti ir

1124
00:49:10,890 --> 00:49:13,200
lielāka problēma, un jūs pērkat
sev papildus dienu.

1125
00:49:13,200 --> 00:49:15,190
Atkal, tas izpaužas jums domāt par
problēma, kas, izpaužas jums

1126
00:49:15,190 --> 00:49:16,380
darba laiks ātrāk.

1127
00:49:16,380 --> 00:49:20,670
Bet kupona kods problēma joprojām
nepieciešams, pat ja jums nav jāiesniedz to.

1128
00:49:20,670 --> 00:49:23,340
>> Bet vēl pārliecinoši tas ir.

1129
00:49:23,340 --> 00:49:26,520
(STAGE WHISPER) Un tiem ļaudīm, atstājot
Jau ir gonna žēl to.

1130
00:49:26,520 --> 00:49:28,620
Tā kā ir uz balkona ļaudīm.

1131
00:49:28,620 --> 00:49:32,510
I atvainojos iepriekš ļaudīm, par
balkons tādu iemeslu dēļ, kas būs

1132
00:49:32,510 --> 00:49:33,920
skaidrs tikai brīdi.

1133
00:49:33,920 --> 00:49:37,050
>> Tātad, mums ir paveicies, lai būtu viens no
CS50 ir bijušie direktoru vietnieki mācību puiši pie

1134
00:49:37,050 --> 00:49:39,302
kompānija sauc dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
Viņi ir ļoti dāsni ziedojuši
kupona kods, šeit par šo daudz vietas,

1136
00:49:45,500 --> 00:49:48,180
, kas ir izveidota no
ierastie 2 gigabaitiem.

1137
00:49:48,180 --> 00:49:51,740
Tātad, ko es domāju, ka mēs varētu darīt par to
gala piezīmi, ir darīt mazliet giveaway,

1138
00:49:51,740 --> 00:49:55,380
saskaņā ar kuru tikai brīdi, mēs atklās
uzvarētājs un kurš ir kuponu

1139
00:49:55,380 --> 00:49:57,980
kodu, tad varat doties uz viņu
mājas lapā, ierakstiet to, un voila, iegūt

1140
00:49:57,980 --> 00:50:01,370
kopumā daudz vairāk Dropbox vietas jūsu
ierīces un jūsu personas lietas.

1141
00:50:01,370 --> 00:50:05,690
>> Un pirmais, kurš vēlētos piedalīties
Šajā zīmējumā?

1142
00:50:05,690 --> 00:50:09,630
Labi, tagad, kas padara to vēl vairāk jautrības.

1143
00:50:09,630 --> 00:50:14,010
Persona, kas saņem šo 25 gigabaitu
kupona kods - kas ir tālu

1144
00:50:14,010 --> 00:50:16,150
vairāk pārliecinoša par vēlu
dienas tagad, varbūt -

1145
00:50:16,150 --> 00:50:20,620
ir viens, kurš sēž uz augšu
sēdekļa spilvenu, zem kuras ir

1146
00:50:20,620 --> 00:50:21,620
ka kupona kodu.

1147
00:50:21,620 --> 00:50:23,480
Jūs tagad var meklēt zem
Jūsu sēdekļa spilvenu.

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
>> -Viens, divi, trīs.

1151
00:50:31,620 --> 00:50:35,015
>> [Kliedz]

1152
00:50:35,015 --> 00:50:35,985
>> -Jūs saņemsiet auto!

1153
00:50:35,985 --> 00:50:36,670
Jūs saņemsiet automašīnu!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID Malan: Redzēsim
Jūs trešdien.

1155
00:50:37,970 --> 00:50:38,904
>> -Jūs saņemsiet auto!

1156
00:50:38,904 --> 00:50:39,371
Jūs saņemsiet automašīnu!

1157
00:50:39,371 --> 00:50:40,305
Jūs saņemsiet automašīnu!

1158
00:50:40,305 --> 00:50:41,706
Jūs saņemsiet automašīnu!

1159
00:50:41,706 --> 00:50:43,107
Jūs saņemsiet automašīnu!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID Malan: Balkons ļaudīm, nāc
lejup šeit uz priekšu,

1161
00:50:45,530 --> 00:50:46,866
kur mums ir ekstras.

1162
00:50:46,866 --> 00:50:50,282
>> -Ikviens izpaužas auto!

1163
00:50:50,282 --> 00:50:52,234
Ikviens izpaužas automašīnu!

1164
00:50:52,234 --> 00:50:52,722
>> [END VIDEO PLAYBACK]

1165
00:50:52,722 --> 00:50:54,590
>> Teicējs: Nākamajā CS50 -

1166
00:50:54,590 --> 00:51:00,374
>> SPEAKER 5: Ak mans Dievs Dievs Dievs Dievs
Dievs Dievs Dievs Dievs Dievs Dievs -

1167
00:51:00,374 --> 00:51:02,106
>> [UKELELE spēlē]