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

2
00:00:00,488 --> 00:00:10,800
>> [Predvajanja glasbe]

3
00:00:10,800 --> 00:00:13,500
DAVID Malan V redu.

4
00:00:13,500 --> 00:00:14,670
Vse je v redu, dobrodošli nazaj.

5
00:00:14,670 --> 00:00:18,120
Torej, to je 4 teden, začetek
Pogodbe, že.

6
00:00:18,120 --> 00:00:21,320
In ti boš spomnil, da je prejšnji teden, smo se
kodo namenjen le malo

7
00:00:21,320 --> 00:00:24,240
in smo začeli govoriti malo več
na visoki ravni, o stvareh, kot

8
00:00:24,240 --> 00:00:28,130
iskanje in razvrščanje, ki je, čeprav
Nekoliko preproste ideje, so

9
00:00:28,130 --> 00:00:31,840
Predstavnik vrsti problemov
boste začeli zlasti reševanje

10
00:00:31,840 --> 00:00:34,820
kot ste začeli razmišljati o končni
projekti in zanimive rešitve si

11
00:00:34,820 --> 00:00:36,760
morda morali resničnih problemov.

12
00:00:36,760 --> 00:00:39,490
Zdaj mehurček vrste je bil eden od najpreprostejših
taki algoritmi, in

13
00:00:39,490 --> 00:00:42,900
delo, ki ga ob teh majhnih številkah
na seznamu ali v matrično vrste

14
00:00:42,900 --> 00:00:46,530
mehurček svojo pot do vrha in
velike številke premakniti svojo pot navzdol

15
00:00:46,530 --> 00:00:47,930
Konec tega seznama.

16
00:00:47,930 --> 00:00:50,650
>> In opozarjajo, da bi lahko vizualizirati
bubble sort malo

17
00:00:50,650 --> 00:00:52,310
kaj takega.

18
00:00:52,310 --> 00:00:53,640
Naj gredo naprej in kliknite Start.

19
00:00:53,640 --> 00:00:55,350
Sem predizbere mehurček vrste.

20
00:00:55,350 --> 00:00:58,920
In če se spomnite, da je višji modra
črte predstavljajo velike številke, mala

21
00:00:58,920 --> 00:01:03,300
modre črte predstavljajo majhno število, kot
gremo skozi to spet in

22
00:01:03,300 --> 00:01:07,680
spet primerjavo dveh palic drug poleg
druga v rdeči barvi, bomo zamenjali

23
00:01:07,680 --> 00:01:11,010
Največji in najmanjši če
so v okvari.

24
00:01:11,010 --> 00:01:14,150
>> Tako da bo ta šel naprej in naprej in iti
naprej, in videli boste, da večja

25
00:01:14,150 --> 00:01:16,700
Elementi so svojo pot do
desno in manjše elementi

26
00:01:16,700 --> 00:01:17,900
ki svojo pot na levo.

27
00:01:17,900 --> 00:01:21,380
Vendar pa smo začeli količinsko
učinkovitosti,

28
00:01:21,380 --> 00:01:22,970
Kakovost tega algoritma.

29
00:01:22,970 --> 00:01:25,200
In mi je rekel, da je v najslabšem
primeru ta algoritem je

30
00:01:25,200 --> 00:01:27,940
približno koliko korakov?

31
00:01:27,940 --> 00:01:28,980
>> Torej n kvadrat.

32
00:01:28,980 --> 00:01:30,402
In kaj je bilo n?

33
00:01:30,402 --> 00:01:31,650
>> PUBLIKA: Število elementov.

34
00:01:31,650 --> 00:01:32,790
>> DAVID Malan: Tako je n
število elementov.

35
00:01:32,790 --> 00:01:33,730
In zato bomo to pogosto.

36
00:01:33,730 --> 00:01:36,650
Vsak čas želimo govoriti o velikosti
o problemu ali velikost

37
00:01:36,650 --> 00:01:39,140
vložek, ali koliko časa traja
za izdelavo izhod, bova

38
00:01:39,140 --> 00:01:41,610
posplošena karkoli
Vhod je, kot n.

39
00:01:41,610 --> 00:01:45,970
Torej nazaj v tednu 0, število strani
V telefonskem imeniku je n.

40
00:01:45,970 --> 00:01:47,550
Število študentov
V sobi je bil n.

41
00:01:47,550 --> 00:01:49,630
Torej tudi tu bomo po
da vzorec.

42
00:01:49,630 --> 00:01:52,800
>> Zdaj n kvadrat ni posebej
hitro, zato smo poskušali narediti bolje.

43
00:01:52,800 --> 00:01:55,970
In tako smo si ogledali nekaj
drugi algoritmi, med katerimi

44
00:01:55,970 --> 00:01:57,690
so izbor sort.

45
00:01:57,690 --> 00:01:59,180
Torej, izbira sort je
malo drugačna.

46
00:01:59,180 --> 00:02:03,130
Bilo je skoraj enostavnejša, upam si reči,
s katerim sem začel na začetku

47
00:02:03,130 --> 00:02:06,740
seznam naših prostovoljcev in sem spet
in spet in spet šla skozi

48
00:02:06,740 --> 00:02:10,060
Seznam, skubljenje od najmanjše
element naenkrat in ga dajanje ali

49
00:02:10,060 --> 00:02:13,040
jo na začetku seznama.

50
00:02:13,040 --> 00:02:16,410
>> Ampak tudi to, ko smo začeli razmišljati
s pomočjo matematike in večjo

51
00:02:16,410 --> 00:02:19,860
slika, pomislili kolikokrat
Nameraval sem nazaj in naprej in nazaj

52
00:02:19,860 --> 00:02:24,090
in tja, smo rekli v najslabšem primeru,
izbira sort, preveč, je bilo kaj?

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

54
00:02:24,960 --> 00:02:27,490
Zdaj v resničnem svetu, bi bilo
dejansko nekoliko hitreje.

55
00:02:27,490 --> 00:02:30,620
Ker še enkrat, nisem imel, da
nazadovanja, ko sem razporejene

56
00:02:30,620 --> 00:02:31,880
najmanjši elementi.

57
00:02:31,880 --> 00:02:35,090
Ampak, če razmišljamo o zelo velikem n, in
Če nekako storiti math kot

58
00:02:35,090 --> 00:02:39,170
Jaz sem na krovu, pri čemer n kvadrat
minus nekaj, vse ostalo

59
00:02:39,170 --> 00:02:41,850
poleg n kvadrat, enkrat n
postane zelo velik, ne

60
00:02:41,850 --> 00:02:42,850
res toliko pomembno.

61
00:02:42,850 --> 00:02:45,470
Tako kot računalniški znanstveniki, smo nekako
zamižijo na eno oko, da manjša

62
00:02:45,470 --> 00:02:49,220
dejavniki in se osredotočiti le na faktor v
izraz, ki se dogaja, da

63
00:02:49,220 --> 00:02:50,330
Največja razlika.

64
00:02:50,330 --> 00:02:52,840
>> No, na koncu smo pogledal
ob vstavitvi vrste.

65
00:02:52,840 --> 00:02:56,620
In to je bila podobna v duhu, ampak
namesto skozi ponavljajočim in

66
00:02:56,620 --> 00:03:01,250
izberite najmanjši element enega na
Tokrat sem namesto da bi vzel v roke, da sem

67
00:03:01,250 --> 00:03:04,070
bila obravnavana, in sem se odločil, vse
Dobro, ti spadaš sem.

68
00:03:04,070 --> 00:03:06,160
Potem sem se preselil na naslednji element
in se odločil, da je on ali

69
00:03:06,160 --> 00:03:07,470
je pripadal tukaj.

70
00:03:07,470 --> 00:03:08,810
In potem sem se preselil naprej in naprej.

71
00:03:08,810 --> 00:03:11,780
In mislim, da bi lahko, na poti,
premik te fante, da bi

72
00:03:11,780 --> 00:03:13,030
naredimo prostor za njih.

73
00:03:13,030 --> 00:03:16,880
Tako da je bil neke vrste mentalnega preobrata
od izbire vrste, ki smo

74
00:03:16,880 --> 00:03:18,630
imenovano vstavljanja vrste.

75
00:03:18,630 --> 00:03:20,810
>> Torej te teme, da se pojavijo
v resničnem svetu.

76
00:03:20,810 --> 00:03:23,640
Še pred nekaj leti, ko nekateri
senator je kandidiral za predsednika,

77
00:03:23,640 --> 00:03:27,160
Eric Schmidt je v času uprave
Google, dejansko možnost

78
00:03:27,160 --> 00:03:28,040
z njim razgovor.

79
00:03:28,040 --> 00:03:32,010
In smo mislili delili YouTube
Posnetek zate, če bi lahko zavihati

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

81
00:03:32,950 --> 00:03:39,360
>> [Predvajanje videa]

82
00:03:39,360 --> 00:03:44,620
>> -Zdaj, senator, da ste tukaj na Googlu,
in mi je všeč, da razmišljajo o predsedovanju

83
00:03:44,620 --> 00:03:46,042
kot razgovor za službo.

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

85
00:03:47,770 --> 00:03:50,800
>> -Zdaj je težko dobiti
delo kot predsednik.

86
00:03:50,800 --> 00:03:52,480
In greste skozi
mrzlica zdaj.

87
00:03:52,480 --> 00:03:54,330
Prav tako je težko dobiti službo pri Googlu.

88
00:03:54,330 --> 00:03:59,610
Imamo vprašanja in vprašamo
Naši kandidati vprašanja.

89
00:03:59,610 --> 00:04:02,250
In to je eden od Larry Schwimmer.

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

91
00:04:05,325 --> 00:04:06,400
-Mislite, da se hecam?

92
00:04:06,400 --> 00:04:08,750
To je tukaj.

93
00:04:08,750 --> 00:04:12,110
Kaj je najbolj učinkovit način za
razvrstite milijon dva-bitnih števil?

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

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

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

97
00:04:19,029 --> 00:04:19,745
Morda bi se morali -

98
00:04:19,745 --> 00:04:21,000
>> -Ne, ne, ne, ne, ne.

99
00:04:21,000 --> 00:04:21,470
>> -To ni -

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

101
00:04:22,185 --> 00:04:25,328
>> Mislim, bubble sort bi
biti napačna pot.

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

103
00:04:26,792 --> 00:04:28,510
>> [Vzklikati in aplavz]

104
00:04:28,510 --> 00:04:31,211
>> Daj no, kdo mu je to povedal?

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

106
00:04:32,155 --> 00:04:33,350
>> [END predvajanje videa]

107
00:04:33,350 --> 00:04:35,070
>> DAVID Malan: Torej, tam ga imate.

108
00:04:35,070 --> 00:04:39,600
Tako smo začeli količinsko ti teče
krat, tako rekoč, z nečim

109
00:04:39,600 --> 00:04:43,480
imenovano asimptotska zapis, ki je
se sklicujejo le na naš nekakšen preobrat

110
00:04:43,480 --> 00:04:47,420
slepo oko na tiste manjše dejavnikov in
samo gledaš časa teče,

111
00:04:47,420 --> 00:04:51,250
Izvajanje teh algoritmov,
kot n postane zelo velik daljšem časovnem obdobju.

112
00:04:51,250 --> 00:04:55,110
In tako smo uvedli veliko O. In Big O
predstavlja nekaj, kar smo mislili

113
00:04:55,110 --> 00:04:57,000
od kot zgornja meja.

114
00:04:57,000 --> 00:04:59,570
In dejansko, Barry, lahko znižamo
kot mic malo bit?

115
00:04:59,570 --> 00:05:01,040
>> Mi smo se to je zgornja meja.

116
00:05:01,040 --> 00:05:04,710
Tako velik O izmed n kvadratov pomeni, da v
najslabšem primeru nekaj podobnega

117
00:05:04,710 --> 00:05:07,780
Izbor vrste bi potrebovali
n kvadratov korake.

118
00:05:07,780 --> 00:05:10,310
Ali nekaj takega vstavljanja vrste
bi n kvadrat korakov.

119
00:05:10,310 --> 00:05:15,150
Zdaj pa nekaj podobnega vstavljanje
sort, kar je bilo v najslabšem primeru?

120
00:05:15,150 --> 00:05:18,200
Glede na to, matrika, kaj je najhujše
Možen scenarij, da bi našli

121
00:05:18,200 --> 00:05:20,650
sami soočajo s številnimi partnerji?

122
00:05:20,650 --> 00:05:21,860
>> To je povsem nazaj, kajne?

123
00:05:21,860 --> 00:05:24,530
Ker če je popolnoma nazaj,
moraš narediti cel kup dela.

124
00:05:24,530 --> 00:05:26,420
Ker če ste popolnoma nazaj,
boste našli

125
00:05:26,420 --> 00:05:28,840
Največji dejavnik tukaj, čeprav
spada tja.

126
00:05:28,840 --> 00:05:31,140
Torej boste rekli, v redu, v
Ta trenutek v času, spadaš sem,

127
00:05:31,140 --> 00:05:32,310
tako da ga pusti pri miru.

128
00:05:32,310 --> 00:05:35,425
>> Potem se zavedaš, oh, prekleto, moram
premaknil nekoliko manjši element za

129
00:05:35,425 --> 00:05:36,470
levo od tebe.

130
00:05:36,470 --> 00:05:38,770
Potem moram storiti, da znova
in znova in znova.

131
00:05:38,770 --> 00:05:41,410
In če sem šel naprej in nazaj, si
bi nekako občutek uspešnosti

132
00:05:41,410 --> 00:05:45,540
da algoritem, saj nenehno sem
shuffling vsem ostalim določa

133
00:05:45,540 --> 00:05:46,510
matrika da bi naredili prostor za to.

134
00:05:46,510 --> 00:05:47,750
Tako da je v najslabšem primeru.

135
00:05:47,750 --> 00:05:48,570
>> Nasprotno -

136
00:05:48,570 --> 00:05:50,320
in to je bil Alpinista zadnji čas -

137
00:05:50,320 --> 00:05:54,065
smo rekli, da je vključitev neke
je omega česa?

138
00:05:54,065 --> 00:05:57,530
Kaj je najboljši primer tek
Čas vstavljanja vrste?

139
00:05:57,530 --> 00:05:58,520
Torej je dejansko n.

140
00:05:58,520 --> 00:06:00,980
To je bil prazen, da smo zapustili
na krovu zadnjič.

141
00:06:00,980 --> 00:06:03,160
>> In to je omega n, ker zakaj?

142
00:06:03,160 --> 00:06:06,630
No, v zelo najboljšem primeru, kaj je
vstavljanje sort bodo predali?

143
00:06:06,630 --> 00:06:09,830
No, Seznam, ki je v celoti urejeno
že minimalna delo narediti.

144
00:06:09,830 --> 00:06:12,460
Toda kaj je boljšega pri vstavljanja vrste
je, da zato, ker Tu se začne in

145
00:06:12,460 --> 00:06:15,340
odloči, oh, ti si številka
ena, spadaš sem.

146
00:06:15,340 --> 00:06:16,970
Oh, kakšna sreča.

147
00:06:16,970 --> 00:06:17,740
>> Ti si številka dve.

148
00:06:17,740 --> 00:06:19,030
Prav tako spadajo sem.

149
00:06:19,030 --> 00:06:21,010
Tretjič, še bolje
spadaš sem.

150
00:06:21,010 --> 00:06:25,210
Takoj, ko pride do konca
psevdokoda Seznam Per vstavitve razvrstite v

151
00:06:25,210 --> 00:06:28,010
da smo šli skozi verbalno
zadnji čas, je to storjeno.

152
00:06:28,010 --> 00:06:32,790
Ampak izbira sort, nasprotno,
redno počne kaj?

153
00:06:32,790 --> 00:06:35,260
>> Bo ohranil skozi seznam
spet in spet in spet.

154
00:06:35,260 --> 00:06:39,160
Ker je bil ključni vpogled le
ko ste pogledal vse do

155
00:06:39,160 --> 00:06:42,500
konec seznama, ste lahko prepričani,
da je element izbrano

156
00:06:42,500 --> 00:06:45,560
res trenutno najmanjši element.

157
00:06:45,560 --> 00:06:48,920
Torej ti različni modeli duševno konec
up prinaša nekaj zelo resničnega sveta

158
00:06:48,920 --> 00:06:53,130
razlike za nas, kot tudi ti
teoretične asimptotske razlike.

159
00:06:53,130 --> 00:06:56,910
>> Torej, samo da Rekapitulacija, nato pa velik O n
kvadrat, smo videli nekaj tak

160
00:06:56,910 --> 00:06:58,350
Algoritmi tako daleč.

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

162
00:06:59,580 --> 00:07:02,870
Kaj je algoritem, ki bi lahko
je dejal, da je velik O n?

163
00:07:02,870 --> 00:07:06,930
V najslabšem primeru je potrebno
linearna več korakov.

164
00:07:06,930 --> 00:07:07,810
>> OK, linearno iskanje.

165
00:07:07,810 --> 00:07:10,470
In v najslabšem primeru, če je
element iščeš, ko

166
00:07:10,470 --> 00:07:12,950
uporabi linearno iskanje?

167
00:07:12,950 --> 00:07:14,680
>> OK, v najslabšem primeru,
sploh ni tam.

168
00:07:14,680 --> 00:07:17,000
Ali v drugem najslabšem primeru, to je
vse poti na koncu, ki je

169
00:07:17,000 --> 00:07:18,880
plus ali minus razlika enem koraku.

170
00:07:18,880 --> 00:07:21,180
Torej, na koncu dneva
lahko rečemo, da je linearna.

171
00:07:21,180 --> 00:07:23,910
Big O n bi bilo linearno iskanje,
ker v najslabšem primeru

172
00:07:23,910 --> 00:07:26,610
element sploh ni tam ali pa je
vse poti na koncu.

173
00:07:26,610 --> 00:07:29,370
>> No, veliki O log n.

174
00:07:29,370 --> 00:07:32,760
Nismo govorili zelo podrobno o
to, ampak to smo že videli prej.

175
00:07:32,760 --> 00:07:36,840
Kaj deluje v tako imenovanih logaritemsko
Čas, v najslabšem primeru?

176
00:07:36,840 --> 00:07:38,500
>> Ja, tako binarno iskanje.

177
00:07:38,500 --> 00:07:42,930
In binarno iskanje v najslabšem primeru
morda element nekje v

178
00:07:42,930 --> 00:07:45,640
srednji ali nekje
znotraj polja.

179
00:07:45,640 --> 00:07:48,040
Ampak ti samo zdi, ko vas
razdeli seznam na pol, pri

180
00:07:48,040 --> 00:07:48,940
pol, na pol, na pol.

181
00:07:48,940 --> 00:07:50,200
In potem voila, da je tam.

182
00:07:50,200 --> 00:07:52,500
Ali pa še enkrat, v najslabšem primeru,
sploh ni tam.

183
00:07:52,500 --> 00:07:56,770
Vendar ne veste, da to ni tam
dokler si nekako doseči, da je zadnja

184
00:07:56,770 --> 00:08:00,470
spodaj je večina elementov po prepolovitev
in prepolovitev in prepolovili.

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

186
00:08:01,400 --> 00:08:03,540
Tako smo lahko velik O višini 2, velik O 3.

187
00:08:03,540 --> 00:08:06,260
Kadarkoli le konstantno število,
smo le nekako le poenostaviti

188
00:08:06,260 --> 00:08:07,280
da je velik O 1.

189
00:08:07,280 --> 00:08:10,440
Čeprav če realno, je potrebno
2 ali celo 100 korakov, če je

190
00:08:10,440 --> 00:08:13,680
konstantno število korakov,
smo pravkar rekel veliki O od 1.

191
00:08:13,680 --> 00:08:15,930
Kaj je algoritem, ki je
v veliki O 1?

192
00:08:15,930 --> 00:08:18,350
>> PUBLIKA: Iskanje dolžino
v spremenljivko.

193
00:08:18,350 --> 00:08:21,090
>> DAVID Malan: Iskanje
Dolžina spremenljivke?

194
00:08:21,090 --> 00:08:23,870
>> PUBLIKA: Ne, dolžina
če je to že urejeno.

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

196
00:08:24,160 --> 00:08:27,850
OK, tako da iskanje dolžino nekaj
če dolžina tistega nekaj, kot

197
00:08:27,850 --> 00:08:30,020
matrika, ki je shranjena v nekaterih spremenljivko.

198
00:08:30,020 --> 00:08:33,380
Saj lahko samo prebrati spremenljivko
ali natisniti spremenljivko, ali

199
00:08:33,380 --> 00:08:34,960
samo na splošno dostop do te spremenljivke.

200
00:08:34,960 --> 00:08:37,299
In voila, da se stalno čas.

201
00:08:37,299 --> 00:08:38,909
>> Nasprotno, mislim nazaj na praske.

202
00:08:38,909 --> 00:08:42,460
Misli nazaj v prvem tednu C
kliče samo printf in tiskanje

203
00:08:42,460 --> 00:08:46,240
nekaj, na zaslonu je nedvomno
Časovna konstanta, saj traja le

204
00:08:46,240 --> 00:08:50,880
nekateri število CPE prikazati
da je besedilo na zaslonu.

205
00:08:50,880 --> 00:08:52,720
Ali pa počakajte - to počne?

206
00:08:52,720 --> 00:08:56,430
Kako drugače bi lahko modelirati
uspešnost printf?

207
00:08:56,430 --> 00:09:00,420
Bi kdo rad, da se ne strinjam, da je
Mogoče to ni ravno konstanten čas?

208
00:09:00,420 --> 00:09:03,600
V kakšnem smislu bi lahko printf teče
čas, pravzaprav tiskanje niz na

209
00:09:03,600 --> 00:09:05,580
zaslon, je nekaj
razen konstantna.

210
00:09:05,580 --> 00:09:07,860
>> PUBLIKA: [neslišno].

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

212
00:09:08,230 --> 00:09:09,300
Torej je odvisno od naše perspektive.

213
00:09:09,300 --> 00:09:13,390
Če smo dejansko razmišljati o vlaganju v
printf kot string, in

214
00:09:13,390 --> 00:09:16,380
Zato smo merjenje velikosti, ki
Vhod po svoji dolžini - tako recimo

215
00:09:16,380 --> 00:09:17,780
da dolžina n, kot tudi -

216
00:09:17,780 --> 00:09:21,990
verjetno, printf je sam velik O n
saj se dogaja, da vas n korakov bo

217
00:09:21,990 --> 00:09:24,750
natisniti vsako od teh n
znakov, najverjetneje.

218
00:09:24,750 --> 00:09:27,730
Vsaj do te mere, da prevzame
da morda to je z uporabo zanke for

219
00:09:27,730 --> 00:09:28,560
Pod pokrovom.

220
00:09:28,560 --> 00:09:30,860
>> Vendar pa bi morali gledati, da
kodo razumeti bolje.

221
00:09:30,860 --> 00:09:33,650
In res, ko vi začnete
analizira svoje algoritme, boste

222
00:09:33,650 --> 00:09:34,900
dobesedno ne samo to.

223
00:09:34,900 --> 00:09:37,765
Nekako zrkla svojo kodo, in mislim,
O - vse v redu, imam to zanko

224
00:09:37,765 --> 00:09:41,870
tukaj ali imam ugnezdene zanke tukaj
da bo storil n stvari n-krat,

225
00:09:41,870 --> 00:09:46,050
in lahko razvrstite razuma svojo pot
s kodo, tudi če je

226
00:09:46,050 --> 00:09:47,980
psevdokoda in ne dejanska koda.

227
00:09:47,980 --> 00:09:49,730
>> Torej, kaj pa omega n kvadrat?

228
00:09:49,730 --> 00:09:53,582
Kaj je algoritem, ki v najboljšem
primer, še vedno je n kvadrat koraki?

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

230
00:09:54,014 --> 00:09:54,880
>> PUBLIKA: [neslišno].

231
00:09:54,880 --> 00:09:55,900
>> DAVID Malan: Torej, izbira sort.

232
00:09:55,900 --> 00:09:59,150
Ker v tem problemu res zmanjša
na dejstvo, da spet ne vem

233
00:09:59,150 --> 00:10:02,600
Našel sem trenutno najmanjši dokler
Preveril sem vse darn elemente.

234
00:10:02,600 --> 00:10:08,050
Torej omega, recimo, n smo
pravkar prišel gor z eno.

235
00:10:08,050 --> 00:10:09,300
Vstavitev vrste.

236
00:10:09,300 --> 00:10:12,370
Če je seznam zgodi, da je treba sortirati
že, v najboljšem primeru imamo samo

237
00:10:12,370 --> 00:10:15,090
da en skozi to,
na kateri točki smo prepričani.

238
00:10:15,090 --> 00:10:17,890
Potem, da bi se omenjeni
da je linearna, zagotovo.

239
00:10:17,890 --> 00:10:20,570
>> Kaj pa omega od 1?

240
00:10:20,570 --> 00:10:23,790
Katere, v najboljšem primeru, lahko traja
nespremenjeno število korakov?

241
00:10:23,790 --> 00:10:27,220
Torej linearno iskanje, če si le srečo
in element iščete

242
00:10:27,220 --> 00:10:31,000
je takoj na začetku seznama,
če je to, če ste se začne vaše

243
00:10:31,000 --> 00:10:33,070
Linearni prečkanje navedenega seznama.

244
00:10:33,070 --> 00:10:35,180
>> In to velja za
število stvari.

245
00:10:35,180 --> 00:10:37,660
Na primer, čeprav binarni
Iskanje je omega 1.

246
00:10:37,660 --> 00:10:40,310
Ker kaj pa če dobiš res darn
srečo in zadah-DAB v sredini

247
00:10:40,310 --> 00:10:42,950
tvoj array je številka
iščete?

248
00:10:42,950 --> 00:10:45,730
Tako da boste lahko srečni tam, kot dobro.

249
00:10:45,730 --> 00:10:49,190
>> Ta je, nenazadnje, omega n log n.

250
00:10:49,190 --> 00:10:52,573
Torej n log n, nismo zares
govorimo o še, ampak -

251
00:10:52,573 --> 00:10:53,300
>> PUBLIKA: zlivanjem?

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

253
00:10:53,960 --> 00:10:56,920
To je bil Alpinista zadnjega časa,
kjer smo predlagali, in smo pokazali,

254
00:10:56,920 --> 00:10:58,600
vidno, da so algoritmi.

255
00:10:58,600 --> 00:11:02,470
In združiti vrste samo ena taka
algoritem, ki je bistveno hitrejša

256
00:11:02,470 --> 00:11:03,450
kot nekateri od teh drugih fantov.

257
00:11:03,450 --> 00:11:07,800
Dejstvo je, zliti kratki ne le
Najboljši primer n log n, v najslabšem

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

259
00:11:09,460 --> 00:11:14,540
In ko imate to naključje
omega in velik O počutje isto stvar?

260
00:11:14,540 --> 00:11:17,310
Mi lahko dejansko opiše kot tisto, kar je
imenuje theta, čeprav je

261
00:11:17,310 --> 00:11:18,220
Malo manj pogosti.

262
00:11:18,220 --> 00:11:21,730
Ampak to samo pomeni dve meje,
V tem primeru so enake.

263
00:11:21,730 --> 00:11:25,770
>> Torej zlivanjem, kaj to
Res omejijo na za nas?

264
00:11:25,770 --> 00:11:27,000
No, spomnim motivacijo.

265
00:11:27,000 --> 00:11:30,340
Dovolite mi, dvigni drugo animacijo, da
nismo pogled na zadnjem času.

266
00:11:30,340 --> 00:11:33,390
Ta je, enako zamisel, vendar
to je malo večji.

267
00:11:33,390 --> 00:11:36,160
In jaz grem naprej in poudariti
Prvi - imamo vstavljanja vrste na

268
00:11:36,160 --> 00:11:39,410
zgoraj levo, nato pa izbor sort,
bubble sort, nekaj drugih vrst -

269
00:11:39,410 --> 00:11:42,670
lupine in hitro - da se nismo pogovarjali
o, in kup in zlivanjem.

270
00:11:42,670 --> 00:11:47,090
>> Torej vsaj poskusiti, da se osredotoči na svoje oči
Najboljši trije na levo in nato

271
00:11:47,090 --> 00:11:49,120
zlivanjem ko kliknem
ta zelena puščica.

272
00:11:49,120 --> 00:11:51,900
Ampak bom pustil vse od njih teče, samo da bi
vam občutek raznolikosti

273
00:11:51,900 --> 00:11:53,980
algoritmi, ki obstajajo na svetu.

274
00:11:53,980 --> 00:11:56,180
Bom pustil ta tek
le za nekaj sekund.

275
00:11:56,180 --> 00:11:59,640
In če se osredotočite vaše oči - izberite
algoritem, osredotočiti na to, za samo

276
00:11:59,640 --> 00:12:02,970
sekund - boste začeli videvati
vzorec, ki ga je izvajati.

277
00:12:02,970 --> 00:12:04,530
>> Merge sort, obvestilo, je končano.

278
00:12:04,530 --> 00:12:06,430
Heap sort, hitro urejanje, lupini -

279
00:12:06,430 --> 00:12:09,480
Tako se zdi, smo uvedli tri
Najhujši algoritmi prejšnji teden.

280
00:12:09,480 --> 00:12:12,960
Ampak to je dobro, da smo danes tukaj
poglej zlivanjem, ki je eden od

281
00:12:12,960 --> 00:12:16,500
Lažje tisti je, da pogledamo, čeprav
čeprav bo verjetno bend svoj um

282
00:12:16,500 --> 00:12:17,490
Samo malo.

283
00:12:17,490 --> 00:12:21,130
Tu lahko vidimo, koliko
Izbor vrste zanič.

284
00:12:21,130 --> 00:12:24,600
>> Ampak na flip strani, je
zelo preprosto izvajati.

285
00:12:24,600 --> 00:12:28,160
In morda za P Set 3, ki je eden od
algoritmi ste se odločili za izvedbo

286
00:12:28,160 --> 00:12:28,960
Za standardni različici.

287
00:12:28,960 --> 00:12:30,970
Popolnoma v redu, popolnoma pravilna.

288
00:12:30,970 --> 00:12:35,210
>> Ampak spet, kot n postane velik, če
odločijo za izvajanje hitrejši algoritem

289
00:12:35,210 --> 00:12:39,020
všeč zlivanjem, odds so v večji in
Večje vhodi, vaša koda je le

290
00:12:39,020 --> 00:12:39,800
tekoč teči hitreje.

291
00:12:39,800 --> 00:12:41,090
Vaša spletna stran bo delovala bolje.

292
00:12:41,090 --> 00:12:42,650
Vaši uporabniki se bodo srečnejši.

293
00:12:42,650 --> 00:12:45,280
In tako so ti učinki
dejansko daje

294
00:12:45,280 --> 00:12:47,350
nam nekaj globlje mislil.

295
00:12:47,350 --> 00:12:49,990
>> Torej, vzemimo si oglejte, kaj spajanje
vrsta je pravzaprav vse okoli.

296
00:12:49,990 --> 00:12:52,992
Kul stvar je, da se združi
razvrščanja je samo to.

297
00:12:52,992 --> 00:12:56,300
To je, še enkrat, kaj smo se imenuje
psevdokoda, psevdokoda bitje

298
00:12:56,300 --> 00:12:57,720
Angleško-podobno skladnjo.

299
00:12:57,720 --> 00:12:59,890
In preprostost
nekako zanimivo.

300
00:12:59,890 --> 00:13:02,840
>> Torej, na vhodu n elementov - tako, da
pomeni le, tukaj je polje.

301
00:13:02,840 --> 00:13:04,000
Ima n stvari v njem.

302
00:13:04,000 --> 00:13:05,370
To je vse kar si rekel tam.

303
00:13:05,370 --> 00:13:07,560
>> Če je n manj kot 2, vrne.

304
00:13:07,560 --> 00:13:08,640
Torej to je samo nepomembna zadeva.

305
00:13:08,640 --> 00:13:12,580
Če je n manj kot 2, potem seveda to
1 ali 0, pri čemer stvar

306
00:13:12,580 --> 00:13:14,780
je že razporejene ali ga sploh ni,
tako da samo vrniti.

307
00:13:14,780 --> 00:13:15,900
Ni nič narediti.

308
00:13:15,900 --> 00:13:18,360
Tako da je preprost primer, da drobovja off.

309
00:13:18,360 --> 00:13:20,110
>> Drugje, imamo tri korake.

310
00:13:20,110 --> 00:13:23,650
Razvrstite levo polovico elementov, razvrščanja
desna polovica elementov,

311
00:13:23,650 --> 00:13:26,650
in nato združiti razvrščena polovici.

312
00:13:26,650 --> 00:13:29,400
Zanimivo tukaj je, da
Nekako sem punting, kajne?

313
00:13:29,400 --> 00:13:32,300
Tam je nekako krožno definicijo
na ta algoritem.

314
00:13:32,300 --> 00:13:35,986
V kakšnem smislu je to algoritem je
definicija krožna?

315
00:13:35,986 --> 00:13:37,850
>> PUBLIKA: [neslišno].

316
00:13:37,850 --> 00:13:41,670
>> DAVID Malan: Ja, moj sortiranje algoritem,
dveh njegovih korakov "neke

317
00:13:41,670 --> 00:13:44,640
nekaj podobnega. "In tako, da Zastavlja
Vprašanje, no, kaj bom uporabila

318
00:13:44,640 --> 00:13:46,460
razvrstiti levo polovico
in desna polovica?

319
00:13:46,460 --> 00:13:49,600
In lepota tukaj je, da čeprav
še enkrat, to je um-upogibni

320
00:13:49,600 --> 00:13:54,030
del potencialno lahko uporabite isto
algoritem za razvrščanje levo polovico.

321
00:13:54,030 --> 00:13:54,700
>> Toda počakaj malo.

322
00:13:54,700 --> 00:13:57,070
Ko ste povedali, da razvrstite
leva polovica, kar sta dva

323
00:13:57,070 --> 00:13:58,240
korake bo naslednji?

324
00:13:58,240 --> 00:14:00,550
Bomo razvrstite levo polovico
levo polovico in desno

325
00:14:00,550 --> 00:14:01,420
polovica levo polovico.

326
00:14:01,420 --> 00:14:04,430
Prekleto, kako rešiti ta dva
polovice ali četrtine, zdaj?

327
00:14:04,430 --> 00:14:05,260
>> Ampak to je v redu.

328
00:14:05,260 --> 00:14:07,830
Imamo razvrščanja algoritem tukaj.

329
00:14:07,830 --> 00:14:10,660
In čeprav boste morda skrbi,
Prvi je to nekako neskončno

330
00:14:10,660 --> 00:14:12,780
zanke, da je cikel, ki je nikoli
bo na koncu - da se bo

331
00:14:12,780 --> 00:14:15,770
na koncu enkrat, kaj se zgodi?

332
00:14:15,770 --> 00:14:16,970
Ko je n manj kot 2.

333
00:14:16,970 --> 00:14:19,180
Ki sčasoma se bo zgodilo,
ker če boste obdržali prepolovi in

334
00:14:19,180 --> 00:14:23,020
prepolovitev v prepolovitev te polčasih, zagotovo
sčasoma boš do konca

335
00:14:23,020 --> 00:14:25,350
s samo 1 ali 0 elementov.

336
00:14:25,350 --> 00:14:28,500
Tedaj je ta algoritem
pravi, da ste končali.

337
00:14:28,500 --> 00:14:31,020
>> Torej resnično čarobno v tem
Algoritem Zdi se, da

338
00:14:31,020 --> 00:14:33,470
da je zadnji korak, ki združuje.

339
00:14:33,470 --> 00:14:37,190
Ta preprosta ideja, samo združitev dveh
Stvari, da je tisto, kar je v končni fazi bo

340
00:14:37,190 --> 00:14:40,920
nam omogočajo, da razvrstite niz,
recimo, osem elementov.

341
00:14:40,920 --> 00:14:44,410
Torej imam osem več stresa Jajca
Tu je osem koščke in eno

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

343
00:14:45,500 --> 00:14:46,140
ki lahko obdržim.

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

345
00:14:46,960 --> 00:14:48,970
>> DAVID Malan: Če bi lahko traja osem
prostovoljci, in da vidimo, če lahko

346
00:14:48,970 --> 00:14:51,430
igrati to ven, tako.

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

348
00:14:52,500 --> 00:14:53,565
Računalništvo postaja zabavno.

349
00:14:53,565 --> 00:14:54,320
Vse je v redu.

350
00:14:54,320 --> 00:14:57,770
Torej, kaj pa vi trije,
Največji roko gor.

351
00:14:57,770 --> 00:14:58,580
Štiri zadaj.

352
00:14:58,580 --> 00:15:02,220
Kaj pa vam bomo narediti
trije v tej vrsti?

353
00:15:02,220 --> 00:15:03,390
In štiri v ospredju.

354
00:15:03,390 --> 00:15:04,920
Torej si osem, pridi gor.

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

356
00:15:12,060 --> 00:15:13,450
>> DAVID Malan: Jaz sem pravzaprav
Ne vem, kaj je.

357
00:15:13,450 --> 00:15:14,810
Je obremenilne kroglice?

358
00:15:14,810 --> 00:15:16,510
Mizi svetilke?

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

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

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

362
00:15:20,160 --> 00:15:21,310
Torej, pridi gor.

363
00:15:21,310 --> 00:15:22,310
Kdo bi rad -

364
00:15:22,310 --> 00:15:23,570
naprej prihajajo.

365
00:15:23,570 --> 00:15:24,240
Poglejmo.

366
00:15:24,240 --> 00:15:26,460
In to vas postavlja v mestu -

367
00:15:26,460 --> 00:15:27,940
ste v eni lokaciji.

368
00:15:27,940 --> 00:15:28,670
Uh, počakaj malo.

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

370
00:15:30,760 --> 00:15:31,310
Vse je v redu, smo dobri.

371
00:15:31,310 --> 00:15:35,130
Vse je v redu, tako da vsi imajo sedež,
vendar ne na Google Glass.

372
00:15:35,130 --> 00:15:36,475
Dovolite mi, da čakalne vrste te gor.

373
00:15:36,475 --> 00:15:37,115
Kako ti je ime?

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
Vse je v redu, boste dobili izgledal
geek, če je to v redu.

377
00:15:42,000 --> 00:15:44,625
No, jaz tudi mislim,
le za trenutek.

378
00:15:44,625 --> 00:15:45,875
Vse je v redu, v pripravljenosti.

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

380
00:15:48,510 --> 00:15:50,950
Smo bili poskuša dohiteti
primera uporabe za Google Glass, in smo

381
00:15:50,950 --> 00:15:53,750
mislil, da bi bilo zabavno, da pač
to, ko so ljudje na odru.

382
00:15:53,750 --> 00:15:57,120
Snemali bomo svet
iz njihove perspektive.

383
00:15:57,120 --> 00:15:58,410
Vse je v redu.

384
00:15:58,410 --> 00:15:59,830
Ni verjetno, kaj Google je bilo predvideno.

385
00:15:59,830 --> 00:16:02,260
Vse je v redu, če vas ne moti nošenja
to v naslednjih neugodnih minut

386
00:16:02,260 --> 00:16:03,150
da bi bilo čudovito.

387
00:16:03,150 --> 00:16:08,620
>> Vse je v redu, tako da imamo tu niz
elemente, in da matrike, kot na

388
00:16:08,620 --> 00:16:11,480
Lističe v te ljudi '
Roke, ki je trenutno nesortirani.

389
00:16:11,480 --> 00:16:12,050
>> MICHELLE: Oh, to je tako čudno.

390
00:16:12,050 --> 00:16:12,810
>> DAVID Malan: To je precej naključno.

391
00:16:12,810 --> 00:16:15,760
In čez nekaj trenutkov, da bomo poskušali
izvajati zlivanjem skupaj

392
00:16:15,760 --> 00:16:17,950
in videli, kje je ključ uvid je.

393
00:16:17,950 --> 00:16:21,970
In Trik z zlivanjem je
nekaj, kar še nismo prevzel.

394
00:16:21,970 --> 00:16:24,030
Smo dejansko potrebovali nekaj
dodaten prostor.

395
00:16:24,030 --> 00:16:26,650
Torej, kaj se dogaja, še posebej
Zanimivo je to, da so ti

396
00:16:26,650 --> 00:16:29,270
Fantje se bodo za premikanje malo
bit, ker bom za domnevo, da

397
00:16:29,270 --> 00:16:31,880
tam je dodatno polje prostora,
recimo, takoj za njimi.

398
00:16:31,880 --> 00:16:34,570
>> Torej, če si za svojega predsednika,
To je sekundarna polje.

399
00:16:34,570 --> 00:16:36,960
Če jih tukaj sedijo, da je
primarno polje.

400
00:16:36,960 --> 00:16:40,170
Ampak to je vir, ki ga imamo
Ne vzvodom doslej z mehurčkom

401
00:16:40,170 --> 00:16:42,040
vrsta z izbiro vrste,
z vstavljanja vrste.

402
00:16:42,040 --> 00:16:44,600
Spomnimo, prejšnji teden, vsi le
nekako premešan v mestu.

403
00:16:44,600 --> 00:16:46,840
Niso uporabljajte dodatnega pomnilnika.

404
00:16:46,840 --> 00:16:49,310
Smo naredili prostor za ljudi, ki jih
premikanje ljudi okoli.

405
00:16:49,310 --> 00:16:50,580
>> Tako da je to ključno spoznanje, preveč.

406
00:16:50,580 --> 00:16:53,410
Tam je to kompromis, na splošno v
računalništva, sredstev.

407
00:16:53,410 --> 00:16:55,800
Če želite pospešiti nekaj
kot čas, boste

408
00:16:55,800 --> 00:16:56,900
morali plačati ceno.

409
00:16:56,900 --> 00:17:00,750
In eden od teh cen zelo pogosto
prostor, količino pomnilnika ali trdega

410
00:17:00,750 --> 00:17:01,700
prostora na disku, ki ga uporabljate.

411
00:17:01,700 --> 00:17:03,640
Ali pa, odkrito povedano, znesek
časa programer.

412
00:17:03,640 --> 00:17:06,700
Koliko časa vam bo, človek,
dejansko izvajanje nekaterih bolj

413
00:17:06,700 --> 00:17:07,829
zapleten algoritem.

414
00:17:07,829 --> 00:17:09,760
Ampak za danes, kompromis
je čas in prostor.

415
00:17:09,760 --> 00:17:11,930
>> Torej, če bi vidva Dvigni
številke, tako da bomo lahko videli, da ste

416
00:17:11,930 --> 00:17:15,839
dejansko ujemanje 4, 2, 6, 1, 3, 7, 8.

417
00:17:15,839 --> 00:17:16,599
Odlično.

418
00:17:16,599 --> 00:17:19,520
Torej bom poskusil orkester
stvari, lahko, če vidva

419
00:17:19,520 --> 00:17:21,800
sledite mi tukaj.

420
00:17:21,800 --> 00:17:26,650
>> Torej bom izvajala, prvič,
Prvi korak psevdokoda, ki je

421
00:17:26,650 --> 00:17:29,440
o vnosu n elementov, če je n
manj kot 2 in spet.

422
00:17:29,440 --> 00:17:31,370
Očitno je, da ne
uporabljata tako da gremo naprej.

423
00:17:31,370 --> 00:17:33,340
Torej razvrstite levo polovico elementov.

424
00:17:33,340 --> 00:17:36,220
Torej to pomeni, da bom osredotočil moja
pozornost za trenutek na to

425
00:17:36,220 --> 00:17:37,310
Štirje fantje tukaj.

426
00:17:37,310 --> 00:17:39,774
V redu, kaj moram storiti naslednji?

427
00:17:39,774 --> 00:17:40,570
>> PUBLIKA: Razvrstite levo polovico.

428
00:17:40,570 --> 00:17:42,780
>> DAVID Malan: Torej, zdaj moram rešiti
leva polovica od teh fantov.

429
00:17:42,780 --> 00:17:45,580
Ker je spet prevzel nase v
Cilj je, da razvrstite levo polovico.

430
00:17:45,580 --> 00:17:46,440
Kako si to naredil?

431
00:17:46,440 --> 00:17:49,140
Preprosto sledite navodilom, čeprav
čeprav smo to počeli še enkrat.

432
00:17:49,140 --> 00:17:50,160
Torej razvrstite levo polovico.

433
00:17:50,160 --> 00:17:52,030
Zdaj sem razvrščanje teh dveh fantov.

434
00:17:52,030 --> 00:17:53,563
Kaj sledi?

435
00:17:53,563 --> 00:17:54,510
>> PUBLIKA: Razvrstite levo polovico.

436
00:17:54,510 --> 00:17:55,460
>> DAVID Malan: Razvrščanje levo polovico.

437
00:17:55,460 --> 00:18:00,680
Torej, zdaj ti, ta stol tukaj
je seznam velikosti 1.

438
00:18:00,680 --> 00:18:01,365
In kaj ti je že ime?

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

440
00:18:02,390 --> 00:18:03,690
>> DAVID Malan: Princesa Daisy je tukaj.

441
00:18:03,690 --> 00:18:07,470
In tako se je že urejeno, ker
Seznam je velikosti 1.

442
00:18:07,470 --> 00:18:09,490
Kaj moram storiti naslednji?

443
00:18:09,490 --> 00:18:13,680
OK, vrniti, ker ta seznam je
velikost 1, ki je manjša od 2.

444
00:18:13,680 --> 00:18:14,320
Potem, kaj je naslednji korak?

445
00:18:14,320 --> 00:18:17,490
In zdaj moraš nekako
Vrniti v tvoji glavi.

446
00:18:17,490 --> 00:18:19,340
>> Razvrstite desne polovice, ki je -

447
00:18:19,340 --> 00:18:19,570
Kako ti je ime?

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
In kaj naj storimo zdaj,
imamo seznam velikosti 1?

451
00:18:23,210 --> 00:18:24,440
>> PUBLIKA: Nazaj.

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

453
00:18:24,760 --> 00:18:29,540
Vračamo prvi, zdaj tretja
korak - in če sem nekako ga opisujejo z

454
00:18:29,540 --> 00:18:33,490
zajema dva sedeža zdaj, zdaj sem
ima združevanje teh dveh elementov.

455
00:18:33,490 --> 00:18:35,530
Torej, zdaj žal, elementi
so v okvari.

456
00:18:35,530 --> 00:18:39,920
Ampak to je, če proces združevanja
začne, da se prepričljivi.

457
00:18:39,920 --> 00:18:42,410
>> Torej, če bi vi stand up za samo
Trenutek, bom te potrebujem, v

458
00:18:42,410 --> 00:18:44,170
Trenutek, da stopite na stol.

459
00:18:44,170 --> 00:18:46,480
In če Linda, ker 2 je
manjše od 4, zakaj ne

460
00:18:46,480 --> 00:18:48,130
ste prišli okoli prvi?

461
00:18:48,130 --> 00:18:48,690
Ostanite tam.

462
00:18:48,690 --> 00:18:50,520
Torej Linda, prideš okoli prvi.

463
00:18:50,520 --> 00:18:53,820
>> Zdaj v resnici, če je le niz
smo jo lahko samo premaknete v realnem času

464
00:18:53,820 --> 00:18:55,360
iz tega stola na tem mestu.

465
00:18:55,360 --> 00:18:57,770
Torej, si predstavljajte, da je nekaj konstanta
število korakov 1.

466
00:18:57,770 --> 00:18:58,480
In zdaj -

467
00:18:58,480 --> 00:19:01,490
vendar vas moramo postaviti v
Na prvem mestu so tukaj.

468
00:19:01,490 --> 00:19:03,930
>> In zdaj, če bi prišel okoli,
kot tudi, da bomo

469
00:19:03,930 --> 00:19:06,300
v mestu dveh.

470
00:19:06,300 --> 00:19:09,120
In čeprav se to zdi, kot da je
pri čemer nekaj časa, kaj je zdaj lepo je

471
00:19:09,120 --> 00:19:14,710
da leva polovica
leva polovica je sedaj urejeno.

472
00:19:14,710 --> 00:19:18,010
Torej, kaj je naslednji korak, če bomo zdaj
še nazaj v zgodbi?

473
00:19:18,010 --> 00:19:18,980
>> PUBLIKA: Pravica pol.

474
00:19:18,980 --> 00:19:19,900
>> DAVID Malan: Razvrščanje desne polovice.

475
00:19:19,900 --> 00:19:21,320
Torej vidva to morali storiti, kot dobro.

476
00:19:21,320 --> 00:19:23,510
Torej, če bi lahko vstane
za trenutek?

477
00:19:23,510 --> 00:19:25,192
In kako ti je ime?

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

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

480
00:19:25,870 --> 00:19:29,720
OK, Jess je zdaj levo
polovici desni polovici.

481
00:19:29,720 --> 00:19:31,400
In tako da je seznam velikosti 1.

482
00:19:31,400 --> 00:19:32,380
Ona je očitno razporejene.

483
00:19:32,380 --> 00:19:33,070
In tvoje ime?

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

485
00:19:33,630 --> 00:19:35,340
>> DAVID Malan: Michelle je očitno
Seznam velikosti 1.

486
00:19:35,340 --> 00:19:36,050
Ona je že urejeno.

487
00:19:36,050 --> 00:19:38,690
Torej, zdaj se zgodi čarovnija,
Postopek združevanja.

488
00:19:38,690 --> 00:19:39,790
Torej, kdo bo prvi prišel?

489
00:19:39,790 --> 00:19:41,560
Očitno Michelle.

490
00:19:41,560 --> 00:19:43,280
Torej, če bi lahko prišel od zadaj.

491
00:19:43,280 --> 00:19:47,090
Prostor imamo na razpolago za njo zdaj
je takoj za tem stolu tukaj.

492
00:19:47,090 --> 00:19:51,580
In zdaj, če bi lahko prišel nazaj, kot tudi,
imamo zdaj, da bo jasno, dva

493
00:19:51,580 --> 00:19:53,810
polovičke, vsaka velikosti 2 -

494
00:19:53,810 --> 00:19:57,090
in samo zavoljo upodobitev je, če
bi lahko malo prostora -

495
00:19:57,090 --> 00:19:59,780
eden levo polovico tu ena
desna polovica tukaj.

496
00:19:59,780 --> 00:20:01,160
>> Še previti v zgodbi.

497
00:20:01,160 --> 00:20:02,270
Kaj je naslednji korak?

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

499
00:20:03,030 --> 00:20:04,160
>> DAVID Malan: Zdaj moramo združiti.

500
00:20:04,160 --> 00:20:07,490
Torej OK, zdaj, na srečo smo
pravkar sprostila štiri stole.

501
00:20:07,490 --> 00:20:11,480
Tako smo dvakrat uporablja toliko pomnilnika, vendar
lahko damo flip-flopping med

502
00:20:11,480 --> 00:20:12,330
dveh nizov.

503
00:20:12,330 --> 00:20:14,190
Torej, katera številka je na prvem mestu?

504
00:20:14,190 --> 00:20:14,850
Torej Michelle, seveda.

505
00:20:14,850 --> 00:20:16,680
Tako da pridejo okoli in se
vaš sedež tukaj.

506
00:20:16,680 --> 00:20:19,120
In potem številka 2, je očitno
naslednji, tako da boste prišli sem.

507
00:20:19,120 --> 00:20:21,520
Številka 4, številka 6.

508
00:20:21,520 --> 00:20:23,390
In še enkrat, čeprav je
Malo hoje sodeluje,

509
00:20:23,390 --> 00:20:26,010
res, bi to lahko zgodi v trenutku,
s premikanjem enega -

510
00:20:26,010 --> 00:20:26,880
V redu, dobro igral.

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

512
00:20:28,350 --> 00:20:29,680
>> DAVID Malan: In zdaj smo
je v dobrem stanju.

513
00:20:29,680 --> 00:20:34,910
Levo polovico celotnega
Vhod je sedaj urejeno.

514
00:20:34,910 --> 00:20:37,370
Vse je v redu, tako da so ti ljudje imeli
Prednost mojega -

515
00:20:37,370 --> 00:20:40,340
kako se je na koncu vse punce na
levo in vsi fantje na desni strani?

516
00:20:40,340 --> 00:20:42,450
>> OK, torej 'fantje pa zdaj.

517
00:20:42,450 --> 00:20:44,680
Torej vas ne bo sprehod skozi
ti koraki.

518
00:20:44,680 --> 00:20:46,550
Bomo videli, če bomo lahko znova
Enako psevdokoda.

519
00:20:46,550 --> 00:20:50,050
Če želite, da gredo naprej in stand up,
in vi, mi vam mic.

520
00:20:50,050 --> 00:20:52,990
Glej, če ne morete ponoviti, kar
smo pravkar naredil tukaj na

521
00:20:52,990 --> 00:20:53,880
Drugi konec seznama.

522
00:20:53,880 --> 00:20:59,530
Kdo mora govoriti najprej
ki temelji na algoritmu?

523
00:20:59,530 --> 00:21:03,210
Torej, razloži, kaj delaš, preden
kar koli stopala gibe.

524
00:21:03,210 --> 00:21:05,930
>> SPEAKER 1: V redu, torej od leta
Sem levo polovico

525
00:21:05,930 --> 00:21:07,790
levo polovico, se bom vrnil.

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

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

528
00:21:09,250 --> 00:21:10,350
>> SPEAKER 1: In potem -

529
00:21:10,350 --> 00:21:11,800
>> DAVID Malan: Komu
mic iti naprej?

530
00:21:11,800 --> 00:21:12,920
>> SPEAKER 1: Naslednja številka.

531
00:21:12,920 --> 00:21:14,720
>> ZVOČNIK 2: Torej, jaz sem desna polovica
na levi polovici

532
00:21:14,720 --> 00:21:17,830
levo polovico, in se bom vrnil.

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

534
00:21:18,050 --> 00:21:18,550
Vrnete.

535
00:21:18,550 --> 00:21:21,855
Torej, zdaj, kaj je naslednje na vrsti za vaju?

536
00:21:21,855 --> 00:21:23,740
>> ZVOČNIK 2: Želimo videti, kdo je manjši.

537
00:21:23,740 --> 00:21:24,200
>> DAVID Malan: Točno tako.

538
00:21:24,200 --> 00:21:24,940
Želimo, da se združijo.

539
00:21:24,940 --> 00:21:27,590
Prostor bomo uporabili za spajanje
, čeprav oni so si v

540
00:21:27,590 --> 00:21:30,250
očitno že razporejene, bomo
da sledijo isti algoritem.

541
00:21:30,250 --> 00:21:31,560
Torej, kdo gre v prvi nazaj?

542
00:21:31,560 --> 00:21:35,720
Torej 3, nato 7.

543
00:21:35,720 --> 00:21:38,570
In zdaj mic gre
s temi fanti, OK?

544
00:21:38,570 --> 00:21:43,590
>> ZVOČNIK 3: Zato sem desno polovico
levo polovico in moj je n manj kot

545
00:21:43,590 --> 00:21:45,048
1, tako da sem šele tekoč prehod -

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

547
00:21:46,380 --> 00:21:49,450
>> ZVOČNIK 4: Sem prav polovica
desno polovico desne polovice, in sem

548
00:21:49,450 --> 00:21:51,740
tudi ena oseba, zato sem
vrača.

549
00:21:51,740 --> 00:21:52,990
Torej, zdaj smo spojiti.

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

551
00:21:55,140 --> 00:21:56,150
>> ZVOČNIK 3: Torej gremo nazaj.

552
00:21:56,150 --> 00:21:57,160
>> DAVID Malan: Torej, greš v hrbet.

553
00:21:57,160 --> 00:21:59,200
Torej 5 gre, potem 8.

554
00:21:59,200 --> 00:22:01,240
In zdaj občinstvo, ki je
korak moramo sedaj nazaj

555
00:22:01,240 --> 00:22:02,200
nazaj v naših glavah?

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

557
00:22:02,940 --> 00:22:07,270
>> DAVID Malan: Združitev levo in desno polovico
polovico začetne levo polovico.

558
00:22:07,270 --> 00:22:08,840
Torej, zdaj -

559
00:22:08,840 --> 00:22:10,520
in samo, da bi to jasno,
narediti malo prostora

560
00:22:10,520 --> 00:22:11,690
med vami dva fanta.

561
00:22:11,690 --> 00:22:13,800
Torej sedaj, da je na dveh seznamih,
levo in desno.

562
00:22:13,800 --> 00:22:18,320
Torej, kako bomo zdaj spajanju fantje v
prednja vrsta sedežev spet?

563
00:22:18,320 --> 00:22:19,600
>> 3. gre prvi.

564
00:22:19,600 --> 00:22:20,850
Potem 5, seveda.

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

566
00:22:23,110 --> 00:22:27,330
Potem 7. in 8. sedaj.

567
00:22:27,330 --> 00:22:28,710
OK, zdaj smo?

568
00:22:28,710 --> 00:22:29,650
>> PUBLIKA: Ni storiti.

569
00:22:29,650 --> 00:22:32,440
>> DAVID Malan: Ni storiti, ker
Očitno je, da je ostala korak.

570
00:22:32,440 --> 00:22:35,720
Ampak še enkrat, zato sem z uporabo tega
žargon, kot je "previjanju v tvoji glavi,"

571
00:22:35,720 --> 00:22:37,160
to je zato, ker je to res
kaj se dogaja.

572
00:22:37,160 --> 00:22:39,610
Gremo skozi vse te korake,
vendar smo nekako premori za

573
00:22:39,610 --> 00:22:42,480
Trenutek, potapljanje globlje
algoritem, premori za trenutek,

574
00:22:42,480 --> 00:22:45,840
potapljanje globlje v algoritem, in
Zdaj moramo nekako previjanju v našem

575
00:22:45,840 --> 00:22:49,430
možgane in razveljaviti vse te plasti
da smo nekako na čakanju.

576
00:22:49,430 --> 00:22:51,790
>> Torej, zdaj imamo dva seznama velikosti 4.

577
00:22:51,790 --> 00:22:54,790
Če bi vidva stand up še zadnjič
in da malo prostora tukaj

578
00:22:54,790 --> 00:22:57,230
jasno, da je to levo
polovica original,

579
00:22:57,230 --> 00:22:58,620
desna polovica od originala.

580
00:22:58,620 --> 00:23:01,060
Kdo je prva številka, ki smo
morali potegniti v zadnji?

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

582
00:23:01,870 --> 00:23:03,230
>> Tako da smo dal Michelle tukaj.

583
00:23:03,230 --> 00:23:05,080
In kdo ima številko 2?

584
00:23:05,080 --> 00:23:06,440
Številka 2 prihaja na hrbtni strani, kot dobro.

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

586
00:23:07,800 --> 00:23:08,510
Odlično.

587
00:23:08,510 --> 00:23:16,570
Številka 4, številka 5, številka 6,
številka 7 in številka 8.

588
00:23:16,570 --> 00:23:18,850
>> OK, tako da se mu je zdelo, kot veliko
korakov, zagotovo.

589
00:23:18,850 --> 00:23:22,390
Zdaj pa da vidimo, če ne moremo potrditi,
nekako intuitivno, da je to

590
00:23:22,390 --> 00:23:26,190
algoritem bistveno, zlasti
n postane zelo velik, kot smo videli

591
00:23:26,190 --> 00:23:29,170
z animacijami, je
bistveno hitreje.

592
00:23:29,170 --> 00:23:33,400
Torej Trdim ta algoritem, v najslabšem
primera in tudi v najboljšem primeru

593
00:23:33,400 --> 00:23:36,160
je velik O n-krat log n.

594
00:23:36,160 --> 00:23:39,160
To pomeni, da je nekaj vidik tega
algoritem, ki bo n korake, vendar

595
00:23:39,160 --> 00:23:43,110
obstaja še en vidik nekje
da ponovitev, da se zanka, ki

596
00:23:43,110 --> 00:23:44,410
je log n korakih.

597
00:23:44,410 --> 00:23:49,154
Lahko vam bo naš prst na tisto, ki
dve številki se nanaša?

598
00:23:49,154 --> 00:23:51,320
No, če -

599
00:23:51,320 --> 00:23:54,160
kam mic iti?

600
00:23:54,160 --> 00:23:58,660
>> SPEAKER 1: Bi se bo n
nas razpada na dva dela -

601
00:23:58,660 --> 00:23:59,630
delimo z dve, v bistvu.

602
00:23:59,630 --> 00:24:00,120
>> DAVID Malan: Točno tako.

603
00:24:00,120 --> 00:24:03,000
Vsak čas bomo videli v nobenem algoritmu s tem
sedaj je bilo to vzorec

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

605
00:24:04,200 --> 00:24:05,700
In to je običajno zmanjša
za nekaj, kar je

606
00:24:05,700 --> 00:24:07,100
logaritemska osnova dnevnik 2.

607
00:24:07,100 --> 00:24:10,180
Vendar pa bi res lahko karkoli,
pa se prijavite osnove 2.

608
00:24:10,180 --> 00:24:11,330
>> Zdaj kaj pa n?

609
00:24:11,330 --> 00:24:14,550
Vidim, da smo nekako ti razdeljeni
Fantje - ti razdeljen, razdeljen vas,

610
00:24:14,550 --> 00:24:15,910
ti deli, razdeljeni vas.

611
00:24:15,910 --> 00:24:18,760
Kje pa konec prišel?

612
00:24:18,760 --> 00:24:19,810
>> Torej je združevanje.

613
00:24:19,810 --> 00:24:20,610
Ker razmišljam o tem.

614
00:24:20,610 --> 00:24:25,420
Ko se združi osem ljudi skupaj,
pri čemer polovica jih je sklop štirih

615
00:24:25,420 --> 00:24:27,770
, druga polovica pa so drugi
Komplet štirih, kako si šel

616
00:24:27,770 --> 00:24:28,820
o tem združevanje?

617
00:24:28,820 --> 00:24:30,830
No, vidva to storila
precej intuitivno.

618
00:24:30,830 --> 00:24:34,140
>> Ampak, če sem to storil namesto malo več
metodično, morda sem opozoril na

619
00:24:34,140 --> 00:24:38,090
skrajno levo oseba najprej moja leva
roko, opozoril na skrajno levo osebe

620
00:24:38,090 --> 00:24:42,080
od tega polovica s svojo desno roko, in
šele nato šel skozi

621
00:24:42,080 --> 00:24:46,990
Seznam, ki kaže na najmanjši element
vsakič, premikanje moj prst in čez

622
00:24:46,990 --> 00:24:48,970
po potrebi po seznamu.

623
00:24:48,970 --> 00:24:51,890
Ampak kaj je ključna za to združitev
Postopek je jaz primerjavi teh parov

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

625
00:24:53,460 --> 00:24:57,270
Na desni polovici in z leve
pol, jaz niti enkrat nazadovanja.

626
00:24:57,270 --> 00:25:00,570
>> Torej sama spajanje je ob
ne več kot n korakov.

627
00:25:00,570 --> 00:25:03,250
In kolikokrat si moram
storiti, da bi bila združitev?

628
00:25:03,250 --> 00:25:07,150
No, ne več kot n, in smo pravkar
videl, da s končnim spajanje.

629
00:25:07,150 --> 00:25:13,120
In tako, če narediš nekaj, kar traja
log n korakih n-krat, ali obratno,

630
00:25:13,120 --> 00:25:15,210
to se dogaja, da nam n-krat log n.

631
00:25:15,210 --> 00:25:16,310
>> In zakaj je to bolje?

632
00:25:16,310 --> 00:25:19,600
No, če smo že vedeli, da je dnevnik
n je bolje kot n - kajne?

633
00:25:19,600 --> 00:25:22,590
Videli smo v binarnem iskanju, telefonski imenik
Na primer, log n je definitivno

634
00:25:22,590 --> 00:25:23,760
bolje kot linearna.

635
00:25:23,760 --> 00:25:28,420
To pomeni n-krat log n
definitivno boljše kot n-krat drugo

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

637
00:25:30,390 --> 00:25:32,400
In to je tisto, kar na koncu občutek.

638
00:25:32,400 --> 00:25:34,928
>> Tako velik aplavz, če
smo lahko za te fante.

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

640
00:25:38,920 --> 00:25:41,550
>> DAVID Malan: In tvoji Razdjeljak darila -
lahko obdržali število,

641
00:25:41,550 --> 00:25:44,010
če bi želeli.

642
00:25:44,010 --> 00:25:45,620
In tvoj slovo darilo, kot ponavadi.

643
00:25:45,620 --> 00:25:47,290
Oh, in smo vam bo poslal
posnetkov, Michelle.

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

645
00:25:48,343 --> 00:25:49,250
Vse je v redu.

646
00:25:49,250 --> 00:25:50,400
Pomagaj si na stres žogo.

647
00:25:50,400 --> 00:25:54,110
>> In mi potegnite navzgor, v tem času,
naš prijatelj Rob Bowden, da ponudijo

648
00:25:54,110 --> 00:25:59,520
nekoliko drugačen pogled na to,
saj si lahko misliš o teh

649
00:25:59,520 --> 00:26:01,280
koraki dogaja v nekoliko
drugačen način.

650
00:26:01,280 --> 00:26:04,750
V resnici, set-up za to, kar je približno Rob
da nam pokaže, predpostavlja, da smo jih

651
00:26:04,750 --> 00:26:09,030
že storili tako sestavljajo
velik seznam na osem manjših seznamov,

652
00:26:09,030 --> 00:26:10,570
vsaka od velikosti 1.

653
00:26:10,570 --> 00:26:13,350
>> Torej smo spreminja psevdokoda
malo samo da nekako priti na

654
00:26:13,350 --> 00:26:15,320
Osnovna ideja o tem, kako združuje dela.

655
00:26:15,320 --> 00:26:17,600
Toda čas kaj teče
on je na tem, da je še vedno

656
00:26:17,600 --> 00:26:19,110
bo enaka.

657
00:26:19,110 --> 00:26:23,540
In spet, set-up tukaj je, da je on
začeli z osmimi sezname velikosti 1.

658
00:26:23,540 --> 00:26:27,730
Torej ste zamudili del, kjer se je
dejansko opravljeno log n, log n, log n

659
00:26:27,730 --> 00:26:31,205
delitvijo na vhodu.

660
00:26:31,205 --> 00:26:32,120
>> [Predvajanje videa]

661
00:26:32,120 --> 00:26:33,615
>> -To je to za en korak je.

662
00:26:33,615 --> 00:26:38,270
Za drugi korak, večkrat
združi pare seznamov.

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

664
00:26:39,210 --> 00:26:41,270
Samo zvok prihaja
iz mojega računalnika.

665
00:26:41,270 --> 00:26:42,520
Dajmo še enkrat poskusiti.

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

667
00:26:45,330 --> 00:26:48,310
>> -Samo samovoljno izbirati, katere -
Zdaj imamo štiri sezname.

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

669
00:26:51,590 --> 00:26:52,120
Naučite prej.

670
00:26:52,120 --> 00:26:53,040
>> DAVID Malan: Takole.

671
00:26:53,040 --> 00:27:00,510
>> Združitev-108 in 15, smo na koncu
s seznama 15, 108.

672
00:27:00,510 --> 00:27:07,170
Združitev 50 in 4, smo
končajo s 4, 50.

673
00:27:07,170 --> 00:27:12,990
Združitev 8 in 42, smo
končajo z 8, 42.

674
00:27:12,990 --> 00:27:19,970
In združitvijo 23 in 16, smo
na koncu z 16., 23..

675
00:27:19,970 --> 00:27:23,270
>> Zdaj vsi naši seznami velikosti 2.

676
00:27:23,270 --> 00:27:26,690
Opazili, da vsak
štirje seznami so razvrščeni.

677
00:27:26,690 --> 00:27:29,450
Torej lahko začnemo združitvijo
parov seznamov znova.

678
00:27:29,450 --> 00:27:38,420
Združitev 15 in 108 ter 4 in 50, smo
najprej vzeti 4, nato 15, nato

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

680
00:27:41,500 --> 00:27:50,610
Združitev 8, 42 in 16, 23, moramo najprej sprejeti
8, nato 16, nato 23,

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

682
00:27:52,700 --> 00:27:57,600
>> Torej, zdaj imamo samo dve sezname velikosti
4, od katerih je vsak razporejene.

683
00:27:57,600 --> 00:28:01,170
Torej, zdaj imamo združevanje teh dveh seznamov.

684
00:28:01,170 --> 00:28:11,835
Najprej smo vzeli 4, nato pa vzamemo
8, potem smo vzeli 15, nato 16, nato

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

686
00:28:19,456 --> 00:28:19,872
>> [END predvajanje videa]

687
00:28:19,872 --> 00:28:23,430
>> DAVID Malan: Spet obvestilo, nikoli
dotaknila določeno posodo več kot enkrat

688
00:28:23,430 --> 00:28:24,860
Po napreduje zunaj njega.

689
00:28:24,860 --> 00:28:26,200
Torej še nikoli ponoviti.

690
00:28:26,200 --> 00:28:29,850
Torej, on je vedno gibljejo na strani
in to je, če imava n.

691
00:28:29,850 --> 00:28:33,290
>> Zakaj ne pustite me dvigni eno animacijo
da smo videli zgoraj, vendar tokrat

692
00:28:33,290 --> 00:28:35,110
osredotoča le na zlivanjem.

693
00:28:35,110 --> 00:28:38,030
Dovolite mi, da gredo naprej in povečavo
V zvezi s tem tukaj.

694
00:28:38,030 --> 00:28:42,530
Najprej naj izberejo naključno vhod,
poveličevati to, in si lahko nekako videti

695
00:28:42,530 --> 00:28:46,600
kar je samoumevno, prej,
zlivanjem dejansko počne.

696
00:28:46,600 --> 00:28:50,330
>> Tako opazili, da ste dobili te polčasih ali
te četrtine ali ti osmine

697
00:28:50,330 --> 00:28:53,140
Problem, ki naenkrat
začnete jemati dobri formi.

698
00:28:53,140 --> 00:28:57,070
In potem na koncu, boste videli na
Zelo konec, da bam,

699
00:28:57,070 --> 00:28:58,860
vse je združila skupaj.

700
00:28:58,860 --> 00:29:01,690
>> Torej so to le trije različni
je na isti zamisli.

701
00:29:01,690 --> 00:29:05,980
Ampak ključno spoznanje, tako kot ločnice
in vladaj v prvi razred,

702
00:29:05,980 --> 00:29:10,640
je bil, da smo se odločili, da nekako razdeliti
problem v nekaj velikega, v

703
00:29:10,640 --> 00:29:14,760
kar nekako enaka v duhu
ampak manjši in manjši in manjši

704
00:29:14,760 --> 00:29:15,660
in manjši.

705
00:29:15,660 --> 00:29:18,420
>> Zdaj pa še en zabaven način, da nekako mislim,
o njih, čeprav to ni

706
00:29:18,420 --> 00:29:20,520
bo dal enako intuitivno
razumevanje, je

707
00:29:20,520 --> 00:29:21,640
naslednja animacija.

708
00:29:21,640 --> 00:29:25,400
Torej je ta video je nekdo dal skupaj
, ki so povezana različna

709
00:29:25,400 --> 00:29:29,970
zvoki z različnimi postopki za
vstavljanje sort, za urejanje z zlivanjem, in

710
00:29:29,970 --> 00:29:31,150
za nekaj drugih.

711
00:29:31,150 --> 00:29:32,330
Torej, v tem trenutku, bom udaril Play.

712
00:29:32,330 --> 00:29:33,600
To je približno dolg minuto.

713
00:29:33,600 --> 00:29:37,410
In čeprav še vedno lahko vidite
Vzorci se dogaja, tem času lahko

714
00:29:37,410 --> 00:29:41,420
tudi slišati, kako so ti algoritmi
opravljanju drugače in z

715
00:29:41,420 --> 00:29:43,950
Nekoliko različni vzorci.

716
00:29:43,950 --> 00:29:45,830
>> To je vstavljanje vrste.

717
00:29:45,830 --> 00:29:50,400
>> [TONES IGRANJE]

718
00:29:50,400 --> 00:29:52,400
>> DAVID Malan: Spet se poskuša
vstaviti vsak element

719
00:29:52,400 --> 00:29:52,900
na mesto, kamor spada.

720
00:29:52,900 --> 00:29:54,628
To je bubble sort.

721
00:29:54,628 --> 00:30:10,097
>> [TONES IGRANJE]

722
00:30:10,097 --> 00:30:13,630
>> DAVID Malan: In lahko nekako počutim
kako relativno malo delo, ki ga počne

723
00:30:13,630 --> 00:30:15,834
za vsak korak.

724
00:30:15,834 --> 00:30:20,470
To je tisto, kar tediousness sliši.

725
00:30:20,470 --> 00:30:21,472
>> [TONES IGRANJE]

726
00:30:21,472 --> 00:30:25,222
>> DAVID Malan: To je izbor sort,
kjer izberete element, ki ga želimo

727
00:30:25,222 --> 00:30:28,845
skozi znova in znova in znova
in dajanje na začetku.

728
00:30:28,845 --> 00:30:37,674
>> [TONES IGRANJE]

729
00:30:37,674 --> 00:30:43,970
>> DAVID Malan: To je združiti vrste, ki
lahko zares začutite.

730
00:30:43,970 --> 00:30:51,810
>> [TONES IGRANJE]

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

732
00:30:54,770 --> 00:30:58,395
>> DAVID Malan: Nekaj ​​se imenuje gnome
sort, ki jih nismo pogledal.

733
00:30:58,395 --> 00:31:13,630
>> [TONES IGRANJE]

734
00:31:13,630 --> 00:31:17,910
>> DAVID Malan: Torej, da vidim, zdaj,
raztresen, kot si upamo so jih

735
00:31:17,910 --> 00:31:21,110
glasbo, če bom lahko porinil malo
malo matematike tukaj.

736
00:31:21,110 --> 00:31:24,850
Torej je Četrti način, da bomo lahko
pomislite, kaj to pomeni, da ti

737
00:31:24,850 --> 00:31:29,210
naloge, ki se hitreje od tistih,
, ki smo jih videli prej.

738
00:31:29,210 --> 00:31:32,470
In če ste prihajajo v času od
matematika ozadje, si

739
00:31:32,470 --> 00:31:36,030
pravzaprav vem, morda je že, da si
Lahko slap izraz na to tehniko -

740
00:31:36,030 --> 00:31:40,400
sicer rekurzija, funkcija
da se nekako kliče.

741
00:31:40,400 --> 00:31:44,780
>> In spet opozoriti, da zlivanjem
psevdokoda je rekurzivna v smislu

742
00:31:44,780 --> 00:31:48,460
da je eden od korakov zlivanjem je
je, da pokličete vrste -

743
00:31:48,460 --> 00:31:49,740
da je sama.

744
00:31:49,740 --> 00:31:52,480
Ampak na srečo, ker smo ohranili
kliče vrste ali zlivanjem,

745
00:31:52,480 --> 00:31:55,880
Natančneje, v manjši in manjši
in manjši seznam, bomo na koncu

746
00:31:55,880 --> 00:32:00,005
dno, hvala za tisto, kar imenujemo
osnovna, težko kodiran primeru, da

747
00:32:00,005 --> 00:32:04,270
omenjeni če seznam je majhna, manj kot 2
v tem primeru le vrnil takoj.

748
00:32:04,270 --> 00:32:07,550
Če ne bi imeli to poseben primer,
Algoritem bi nikoli dno ven,

749
00:32:07,550 --> 00:32:11,010
in ti bi dejansko dobili v
neskončna zanka resnično večno.

750
00:32:11,010 --> 00:32:14,330
>> Recimo, da želimo, da sedaj dajo
nekatere številke o tem, še enkrat, z uporabo n

751
00:32:14,330 --> 00:32:15,660
kot je velikost vnosa.

752
00:32:15,660 --> 00:32:18,680
In sem te hotel vprašati, kaj je
Skupni čas sodeluje pri

753
00:32:18,680 --> 00:32:19,800
teče zlivanjem?

754
00:32:19,800 --> 00:32:22,960
Ali bolj na splošno, kaj je
stroški pa v času?

755
00:32:22,960 --> 00:32:24,730
>> No, to je precej težko izmeriti, da.

756
00:32:24,730 --> 00:32:29,010
Če je n manj kot 2, ki je vpletena čas
V sortiranje n elementov,

757
00:32:29,010 --> 00:32:30,480
kjer je n 2, je 0.

758
00:32:30,480 --> 00:32:31,410
Ker smo pravkar vrnil.

759
00:32:31,410 --> 00:32:32,510
Ni treba kaj postoriti.

760
00:32:32,510 --> 00:32:35,660
Zdaj verjetno, morda je še korak ali dva
korake, da ugotovimo količino

761
00:32:35,660 --> 00:32:38,420
delo, ampak to je dovolj blizu 0, da
Jaz sem samo reči, no delo

762
00:32:38,420 --> 00:32:40,940
potrebna, če je seznam tako majhen
ne zanimajo.

763
00:32:40,940 --> 00:32:42,580
>> Ampak v tem primeru je zanimivo.

764
00:32:42,580 --> 00:32:47,320
Rekurzivni primer je podružnica
psevdokoda tem je dejal še, neke

765
00:32:47,320 --> 00:32:52,000
leva polovica razvrstite desno
pol, združila dve polovici.

766
00:32:52,000 --> 00:32:55,530
Zdaj zakaj se ta izraz
predstavljati, da je račun?

767
00:32:55,530 --> 00:32:58,690
No, T n pomeni le
Čas je, da razvrstite n elementov.

768
00:32:58,690 --> 00:33:03,070
In nato na desni strani
enačaj tam, T n razdelimo

769
00:33:03,070 --> 00:33:06,600
po 2 se nanaša na stroške za kaj?

770
00:33:06,600 --> 00:33:07,570
Razvrščanje levo polovico.

771
00:33:07,570 --> 00:33:10,990
Drugi T n deljeno z 2 je
domnevno nanašajo na stroške

772
00:33:10,990 --> 00:33:12,390
razvrstite desno polovico.

773
00:33:12,390 --> 00:33:14,590
>> In potem plus n?

774
00:33:14,590 --> 00:33:15,420
Se združujejo.

775
00:33:15,420 --> 00:33:19,120
Ker če imate dva seznama, eden od
velikost n več kot 2 in drugega velikosti n

776
00:33:19,120 --> 00:33:22,580
več kot 2, moraš v bistvu dotik
vsak od teh elementov, tako kot Rob

777
00:33:22,580 --> 00:33:24,990
dotakne vsakega od skodelic, in samo
kot smo poudarili na vsaki

778
00:33:24,990 --> 00:33:26,310
Prostovoljci na odru.

779
00:33:26,310 --> 00:33:28,790
Torej je n stroške združevanja.

780
00:33:28,790 --> 00:33:31,780
>> Zdaj žal, ta formula
je tudi sama rekurzivno.

781
00:33:31,780 --> 00:33:36,390
Torej, če je vprašal, če je n, recimo,
16, če je 16 ljudi na odru

782
00:33:36,390 --> 00:33:40,670
ali 16 skodelic v videu, koliko skupaj
koraki traja, da jih razvrstite

783
00:33:40,670 --> 00:33:41,550
z zlivanjem?

784
00:33:41,550 --> 00:33:45,790
To je pravzaprav ni očiten odgovor,
ker zdaj moraš nekako

785
00:33:45,790 --> 00:33:48,500
rekurzivno odgovoriti na to formulo.

786
00:33:48,500 --> 00:33:51,190
>> Ampak to je v redu, ker mi predlagamo
da bomo naslednje.

787
00:33:51,190 --> 00:33:56,670
Čas je izbral rešiti 16 ljudi, ali
16 skodelic se bo predstavljal

788
00:33:56,670 --> 00:33:58,020
splošno kot T 16.

789
00:33:58,020 --> 00:34:01,400
Ampak to je enako, glede na naše
Predhodna formula, 2-krat znesek

790
00:34:01,400 --> 00:34:04,780
Čas, ki je potreben za razvrščanje
8 skodelice plus 16.

791
00:34:04,780 --> 00:34:08,590
In spet, plus 16 je čas, da se združijo,
in dvakrat T 8 je

792
00:34:08,590 --> 00:34:10,790
Čas je, da razvrstite levo polovico in desno polovico.

793
00:34:10,790 --> 00:34:11,989
>> Toda tudi to ni dovolj.

794
00:34:11,989 --> 00:34:13,210
Moramo, da se potopite globlje.

795
00:34:13,210 --> 00:34:16,409
To pomeni, da moramo odgovoriti
Vprašanje, kaj je T 8?

796
00:34:16,409 --> 00:34:19,610
No T 8 je samo 2
Časovni T 4 plus 8.

797
00:34:19,610 --> 00:34:20,520
No, kaj je T 4?

798
00:34:20,520 --> 00:34:23,780
T 4 je le 2-krat T 2 plus 4.

799
00:34:23,780 --> 00:34:25,489
No, kaj je T 2?

800
00:34:25,489 --> 00:34:29,030
T 2 je le 2-krat T 1 plus 2.

801
00:34:29,030 --> 00:34:31,940
>> In spet smo nekako dobili
zaljubljen v tem ciklusu.

802
00:34:31,940 --> 00:34:34,790
Ampak to je približno zadeti, da
tako imenovani osnovni primer.

803
00:34:34,790 --> 00:34:37,310
Ker kaj je T 1, ni trdimo?

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

805
00:34:37,810 --> 00:34:39,730
Zdaj končno lahko delamo nazaj.

806
00:34:39,730 --> 00:34:44,290
>> Če T 1 je 0, lahko zdaj iti nazaj gor en
poravnati s tem tipom sem in sem lahko

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

808
00:34:46,330 --> 00:34:51,770
Torej to pomeni, da je enaka 2 krat nič,
sicer znan kot 0, plus 2.

809
00:34:51,770 --> 00:34:53,739
In da celo izraz je 2.

810
00:34:53,739 --> 00:34:58,740
>> Zdaj, če vzamem t 2, katerega odgovor
je 2, ga priključite na srednjo črto, T

811
00:34:58,740 --> 00:35:02,740
od 4, ki mi daje 2-krat
2 plus 4, tako 8.

812
00:35:02,740 --> 00:35:07,080
Če sem nato priključite 8. do prejšnja
linija, ki mi daje 2 krat 8, 16.

813
00:35:07,080 --> 00:35:12,470
In če potem še, da se z
24, tako da v 16., smo končno dobili

814
00:35:12,470 --> 00:35:13,820
vrednost 64.

815
00:35:13,820 --> 00:35:18,480
>> Zdaj, samo po sebi nekako govori
nič do n zapisu

816
00:35:18,480 --> 00:35:20,700
velik O, omega, da smo jih
je govoril.

817
00:35:20,700 --> 00:35:24,890
Ampak se je izkazalo, da je 64 dejansko
16, velikost vhodu

818
00:35:24,890 --> 00:35:27,110
log osnovo 2 16.

819
00:35:27,110 --> 00:35:30,200
In če je to malo poznajo, samo
pomislim nazaj, in to bom prišel nazaj

820
00:35:30,200 --> 00:35:30,700
da vas na koncu.

821
00:35:30,700 --> 00:35:33,775
Če je to osnova dnevnik 2, je kot 2.
postavljeno na kaj vam daje 16?

822
00:35:33,775 --> 00:35:36,380
Oh, to je 4, tako da je 16-krat 4.

823
00:35:36,380 --> 00:35:39,380
>> In spet, to ni nič takega, če je to
je neke vrste meglenem spominu zdaj.

824
00:35:39,380 --> 00:35:43,720
Ampak za zdaj, da na veri
da je 16 dnevnik 16 64.

825
00:35:43,720 --> 00:35:46,590
In tako res, s to preprosto duševno zdravje
preveriti, smo potrdili -

826
00:35:46,590 --> 00:35:48,250
vendar ne dokazano formalno -

827
00:35:48,250 --> 00:35:52,800
da čas teče spajanje
vrsta je res n log n.

828
00:35:52,800 --> 00:35:53,790
>> Torej ni slabo.

829
00:35:53,790 --> 00:35:57,260
To je vsekakor bolje kot
algoritmi smo videli doslej, in

830
00:35:57,260 --> 00:36:00,710
to je zato, ker smo vzvodom, ena,
tehniko, imenovano rekurzija.

831
00:36:00,710 --> 00:36:03,880
Še bolj zanimivo kot to, da
Pojem delitve in osvajanje.

832
00:36:03,880 --> 00:36:07,460
Še enkrat, zares teden 0 stvari, ki
tudi zdaj se ponovilo

833
00:36:07,460 --> 00:36:08,740
bolj prepričljiv način.

834
00:36:08,740 --> 00:36:11,750
>> Zdaj zabavno malo vaje, če ste
nikoli naredil to - in verjetno

835
00:36:11,750 --> 00:36:14,660
ne bi bilo, ker nekako normalno
ljudje ne mislijo, da to storijo.

836
00:36:14,660 --> 00:36:20,650
Ampak, če grem na google.com in, če je
Želim, da se naučijo nekaj o

837
00:36:20,650 --> 00:36:22,356
rekurzija, Enter.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [SMEH]

840
00:36:29,058 --> 00:36:32,030
[Več smeha]

841
00:36:32,030 --> 00:36:33,385
DAVID Malan: Bad šala počasi širi.

842
00:36:33,385 --> 00:36:34,450
[SMEH]

843
00:36:34,450 --> 00:36:36,970
DAVID Malan: Samo v primeru, da je tam.

844
00:36:36,970 --> 00:36:38,710
Nisem urok narobe,
in tam je šala.

845
00:36:38,710 --> 00:36:40,810
Vse je v redu.

846
00:36:40,810 --> 00:36:42,950
Pojasnite, da ljudje poleg vas, če
to je precej ni kliknil samo še.

847
00:36:42,950 --> 00:36:47,650
Ampak rekurzija, bolj na splošno, se nanaša
s procesom funkcijo kliče

848
00:36:47,650 --> 00:36:51,430
sam, ali bolj na splošno, tako
problem v nekaj, kar je lahko

849
00:36:51,430 --> 00:36:56,220
rešiti po kosih z reševanjem enaki
reprezentativnih težave.

850
00:36:56,220 --> 00:36:58,400
>> No, pa prestavljanje
le za trenutek.

851
00:36:58,400 --> 00:37:00,840
Radi bi na koncu o nekaterih cliffhangers,
zato začnimo, da nastavite

852
00:37:00,840 --> 00:37:05,870
faza, za nekaj minut,
na zelo preprosto idejo -

853
00:37:05,870 --> 00:37:07,620
da z zamenjavo dveh elementov, kajne?

854
00:37:07,620 --> 00:37:10,040
Vseh teh algoritmov smo bili
govorimo o zadnjih nekaj

855
00:37:10,040 --> 00:37:12,420
predavanja vključujejo nekatere
neke vrste zamenjavo.

856
00:37:12,420 --> 00:37:14,630
Danes je vizualizirali z njihovo pridobivanje
največ iz svojih stolov in

857
00:37:14,630 --> 00:37:18,570
sprehod okoli, ampak v kodi, bi mi
vzemite element iz enega niza

858
00:37:18,570 --> 00:37:20,370
Pasti in ga v drugo.

859
00:37:20,370 --> 00:37:21,880
>> Torej, kako bomo šli o tem?

860
00:37:21,880 --> 00:37:24,850
No, naj gredo naprej in pisati
Hitro program najdete tukaj.

861
00:37:24,850 --> 00:37:31,600
Jaz grem naprej in to
to kot sledi.

862
00:37:31,600 --> 00:37:33,910
Recimo to -

863
00:37:33,910 --> 00:37:38,070
Kaj hočemo, da pokličete to?

864
00:37:38,070 --> 00:37:38,650
>> Pravzaprav ne.

865
00:37:38,650 --> 00:37:39,420
Dovolite mi nazaj.

866
00:37:39,420 --> 00:37:41,220
Ne želim storiti, da
Alpinista še ni.

867
00:37:41,220 --> 00:37:42,270
To bo pokvaril zabavo.

868
00:37:42,270 --> 00:37:43,600
Naredimo to namesto tega.

869
00:37:43,600 --> 00:37:47,430
>> Recimo, da želim napisati malo
Program in da zdaj zajema ta

870
00:37:47,430 --> 00:37:48,700
Ideja rekurzije.

871
00:37:48,700 --> 00:37:50,370
Nekako sem dobil pred sebe tam.

872
00:37:50,370 --> 00:37:51,420
Jaz bom naredil naslednje.

873
00:37:51,420 --> 00:38:00,220
>> Prvič, hitro vključujejo standardne io.h,
kot tudi vključujejo v cs50.h.

874
00:38:00,220 --> 00:38:03,200
In potem bom šel naprej
in razglasi int main praznino

875
00:38:03,200 --> 00:38:04,360
na običajen način.

876
00:38:04,360 --> 00:38:07,920
Sem spoznal, da sem misnamed datoteko, tako da
Naj samo dodati. podaljšanje c tukaj, tako da

877
00:38:07,920 --> 00:38:09,510
, ki ga lahko pripravijo pravilno.

878
00:38:09,510 --> 00:38:10,970
Začeti to funkcijo izklopite.

879
00:38:10,970 --> 00:38:13,290
>> In funkcija želim pisati, precej
Preprosto povedano, je tista, ki prosi

880
00:38:13,290 --> 00:38:16,210
Uporabnik za številne in nato sešteje
vse številke, ki med

881
00:38:16,210 --> 00:38:19,920
število in, recimo, 0.

882
00:38:19,920 --> 00:38:22,510
Torej, najprej bom šel naprej
in razglasi int n.

883
00:38:22,510 --> 00:38:24,760
Potem sem kopirati nekaj kode, ki
uporabili smo za nekaj časa.

884
00:38:24,760 --> 00:38:26,660
Medtem ko je nekaj res.

885
00:38:26,660 --> 00:38:28,000
Vrnil se bom na to v trenutku.

886
00:38:28,000 --> 00:38:29,010
>> Kaj hočem narediti?

887
00:38:29,010 --> 00:38:33,460
Hočem reči printf pozitiven
celo prosim.

888
00:38:33,460 --> 00:38:36,130
In potem bom
pravijo n dobi dobil int.

889
00:38:36,130 --> 00:38:38,800
Torej še enkrat, nekateri boilerplate koda
, ki smo jih uporabljali prej.

890
00:38:38,800 --> 00:38:40,810
In jaz bom to naredil
medtem ko je n manj kot 1.

891
00:38:40,810 --> 00:38:44,120
Tako se s tem zagotovi, da uporabnik
mi daje pozitivno celo število.

892
00:38:44,120 --> 00:38:45,490
>> In zdaj bom naredil naslednje.

893
00:38:45,490 --> 00:38:51,020
Želim, da dodate do vseh številk
med 1 in in n, ali 0 in n,

894
00:38:51,020 --> 00:38:52,570
ekvivalentno, da bi dobili skupno vsoto.

895
00:38:52,570 --> 00:38:55,100
Tako velik simbol sigma
da boste morda spomni.

896
00:38:55,100 --> 00:38:59,050
Torej bom to naredil tako, da najprej kliče
Funkcija Sigma,

897
00:38:59,050 --> 00:39:06,030
njegovo posredovanje v n, nato pa bom
pravijo printf, odgovor je tam.

898
00:39:06,030 --> 00:39:08,180
>> Torej na kratko, dobim in
int od uporabnika.

899
00:39:08,180 --> 00:39:09,280
Jaz se zagotovi, da je pozitivna.

900
00:39:09,280 --> 00:39:12,700
Izjavljam spremenljivko z imenom odgovor
tip int in trgovina v njej povratek

901
00:39:12,700 --> 00:39:15,610
Vrednost sigma, ki poteka v n kot vhod.

902
00:39:15,610 --> 00:39:17,060
In potem sem izpisal tak odgovor.

903
00:39:17,060 --> 00:39:19,550
>> Na žalost, čeprav sigma sliši
kot nekaj, kar bi lahko v

904
00:39:19,550 --> 00:39:24,040
math.h datoteke, njena izjava,
da je dejansko ni.

905
00:39:24,040 --> 00:39:24,690
Tako, da je v redu.

906
00:39:24,690 --> 00:39:26,170
Ne morem izvajati to sam.

907
00:39:26,170 --> 00:39:29,160
Grem izvajati funkcijo imenovano
sigma, in to bo trajalo

908
00:39:29,160 --> 00:39:29,900
parameter -

909
00:39:29,900 --> 00:39:32,100
kaj je samo call it m, samo
tako da je drugačen.

910
00:39:32,100 --> 00:39:35,910
In potem je tu gor, bom rekel,
in, če je m manj kot 1 - to je

911
00:39:35,910 --> 00:39:38,180
zelo nezanimiv program.

912
00:39:38,180 --> 00:39:41,700
Tako da sem šel naprej in
takoj vrne 0..

913
00:39:41,700 --> 00:39:45,920
To preprosto nima smisla sešteti vse
številke od 1 do m, če m

914
00:39:45,920 --> 00:39:48,470
sam 0 ali negativna.

915
00:39:48,470 --> 00:39:50,900
>> In potem bom šel naprej
in to zelo iterativno.

916
00:39:50,900 --> 00:39:53,090
Jaz bom naredil to vrsto old-school,
in jaz grem naprej

917
00:39:53,090 --> 00:39:57,150
in rekel, da bom
razglasi znesek za 0.

918
00:39:57,150 --> 00:39:59,630
Potem bom še
za zanke int -

919
00:39:59,630 --> 00:40:02,820
in mi to storiti za doseganje naših
distribucija kodo, tako da boste imeli kopijo

920
00:40:02,820 --> 00:40:07,500
doma. int i dobi 1 na do
i je manjša ali enaka m.

921
00:40:07,500 --> 00:40:09,430
i plus plus.

922
00:40:09,430 --> 00:40:11,430
In potem notranjost ta zanka -

923
00:40:11,430 --> 00:40:12,440
smo skoraj tam -

924
00:40:12,440 --> 00:40:15,810
vsota dobi vsoto plus 1.

925
00:40:15,810 --> 00:40:17,670
In potem se bom vrnil vsoto.

926
00:40:17,670 --> 00:40:19,420
>> Zato sem to storil hitro,
čisto res.

927
00:40:19,420 --> 00:40:22,775
Ampak še enkrat, katerega glavna funkcija je precej
preprosta, temelji na kodi, ki smo jih

928
00:40:22,775 --> 00:40:23,190
doslej napisal.

929
00:40:23,190 --> 00:40:25,610
Uporablja dvojno zanko, da bi dobili pozitiven
int od uporabnika.

930
00:40:25,610 --> 00:40:29,870
Nato sem mimo tega int na novo funkcijo
imenovane sigma, ga kliče, še enkrat, n.

931
00:40:29,870 --> 00:40:33,100
In jaz shranjevanje vrne vrednost, odgovor
od sedaj črne skrinjice

932
00:40:33,100 --> 00:40:35,460
znan kot sigma v variabilni
imenovano odgovor.

933
00:40:35,460 --> 00:40:36,580
Potem sem ga natisnete.

934
00:40:36,580 --> 00:40:39,090
>> Če bomo zdaj še zgodbo,
kako se sigma izvaja?

935
00:40:39,090 --> 00:40:40,840
Predlagam, da izvaja takole.

936
00:40:40,840 --> 00:40:43,560
Najprej malo napak in
zagotoviti, da uporabnik ni

937
00:40:43,560 --> 00:40:46,480
zajebavam z mano in poteka v
nekatera negativna ali 0 vrednost.

938
00:40:46,480 --> 00:40:49,710
Potem sem se razglasi spremenljivko
sešteje in jo nastavite na 0.

939
00:40:49,710 --> 00:40:55,910
>> In zdaj sem začel premikati iz i je enak
1. vse tja do vključno m,

940
00:40:55,910 --> 00:41:00,130
ker želim, da se vključijo vsi
številke od ena do m, vključno.

941
00:41:00,130 --> 00:41:04,350
In znotraj tega za zanke, sem naredil
Vsota dobi vse, kar je sedaj, plus

942
00:41:04,350 --> 00:41:08,900
Vrednost i.

943
00:41:08,900 --> 00:41:10,370
Plus vrednost i.

944
00:41:10,370 --> 00:41:14,090
>> Kot prahi, če se niste videli tega
prej, obstaja nekaj skladenjsko sladkorja

945
00:41:14,090 --> 00:41:14,870
Za te vrstice.

946
00:41:14,870 --> 00:41:21,120
To lahko znova kot plus enako i,
samo, da sam prihranite nekaj tipkanja

947
00:41:21,120 --> 00:41:22,570
in pogledati malo hladnejše.

948
00:41:22,570 --> 00:41:23,140
Ampak to je vse.

949
00:41:23,140 --> 00:41:24,660
To je funkcionalno enako.

950
00:41:24,660 --> 00:41:26,710
>> Žal pa ta oznaka je
ne bo še prevesti.

951
00:41:26,710 --> 00:41:31,600
Če sem teči, da sigma 0, kako am
Jaz bom dobil nadrla?

952
00:41:31,600 --> 00:41:33,473
Kaj se to dogaja, da ni všeč?

953
00:41:33,473 --> 00:41:35,740
>> PUBLIKA: [neslišno].

954
00:41:35,740 --> 00:41:37,800
>> DAVID Malan: Ja, ni prijavil
Funkcija up top, kajne?

955
00:41:37,800 --> 00:41:40,590
C je malo butast, ampak samo v tem, da
ne, kaj ti povem, da narediti, in ti

956
00:41:40,590 --> 00:41:41,880
to storiti v tem vrstnem redu.

957
00:41:41,880 --> 00:41:45,910
In tako, če sem udaril Enter tukaj, bom
dobili opozorilo o sigma implicitna

958
00:41:45,910 --> 00:41:46,860
deklaracija.

959
00:41:46,860 --> 00:41:48,120
>> Oh, ni problema.

960
00:41:48,120 --> 00:41:50,370
Lahko grem do vrha in sem lahko
rekli, v redu, počakaj malo.

961
00:41:50,370 --> 00:41:54,240
Sigma je funkcija, ki vrne
int in pričakuje, da bo

962
00:41:54,240 --> 00:41:56,620
int kot vstopni, podpičjem.

963
00:41:56,620 --> 00:41:59,550
Ali lahko dam celotno funkcijo
nad glavno, ampak na splošno, jaz bi

964
00:41:59,550 --> 00:42:02,260
odsvetujemo, da zato, ker je
lepo, da imajo vedno glavni na vrhu tako

965
00:42:02,260 --> 00:42:06,310
lahko potopite v desno in vedo, kaj
Program počne z branjem glavni prvi.

966
00:42:06,310 --> 00:42:07,930
>> Torej, zdaj mi počistite zaslon.

967
00:42:07,930 --> 00:42:09,330
Remake sigma 0.

968
00:42:09,330 --> 00:42:10,340
Vse se zdi, da preverite.

969
00:42:10,340 --> 00:42:11,970
Dovolite mi, da teče sigma 0.

970
00:42:11,970 --> 00:42:12,770
Pozitivna med.

971
00:42:12,770 --> 00:42:15,580
Dal bom številko
3. naj bo enostavno.

972
00:42:15,580 --> 00:42:18,710
Tako, da mi je dal 3
plus 2 plus 1, torej 6.

973
00:42:18,710 --> 00:42:20,750
Vnesti, in res sem dobil 6.

974
00:42:20,750 --> 00:42:21,820
>> Jaz lahko naredim nekaj večjega -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Tako kot tangenta, bom naredil
nekaj smešno, kot je res velika

977
00:42:27,690 --> 00:42:30,375
Številka, Oh, to je dejansko delal -

978
00:42:30,375 --> 00:42:31,600
eh, jaz ne mislim, da je prav.

979
00:42:31,600 --> 00:42:32,810
Poglejmo.

980
00:42:32,810 --> 00:42:34,060
Kaj je res igraš z njim.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> To je težava.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
Kaj se dogaja?

985
00:42:44,970 --> 00:42:46,050
Koda ni tako slabo.

986
00:42:46,050 --> 00:42:48,470
Še vedno linearna.

987
00:42:48,470 --> 00:42:50,810
Žvižganje je dober učinek, čeprav.

988
00:42:50,810 --> 00:42:52,060
Kaj se dogaja?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> Ne vem, če sem to slišal.

991
00:42:55,620 --> 00:42:57,620
Tako se izkaže - in
to je kot stran.

992
00:42:57,620 --> 00:42:59,400
To ni jedro
Ideja rekurzije.

993
00:42:59,400 --> 00:43:02,480
Izkazalo se je, ker sem poskušal
predstavljajo tako veliko število, najbolj

994
00:43:02,480 --> 00:43:06,980
verjetno je, da bi razlagala
s C kot ne pozitivnim predznakom,

995
00:43:06,980 --> 00:43:09,980
ampak negativno število.

996
00:43:09,980 --> 00:43:12,690
>> Nismo govorili o tem, vendar je
Izkazalo se je, da so negativne številke

997
00:43:12,690 --> 00:43:14,210
v svetu, poleg
do pozitivnih številk.

998
00:43:14,210 --> 00:43:16,290
In sredstva, s katerimi lahko
predstavljajo negativno število

999
00:43:16,290 --> 00:43:19,530
v bistvu je, da uporabite enega
poseben bit, ki označuje

1000
00:43:19,530 --> 00:43:20,400
pozitivna nad negativno.

1001
00:43:20,400 --> 00:43:22,950
To je malo bolj zapleten kot to,
ampak to je osnovna ideja.

1002
00:43:22,950 --> 00:43:26,740
>> Torej, žal, če C je zmedeno eno
teh bitov so dejansko pomeni,

1003
00:43:26,740 --> 00:43:30,790
oh, to je negativno število, moja zanka
Tukaj, na primer, je dejansko še

1004
00:43:30,790 --> 00:43:31,740
bo prekine.

1005
00:43:31,740 --> 00:43:33,850
Torej, če bi bil dejansko tiskanje nekaj
znova in znova, bi se

1006
00:43:33,850 --> 00:43:34,650
glej cel kup.

1007
00:43:34,650 --> 00:43:36,220
Toda tudi to je poleg točke.

1008
00:43:36,220 --> 00:43:38,590
To je res samo nekakšna
intelektualna radovednost, da bomo prišli

1009
00:43:38,590 --> 00:43:39,550
nazaj na koncu.

1010
00:43:39,550 --> 00:43:43,400
Toda za zdaj, to je pravilno
Izvajanje če predpostavimo, da

1011
00:43:43,400 --> 00:43:45,970
Uporabnik bo ints
, ki se prilegajo v ints.

1012
00:43:45,970 --> 00:43:49,370
>> Vendar trdim, da je ta koda, odkrito povedano,
bi lahko naredili toliko bolj preprosto.

1013
00:43:49,370 --> 00:43:54,060
Če je cilj na roki, je, da se število
kot m in seštejejo vsi

1014
00:43:54,060 --> 00:43:59,510
številke med njim in 1 ali obratno
med 1 in, Trdim

1015
00:43:59,510 --> 00:44:03,380
da si lahko sposodim to idejo, da se združijo
sortiranje imel, ki je bil ob težave

1016
00:44:03,380 --> 00:44:05,660
te velikosti in deljenjem
v nekaj manjši.

1017
00:44:05,660 --> 00:44:09,875
Mogoče ne pol, ampak manjši, vendar
reprezentativno enako.

1018
00:44:09,875 --> 00:44:12,130
Enako zamisel, vendar manjši problem.

1019
00:44:12,130 --> 00:44:15,470
>> Tako da sem pravzaprav - naj shraniti to datoteko
z drugačno številko različice.

1020
00:44:15,470 --> 00:44:17,670
Poklicali bomo to različico
1 namesto 0.

1021
00:44:17,670 --> 00:44:20,790
In trdim, da sem lahko dejansko
reimplement to v tovrstne

1022
00:44:20,790 --> 00:44:22,160
um-upogibni način.

1023
00:44:22,160 --> 00:44:23,710
>> Bom pustil del njega samega.

1024
00:44:23,710 --> 00:44:27,710
Jaz bom rekel, če m je manj
od ali celo enaka 0 -

1025
00:44:27,710 --> 00:44:29,280
Grem, da se malo
več anal tokrat

1026
00:44:29,280 --> 00:44:30,520
z mojo napako preverjanje -

1027
00:44:30,520 --> 00:44:33,190
Jaz grem naprej in vrne 0..

1028
00:44:33,190 --> 00:44:34,490
To je poljubna.

1029
00:44:34,490 --> 00:44:37,500
Jaz sem samo preprosto odloči, če uporabnik
mi daje negativno število, sem

1030
00:44:37,500 --> 00:44:41,490
vračanje 0, in bi moral prebrati
Dokumentacija bolj.

1031
00:44:41,490 --> 00:44:42,170
>> Drugega -

1032
00:44:42,170 --> 00:44:44,070
opazili, kaj bom naredil.

1033
00:44:44,070 --> 00:44:49,260
Sicer se bom vrnil m plus -

1034
00:44:49,260 --> 00:44:51,010
kaj je sigma od m?

1035
00:44:51,010 --> 00:44:56,710
No, sigma o m plus minus 1 m,
plus minus m 2, plus minus 3 m.

1036
00:44:56,710 --> 00:44:58,030
Ne želim napisati vse to ven.

1037
00:44:58,030 --> 00:44:59,120
Zakaj ne bi jaz samo punt?

1038
00:44:59,120 --> 00:45:05,080
Rekurzivno sam klic z nekoliko
manjši problem, podpičje,

1039
00:45:05,080 --> 00:45:06,840
in za danes?

1040
00:45:06,840 --> 00:45:07,040
>> Kajne?

1041
00:45:07,040 --> 00:45:10,980
Zdaj tudi tu, bi lahko počutite ali skrbi
da je to neskončno zanko, da sem

1042
00:45:10,980 --> 00:45:15,450
indukcije, pri čemer sem izvajanjem
sigma ga kliče sigma.

1043
00:45:15,450 --> 00:45:20,342
Ampak to je popolnoma v redu, ker sem
Mislil naprej dodal, katere vrstice?

1044
00:45:20,342 --> 00:45:22,600
>> PUBLIKA: [neslišno].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID Malan: 23 do 26, ki
če je moj pogoj.

1046
00:45:25,430 --> 00:45:28,390
Ker tisto, kar je lepo o
odštevanje tukaj, ker sem naprej

1047
00:45:28,390 --> 00:45:31,180
Izročitev sigma manjše težave, manjša
Težave, manjši - to ni

1048
00:45:31,180 --> 00:45:31,870
pol velikosti.

1049
00:45:31,870 --> 00:45:34,380
Saj je samo otrok korak manjši,
ampak to je v redu.

1050
00:45:34,380 --> 00:45:38,050
Ker na koncu, bomo delo
naša pot navzdol na 1 ali 0.

1051
00:45:38,050 --> 00:45:41,630
In ko smo zadeli 0, sigma ni
dogaja, da se več poklical.

1052
00:45:41,630 --> 00:45:43,590
To se dogaja, da takoj vrne 0..

1053
00:45:43,590 --> 00:45:47,960
>> Torej učinek, če nekako veter to
v tvoji glavi, je dodati m plus

1054
00:45:47,960 --> 00:45:52,740
m minus 1, plus minus m 2, plus minus m
3, plus pika, dot, pika, m minus

1055
00:45:52,740 --> 00:45:57,820
m, na koncu vam daje 0 in
Učinek je na koncu dodati vse

1056
00:45:57,820 --> 00:45:59,070
te stvari skupaj.

1057
00:45:59,070 --> 00:46:02,380
Torej nimamo, z rekurzijo,
rešiti problem, ki smo

1058
00:46:02,380 --> 00:46:03,470
ne more rešiti prej.

1059
00:46:03,470 --> 00:46:06,840
Dejansko verzija 0 tega, in vsak
problem danes je bil rešljiv

1060
00:46:06,840 --> 00:46:09,980
s samo uporabo for zanke ali pa
zanke ali podobne konstrukcije.

1061
00:46:09,980 --> 00:46:13,150
>> Ampak rekurzija, upam si reči, daje nam
drugačen način razmišljanja o

1062
00:46:13,150 --> 00:46:17,010
Težave, s katerimi se lahko, če vzamemo
problem, ga razdelite od nečesa

1063
00:46:17,010 --> 00:46:22,340
nekoliko velik v nekaj nekoliko
manjši, Trdim, da ga bomo lahko rešili

1064
00:46:22,340 --> 00:46:26,040
morda malo bolj elegantno v smislu
zasnove, z manj kode,

1065
00:46:26,040 --> 00:46:30,980
in morda celo rešili težave, ki bi
bo težje, saj bomo sčasoma

1066
00:46:30,980 --> 00:46:33,280
glej, reševanje zgolj iterativno.

1067
00:46:33,280 --> 00:46:35,980
>> Ampak Alpinista, da sem storil
želimo, da nas pustite bilo to.

1068
00:46:35,980 --> 00:46:40,720
Dovolite mi, da gredo naprej in odprite
do datotek od -

1069
00:46:40,720 --> 00:46:44,300
pravzaprav, naj gredo in
to storiti zelo hitro.

1070
00:46:44,300 --> 00:46:46,875
Dovolite mi, da gredo naprej in predlagati
Naslednji.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Med današnjim koda je ta datoteka tukaj.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Ta tukaj, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Torej, to je neumno malo program, ki
Sem podžigal, ki trdi, da ne

1076
00:47:06,260 --> 00:47:06,940
Naslednji.

1077
00:47:06,940 --> 00:47:10,140
V glavnem, najprej razglasi
int imenuje x in ga dodeli

1078
00:47:10,140 --> 00:47:11,100
vrednost 1.

1079
00:47:11,100 --> 00:47:13,520
Potem pa izjavlja, int y in
dodeli to vrednost 2.

1080
00:47:13,520 --> 00:47:15,310
Potem se natisne kar x in y.

1081
00:47:15,310 --> 00:47:17,781
Potem pa pravi, zamenjavo, dot dot piko.

1082
00:47:17,781 --> 00:47:21,670
>> Potem pa trdi, da se kliče funkcijo
imenuje zamenjavo, ki poteka v x in

1083
00:47:21,670 --> 00:47:24,290
y, ideja, ki je, upajmo
x in y bo ponovno

1084
00:47:24,290 --> 00:47:25,620
drugačen, nasprotno.

1085
00:47:25,620 --> 00:47:27,110
Potem pa trdijo, zamenjali!

1086
00:47:27,110 --> 00:47:28,420
s klicajem.

1087
00:47:28,420 --> 00:47:30,190
Potem se natisne x in y.

1088
00:47:30,190 --> 00:47:33,480
>> Ampak se je izkazalo, da je to zelo
preprosta predstavitev navzdol

1089
00:47:33,480 --> 00:47:35,570
Tu je pravzaprav vozičkom.

1090
00:47:35,570 --> 00:47:38,870
Čeprav sem o razglasitvi začasne
spremenljiva in začasno dajanje v

1091
00:47:38,870 --> 00:47:42,010
jo, nato pa sem prerazporeditev
vrednost b -

1092
00:47:42,010 --> 00:47:45,080
ki se počuti smiselno, ker sem
shrani kopijo v temp.

1093
00:47:45,080 --> 00:47:48,410
Potem sem posodobiti b, da enako
kar je bilo v temp.

1094
00:47:48,410 --> 00:47:51,610
Ta vrsta shell igro gibljejo
v B in B v s tem

1095
00:47:51,610 --> 00:47:54,360
middle-man imenovano temp počuti
popolnoma razumljiva.

1096
00:47:54,360 --> 00:47:57,270
>> Vendar trdim, da ko sem teči ta
kodo, kot bom pa zdaj -

1097
00:47:57,270 --> 00:47:59,490
Naj gredo naprej in ga prilepite tukaj.

1098
00:47:59,490 --> 00:48:01,995
Poklical bom to noswap.c.

1099
00:48:01,995 --> 00:48:05,630
Kot ime pove, da to ni
bo pravilen program.

1100
00:48:05,630 --> 00:48:09,460
Naredite noswap. / Ne swap.

1101
00:48:09,460 --> 00:48:12,110
x 1, y 2, zamenjavo, zamenjali.

1102
00:48:12,110 --> 00:48:14,220
x je 1, je y 2.

1103
00:48:14,220 --> 00:48:16,920
To je popolnoma narobe, čeprav
čeprav se to zdi povsem

1104
00:48:16,920 --> 00:48:17,730
smiselno, da me.

1105
00:48:17,730 --> 00:48:21,330
In tu je razlog, vendar nismo
bo razkrila razlog samo še.

1106
00:48:21,330 --> 00:48:24,610
>> Za zdaj drugi Cliffhanger sem hotel
da greš s to,

1107
00:48:24,610 --> 00:48:27,120
Napoved vrst na kod kuponov.

1108
00:48:27,120 --> 00:48:31,590
Naša inovacija poznih dneh letos
je izzvala nepomembno število

1109
00:48:31,590 --> 00:48:33,830
vprašanj, kar je bilo
ni naš namen.

1110
00:48:33,830 --> 00:48:36,590
Namen teh kod kuponov,
pri čemer, če vam del problema

1111
00:48:36,590 --> 00:48:39,850
nastavite zgodaj, tako dobili dodaten dan,
je res, da bi vi pomagali

1112
00:48:39,850 --> 00:48:42,420
sami začeli zgodaj, vrste
stranskih vas incentivizing.

1113
00:48:42,420 --> 00:48:44,880
Pomaga nam distribucijo tovora čez
Uradne ure bolje, tako da

1114
00:48:44,880 --> 00:48:45,740
to je nekako win-win.

1115
00:48:45,740 --> 00:48:48,860
>> Na žalost, mislim, da mojim navodilom
niso bili do sedaj zelo jasno, da

1116
00:48:48,860 --> 00:48:52,230
Ta vikend sem se vrnil in posodobljene
spec v večji, drznejši besedilo k

1117
00:48:52,230 --> 00:48:53,600
razložiti naboje kot ti.

1118
00:48:53,600 --> 00:48:56,900
In samo to povedati javnosti bolj po
privzete, problem sprejemnikov so posledica četrtek

1119
00:48:56,900 --> 00:48:58,400
opoldne po predmetniku.

1120
00:48:58,400 --> 00:49:02,030
Če začnete zgodaj, zaključna dela
Problem, ki ga je v sredo ob 12:00

1121
00:49:02,030 --> 00:49:05,170
PM, del, ki se nanaša na obrestno mero
koda, ideja je, da lahko podaljša

1122
00:49:05,170 --> 00:49:07,710
poteče rok za
P nastavite do petka.

1123
00:49:07,710 --> 00:49:10,890
To je malo off majhen del P
relativne glede na to, kar je značilno

1124
00:49:10,890 --> 00:49:13,200
večji problem, kupite
sami dodaten dan.

1125
00:49:13,200 --> 00:49:15,190
Spet vam pride razmišljanje o
Problem set, vam do gets

1126
00:49:15,190 --> 00:49:16,380
govorilne ure prej.

1127
00:49:16,380 --> 00:49:20,670
Ampak koda problem kupon še
zahteva, da tudi če ga ne predloži.

1128
00:49:20,670 --> 00:49:23,340
>> Ampak bolj prepričljivo je to.

1129
00:49:23,340 --> 00:49:26,520
(ODER WHISPER) In ti ljudje zapuščajo
zgodaj so žal boš.

1130
00:49:26,520 --> 00:49:28,620
Ker so ljudje na balkonu.

1131
00:49:28,620 --> 00:49:32,510
Se opravičujem vnaprej ljudska pesem o
balkon iz razlogov, ki bodo

1132
00:49:32,510 --> 00:49:33,920
jasno, čez nekaj trenutkov.

1133
00:49:33,920 --> 00:49:37,050
>> Tako da smo srečni, da imajo enega
CS50 je nekdanji vodja poučevanje tovariši na

1134
00:49:37,050 --> 00:49:39,302
podjetje, imenovano dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
Imajo zelo velikodušno podaril
kupon koda tukaj za to toliko prostora,

1136
00:49:45,500 --> 00:49:48,180
ki je odvisno od
Običajni 2 gigabajta.

1137
00:49:48,180 --> 00:49:51,740
Torej, kaj sem mislil, da bi naredil o tem
Končna ocena je narediti nekaj v zibelko,

1138
00:49:51,740 --> 00:49:55,380
pri čemer vsak trenutek, bomo razkriti
zmagovalec in kdo ima kupon

1139
00:49:55,380 --> 00:49:57,980
kodo, ki jo lahko nato iti na svoje
Spletna stran, ga vnesite v, in voila, dobil

1140
00:49:57,980 --> 00:50:01,370
veliko več Dropbox prostor za vaš
aparata in vaših osebnih datotek.

1141
00:50:01,370 --> 00:50:05,690
>> In prvi, ki bi želeli sodelovati
v tej risbi?

1142
00:50:05,690 --> 00:50:09,630
OK, zdaj je še bolj zabavno.

1143
00:50:09,630 --> 00:50:14,010
Oseba, ki prejme ta 25-GB
kupon koda - ki je daleč

1144
00:50:14,010 --> 00:50:16,150
bolj prepričljiv kot prepozno
Zdaj dni, morda -

1145
00:50:16,150 --> 00:50:20,620
je tisti, ki sedi na vrhu
sedežne blazine, pod katerimi so

1146
00:50:20,620 --> 00:50:21,620
da je koda kupona.

1147
00:50:21,620 --> 00:50:23,480
Sedaj lahko ogledate spodaj
vaše sedežne blazine.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [Predvajanje videa]

1150
00:50:29,680 --> 00:50:31,620
>> -Ena, dva, tri.

1151
00:50:31,620 --> 00:50:35,015
>> [Kričanje]

1152
00:50:35,015 --> 00:50:35,985
>> Si dobil avto!

1153
00:50:35,985 --> 00:50:36,670
Dobiš avto!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID Malan: Bomo videli
ste v sredo.

1155
00:50:37,970 --> 00:50:38,904
>> Si dobil avto!

1156
00:50:38,904 --> 00:50:39,371
Dobiš avto!

1157
00:50:39,371 --> 00:50:40,305
Dobiš avto!

1158
00:50:40,305 --> 00:50:41,706
Dobiš avto!

1159
00:50:41,706 --> 00:50:43,107
Dobiš avto!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID Malan: Balkon ljudje, pridite
dol s čela

1161
00:50:45,530 --> 00:50:46,866
kjer imamo statistov.

1162
00:50:46,866 --> 00:50:50,282
>> -Vsak dobi avto!

1163
00:50:50,282 --> 00:50:52,234
Vsakdo dobi svoj avto!

1164
00:50:52,234 --> 00:50:52,722
>> [END predvajanje videa]

1165
00:50:52,722 --> 00:50:54,590
>> Pripovedovalec: Na naslednjem CS50 -

1166
00:50:54,590 --> 00:51:00,374
>> ZVOČNIK 5: O moj bog bog bog bog
bog bog bog bog bog bog -

1167
00:51:00,374 --> 00:51:02,106
>> [UKELELE Predvaja]