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

2
00:00:00,488 --> 00:00:10,800
>> [Tónlist spila]

3
00:00:10,800 --> 00:00:13,500
DAVID Malan: Allt í lagi.

4
00:00:13,500 --> 00:00:14,670
Allt í lagi, velkominn aftur.

5
00:00:14,670 --> 00:00:18,120
Svo er þetta Vika 4, í upphafi
þeirra, þegar.

6
00:00:18,120 --> 00:00:21,320
Og þú munt minnast þess að í síðustu viku, leggjum
númerið til hliðar fyrir aðeins lítill hluti

7
00:00:21,320 --> 00:00:24,240
og við byrjuðum að tala smá meira
hár-láréttur flötur, um hluti eins

8
00:00:24,240 --> 00:00:28,130
leita og flokka, sem þó
nokkuð einfalt hugmyndir, eru

9
00:00:28,130 --> 00:00:31,840
fulltrúi flokki vandamálum
þú verður að byrja að leysa sérstaklega

10
00:00:31,840 --> 00:00:34,820
eins og þú byrjar að hugsa um endanlega
verkefni og áhugaverðar lausnir sem þú

11
00:00:34,820 --> 00:00:36,760
gæti þurft að raunverulegur-veröld vandamál.

12
00:00:36,760 --> 00:00:39,490
Nú kúla tegund var eitt af því einfaldasta
svo reiknirit, og það

13
00:00:39,490 --> 00:00:42,900
unnið með því að hafa þessar litlu tölur
í lista eða í array konar

14
00:00:42,900 --> 00:00:46,530
kúla leið sína upp á toppinn og
stór númer færa leið sína niður að

15
00:00:46,530 --> 00:00:47,930
enda þeim lista.

16
00:00:47,930 --> 00:00:50,650
>> Og muna að við gætum sjón
kúla konar smá

17
00:00:50,650 --> 00:00:52,310
eitthvað eins og this.

18
00:00:52,310 --> 00:00:53,640
Svo láta mig fara á undan og smelltu á Start.

19
00:00:53,640 --> 00:00:55,350
Ég hef forvalinn kúla konar.

20
00:00:55,350 --> 00:00:58,920
Og ef þú manst að hærri blár
línur tákna stór númer, lítið

21
00:00:58,920 --> 00:01:03,300
blár línur tákna lítil númer, eins og
við förum í gegnum þetta aftur og aftur og

22
00:01:03,300 --> 00:01:07,680
aftur, bera saman tvær bars við hliðina á hvor
annan í rauðu, við erum að fara að skipta á

23
00:01:07,680 --> 00:01:11,010
Stærsta og minnsta ef
þeir eru út af röð.

24
00:01:11,010 --> 00:01:14,150
>> Þannig að þetta mun halda áfram og áfram og fara
á, og þú munt sjá að stærri

25
00:01:14,150 --> 00:01:16,700
þættir eru að gera sér leið til
rétt, og smærri þættir eru

26
00:01:16,700 --> 00:01:17,900
gerð þeirra vegur til vinstri.

27
00:01:17,900 --> 00:01:21,380
En við byrjuðum að mæla
skilvirkni, the

28
00:01:21,380 --> 00:01:22,970
gæði þessa reiknirit.

29
00:01:22,970 --> 00:01:25,200
Og við sögðum að í versta
tilfelli, þetta reiknirit tók

30
00:01:25,200 --> 00:01:27,940
u.þ.b. hversu mörg skref?

31
00:01:27,940 --> 00:01:28,980
>> Svo n ferningur.

32
00:01:28,980 --> 00:01:30,402
Og hvað var n?

33
00:01:30,402 --> 00:01:31,650
>> Áhorfendur: Fjöldi þátta.

34
00:01:31,650 --> 00:01:32,790
>> DAVID Malan: Svo n var
Fjöldi þátta.

35
00:01:32,790 --> 00:01:33,730
Og svo við munum gera þetta oft.

36
00:01:33,730 --> 00:01:36,650
Hvenær við viljum tala um stærð
um vandamál eða stærð að

37
00:01:36,650 --> 00:01:39,140
inntak, eða þann tíma sem það tekur
að framleiða framleiðsla, munum við bara

38
00:01:39,140 --> 00:01:41,610
almenn hvað
inntak er eins n.

39
00:01:41,610 --> 00:01:45,970
Svo aftur í viku 0, fjölda síður
í símaskránni var n.

40
00:01:45,970 --> 00:01:47,550
Fjölda nemenda
í herberginu var n.

41
00:01:47,550 --> 00:01:49,630
Svo hér líka, við erum eftir
að mynstur.

42
00:01:49,630 --> 00:01:52,800
>> Nú n ferningur er ekki sérstaklega
hratt, svo við reyndum að gera betur.

43
00:01:52,800 --> 00:01:55,970
Og svo skoðuðum við nokkra
önnur reiknirit, þar á meðal

44
00:01:55,970 --> 00:01:57,690
voru val konar.

45
00:01:57,690 --> 00:01:59,180
Svo raða val var
svolítið öðruvísi.

46
00:01:59,180 --> 00:02:03,130
Það var næstum einfaldara, ég þori að segja,
þar sem ég byrjaði í upphafi sem

47
00:02:03,130 --> 00:02:06,740
listi af sjálfboðaliðum okkar og ég bara aftur
og aftur og aftur fór í gegnum

48
00:02:06,740 --> 00:02:10,060
lista, plokkun út minnstu
þáttur í einu og setja hann eða

49
00:02:10,060 --> 00:02:13,040
henni í upphafi á listanum.

50
00:02:13,040 --> 00:02:16,410
>> En þetta líka, þegar við byrjuðum að hugsa
gegnum stærðfræði og stærri

51
00:02:16,410 --> 00:02:19,860
mynd, hugsaði um hversu oft
Ég var að fara fram og til baka og aftur

52
00:02:19,860 --> 00:02:24,090
og fram, sagði að við í versta tilfelli,
val tagi, líka, var það?

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

54
00:02:24,960 --> 00:02:27,490
Nú í hinum raunverulega heimi, gæti það
reyndar vera ívið hraðar.

55
00:02:27,490 --> 00:02:30,620
Því aftur, gerði ég ekki að halda
backtracking þegar ég hafði raðað á

56
00:02:30,620 --> 00:02:31,880
Minnsta atriði.

57
00:02:31,880 --> 00:02:35,090
En ef við hugsum um mjög stór n og
ef þú gerir svona út stærðfræði sem

58
00:02:35,090 --> 00:02:39,170
Ég gerði í stjórn, með n veldi
mínus eitthvað, allt annað

59
00:02:39,170 --> 00:02:41,850
auk n veldi, einu sinni n
fær mjög stór, er ekki

60
00:02:41,850 --> 00:02:42,850
máli eins mikið.

61
00:02:42,850 --> 00:02:45,470
Svo sem tölvunarfræðingum, raða við um
snúa að blindu auga til minni

62
00:02:45,470 --> 00:02:49,220
þættir og einblína á þáttur í
tjáning sem er að fara að gera

63
00:02:49,220 --> 00:02:50,330
mesti munurinn.

64
00:02:50,330 --> 00:02:52,840
>> Jæja, loksins, leit við
á Innsetningarröðun.

65
00:02:52,840 --> 00:02:56,620
Og þetta var svipað í anda, en
frekar en að fara í gegnum iteratively og

66
00:02:56,620 --> 00:03:01,250
velja minnstu þátturinn einn á
tími, tók ég í staðinn höndina sem ég

67
00:03:01,250 --> 00:03:04,070
var fjallað, og ég ákvað, allt
rétt, tilheyrir þú hér.

68
00:03:04,070 --> 00:03:06,160
Þá er ég flutti á til the næstur þáttur
og ákvað að hann eða

69
00:03:06,160 --> 00:03:07,470
hún átti hér.

70
00:03:07,470 --> 00:03:08,810
Og þá er ég flutti á og á.

71
00:03:08,810 --> 00:03:11,780
Og ég gæti til, á leiðinni,
skipta þessar krakkar í því skyni að

72
00:03:11,780 --> 00:03:13,030
gera pláss fyrir þá.

73
00:03:13,030 --> 00:03:16,880
Svo sem var eins konar andlega viðsnúnings
af tegund val sem við

74
00:03:16,880 --> 00:03:18,630
kallað innsetningu konar.

75
00:03:18,630 --> 00:03:20,810
>> Svo þessi mál til komið
í hinum raunverulega heimi.

76
00:03:20,810 --> 00:03:23,640
Fyrir nokkrum árum síðan, þegar tiltekinn
Senator var í gangi fyrir forseta,

77
00:03:23,640 --> 00:03:27,160
Eric Schmidt, á þeim tíma forstjóri
Google, í raun hafði tækifæri

78
00:03:27,160 --> 00:03:28,040
að viðtal honum.

79
00:03:28,040 --> 00:03:32,010
Og við héldum að við myndum deila þessu YouTube
bút fyrir þig hér, ef við gætum snúið upp

80
00:03:32,010 --> 00:03:32,950
rúmmál.

81
00:03:32,950 --> 00:03:39,360
>> [Vídeó spilun]

82
00:03:39,360 --> 00:03:44,620
>> -Nú, Senator, ert þú hér á Google,
og ég eins og til hugsa af formennsku

83
00:03:44,620 --> 00:03:46,042
sem atvinnuviðtal.

84
00:03:46,042 --> 00:03:47,770
>> [Hlátur]

85
00:03:47,770 --> 00:03:50,800
>> -Nú er það erfitt að fá
starf sem forseti.

86
00:03:50,800 --> 00:03:52,480
Og þú ert að fara í gegnum
rigors núna.

87
00:03:52,480 --> 00:03:54,330
Það er líka erfitt að fá vinnu á Google.

88
00:03:54,330 --> 00:03:59,610
Við höfum spurningar og við spyrjum
frambjóðendur spurningum okkar.

89
00:03:59,610 --> 00:04:02,250
Og þetta er frá Larry Schwimmer.

90
00:04:02,250 --> 00:04:05,325
>> [Hlátur]

91
00:04:05,325 --> 00:04:06,400
-Þið held ég að grínast?

92
00:04:06,400 --> 00:04:08,750
Það er hérna.

93
00:04:08,750 --> 00:04:12,110
Hvað er skilvirkasta leiðin til
raða milljón tveggja bita heiltölur?

94
00:04:12,110 --> 00:04:15,810
>> [Hlátur]

95
00:04:15,810 --> 00:04:18,260
>> -Jæja, uh -

96
00:04:18,260 --> 00:04:19,029
>> -Ég því miður.

97
00:04:19,029 --> 00:04:19,745
Kannski við ættum -

98
00:04:19,745 --> 00:04:21,000
>> -Nei, nei, nei, nei, nei.

99
00:04:21,000 --> 00:04:21,470
>> -Það er ekki -

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

101
00:04:22,185 --> 00:04:25,328
>> -Ég held að kúla tegund myndi
vera röng leið til að fara.

102
00:04:25,328 --> 00:04:26,792
>> [Hlátur]

103
00:04:26,792 --> 00:04:28,510
>> [Uppörvandi og lófaklapp]

104
00:04:28,510 --> 00:04:31,211
>> -Komdu, sem sagði honum þetta?

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

106
00:04:32,155 --> 00:04:33,350
>> [END vídeó spilun]

107
00:04:33,350 --> 00:04:35,070
>> DAVID Malan: Svo þar hafið þið það.

108
00:04:35,070 --> 00:04:39,600
Svo byrjuðum við að mæla þetta gangi
sinnum, svo að segja, með eitthvað

109
00:04:39,600 --> 00:04:43,480
kallað asymptotic merki, sem er
bara vísa til að flokka okkar beygja

110
00:04:43,480 --> 00:04:47,420
blindur auga til þeirra smærri þáttum og
aðeins að horfa á hlaupandi tíma,

111
00:04:47,420 --> 00:04:51,250
árangur þessara reiknirit,
eins og n fær mjög stór með tímanum.

112
00:04:51,250 --> 00:04:55,110
Og svo við kynna stór O. og Big O
fulltrúa eitthvað sem við héldum

113
00:04:55,110 --> 00:04:57,000
af eins og efri bundið.

114
00:04:57,000 --> 00:04:59,570
Og reyndar, Barry, getum við lækkað
en mic svolítið?

115
00:04:59,570 --> 00:05:01,040
>> Við héldum þetta er efri bundið.

116
00:05:01,040 --> 00:05:04,710
Svo stór O n veldi þýðir að í
versta tilfelli, eitthvað eins og

117
00:05:04,710 --> 00:05:07,780
val konar myndi taka
n ferhyrndir skrefum.

118
00:05:07,780 --> 00:05:10,310
Eða eitthvað eins og Innsetningarröðun
myndi n ferningur skref.

119
00:05:10,310 --> 00:05:15,150
Nú fyrir eitthvað eins innsetningu
tegund, hvað var það versta tilfelli?

120
00:05:15,150 --> 00:05:18,200
Gefið fylki, hvað er það versta
mögulegt atburðarás sem þú gætir fundið

121
00:05:18,200 --> 00:05:20,650
sjálfur frammi?

122
00:05:20,650 --> 00:05:21,860
>> Það er alveg afturábak, ekki satt?

123
00:05:21,860 --> 00:05:24,530
Vegna þess að ef það er alveg aftur á bak,
þú þarft að gera a heild einhver fjöldi af vinna.

124
00:05:24,530 --> 00:05:26,420
Vegna þess að ef þú ert alveg aftur,
þú ert að fara að finna

125
00:05:26,420 --> 00:05:28,840
stærsta þáttur hér, jafnvel þótt
það tilheyrir þangað.

126
00:05:28,840 --> 00:05:31,140
Svo þú ert að fara að segja, allt í lagi, að minnsta
þessari stundu í tíma, tilheyrir þú hér,

127
00:05:31,140 --> 00:05:32,310
svo þú láta það standa.

128
00:05:32,310 --> 00:05:35,425
>> Þá þér grein, ó, fjandinn, ég verð að
færa þetta örlítið minni þáttur að

129
00:05:35,425 --> 00:05:36,470
vinstri af þér.

130
00:05:36,470 --> 00:05:38,770
Þá verð ég að gera það aftur
og aftur og aftur.

131
00:05:38,770 --> 00:05:41,410
Og ef ég gekk fram og til baka, þú
myndi raða á finnst árangur

132
00:05:41,410 --> 00:05:45,540
að reiknirit, vegna þess að stöðugt er ég
uppstokkun allir aðrir niður í

133
00:05:45,540 --> 00:05:46,510
array til að gera pláss fyrir það.

134
00:05:46,510 --> 00:05:47,750
Svo er það versta tilfelli.

135
00:05:47,750 --> 00:05:48,570
>> Með því móti -

136
00:05:48,570 --> 00:05:50,320
og þetta var cliffhanger síðast -

137
00:05:50,320 --> 00:05:54,065
ég sagði að innsetning konar
var Ómega um hvað?

138
00:05:54,065 --> 00:05:57,530
Hvað er best málið gangi
tími Innsetningarröðun?

139
00:05:57,530 --> 00:05:58,520
Svo það er í raun n.

140
00:05:58,520 --> 00:06:00,980
Það var autt að við fórum
á borð síðast.

141
00:06:00,980 --> 00:06:03,160
>> Og það er Omega í n því hvers vegna?

142
00:06:03,160 --> 00:06:06,630
Jæja, í besta tilfelli, hvað er
innsetningu konar leið til að afhenda?

143
00:06:06,630 --> 00:06:09,830
Jæja, lista sem er alveg raðað
nú þegar, lítil vinna að gera.

144
00:06:09,830 --> 00:06:12,460
En hvað er sniðugt um Innsetningarröðun
er það vegna þess að það byrjar hér og

145
00:06:12,460 --> 00:06:15,340
ákveður, ó, þú ert númer
einn, tilheyrir þú hér.

146
00:06:15,340 --> 00:06:16,970
Hvílíkur gæfu.

147
00:06:16,970 --> 00:06:17,740
>> Þú ert númer tvö.

148
00:06:17,740 --> 00:06:19,030
Þú tilheyra einnig hér.

149
00:06:19,030 --> 00:06:21,010
Númer þrjú, jafnvel betra,
þú tilheyrir hér.

150
00:06:21,010 --> 00:06:25,210
Um leið og það fær að lok
lista, Per innsetningu tagi er sauðakóðanum

151
00:06:25,210 --> 00:06:28,010
sem við gengum í gegnum munnlega
síðasta sinn, það er gert.

152
00:06:28,010 --> 00:06:32,790
En val tagi, hins vegar
hélt að gera hvað?

153
00:06:32,790 --> 00:06:35,260
>> Haldið að fara í gegnum listann
aftur og aftur og aftur.

154
00:06:35,260 --> 00:06:39,160
Þar sem lykillinn innsýn það var aðeins
þegar þú hefur skoðað alla leið til

155
00:06:39,160 --> 00:06:42,500
endir á listanum getur þú verið viss
að þáttur sem þú valdir var

156
00:06:42,500 --> 00:06:45,560
örugglega eins lítill þáttur.

157
00:06:45,560 --> 00:06:48,920
Svo þessar mismunandi andlega módel enda
upp sveigjanlegur sumir mjög raunverulegur-veröld

158
00:06:48,920 --> 00:06:53,130
munur fyrir okkur, eins og heilbrigður eins og þessir
fræðileg aðfelluþrýstingi munur.

159
00:06:53,130 --> 00:06:56,910
>> Svo bara til að ágrip, þá stór O í n
ferningur, höfum við séð nokkur slík

160
00:06:56,910 --> 00:06:58,350
reiknirit svona langt.

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

162
00:06:59,580 --> 00:07:02,870
Hvað er reiknirit sem gæti
að segja að vera stór O í n?

163
00:07:02,870 --> 00:07:06,930
Í versta tilfelli, það tekur
línulegt fjölda skrefum.

164
00:07:06,930 --> 00:07:07,810
>> OK, línuleg leit.

165
00:07:07,810 --> 00:07:10,470
Og í versta tilfelli, þar er
þáttur sem þú ert að leita að þegar

166
00:07:10,470 --> 00:07:12,950
beita línuleg leit?

167
00:07:12,950 --> 00:07:14,680
>> OK, í versta tilfelli,
það er ekki einu sinni þarna.

168
00:07:14,680 --> 00:07:17,000
Eða í annarri versta tilfelli, það er
alla leið á endanum, sem er

169
00:07:17,000 --> 00:07:18,880
plús-eða-mínus eitt skref munur.

170
00:07:18,880 --> 00:07:21,180
Svo í lok dagsins,
við getum sagt að það er línuleg.

171
00:07:21,180 --> 00:07:23,910
Big O n væri línuleg leit,
vegna þess að í versta tilfelli,

172
00:07:23,910 --> 00:07:26,610
þáttur er ekki einu sinni þar eða það er
alla leið á enda.

173
00:07:26,610 --> 00:07:29,370
>> Jæja, stór O log n.

174
00:07:29,370 --> 00:07:32,760
Við ekki tala í smáatriðum um
þetta, en við höfum séð þetta áður.

175
00:07:32,760 --> 00:07:36,840
Hvað liggur í svokölluðum lógaritmískum
tíma, í versta tilfelli?

176
00:07:36,840 --> 00:07:38,500
>> Já, svo tvöfaldur leit.

177
00:07:38,500 --> 00:07:42,930
Og tvöfaldur leita í versta tilfelli
gæti hafa þáttur einhversstaðar í

178
00:07:42,930 --> 00:07:45,640
miðju, eða einhvers staðar
inni í array.

179
00:07:45,640 --> 00:07:48,040
En þú finnur bara það þegar þú
skipta lista í tvennt, í

180
00:07:48,040 --> 00:07:48,940
helmingur, í tvennt, í tvennt.

181
00:07:48,940 --> 00:07:50,200
Og þá voila, það er það.

182
00:07:50,200 --> 00:07:52,500
Eða aftur, versta tilfelli,
það er ekki einu sinni þarna.

183
00:07:52,500 --> 00:07:56,770
En þú veist ekki að það er ekki þar
þar til þú nærð svona að síðustu

184
00:07:56,770 --> 00:08:00,470
botn-flestir þættir með helminga
og helminga og helminga.

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

186
00:08:01,400 --> 00:08:03,540
Svo við gætum stór O 2, stór O í 3.

187
00:08:03,540 --> 00:08:06,260
Hvenær sem þú vilt bara stöðugt tala,
við að raða bara í bara einfalda

188
00:08:06,260 --> 00:08:07,280
að eins stór O í 1.

189
00:08:07,280 --> 00:08:10,440
Jafnvel þó að raunhæft, það tekur
2 eða jafnvel 100 skref, ef það er

190
00:08:10,440 --> 00:08:13,680
stöðug tala af skrefum,
við segjum bara stór O 1..

191
00:08:13,680 --> 00:08:15,930
Hvað er reiknirit sem er
í stóru O í 1?

192
00:08:15,930 --> 00:08:18,350
>> Áhorfendur: Að finna lengd
af breytu.

193
00:08:18,350 --> 00:08:21,090
>> DAVID Malan: Finndu
lengd breytu?

194
00:08:21,090 --> 00:08:23,870
>> Áhorfendur: Nei, lengd
ef það er þegar raðað.

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

196
00:08:24,160 --> 00:08:27,850
OK, svo að finna lengd eitthvað
ef lengd að eitthvað, eins og

197
00:08:27,850 --> 00:08:30,020
fylki, er geymt í sumum breytu.

198
00:08:30,020 --> 00:08:33,380
Þar sem þú getur bara lesið breytu,
eða prenta breytu, eða

199
00:08:33,380 --> 00:08:34,960
bara almennt aðgang þá breytu.

200
00:08:34,960 --> 00:08:37,299
Og voila, sem tekur stöðugum tíma.

201
00:08:37,299 --> 00:08:38,909
>> Hins vegar að hugsa til baka til að klóra.

202
00:08:38,909 --> 00:08:42,460
Hugsaðu til baka í fyrsta viku C,
hringja bara printf og prentun

203
00:08:42,460 --> 00:08:46,240
eitthvað á skjánum er að öllum líkindum
stöðug tíma, vegna þess að það tekur bara

204
00:08:46,240 --> 00:08:50,880
sumir tala um hringrás CPU til að sýna
þessi texti á skjánum.

205
00:08:50,880 --> 00:08:52,720
Eða bíddu - er það?

206
00:08:52,720 --> 00:08:56,430
Hvernig annars gætum við fyrirmynd
Afkoma printf?

207
00:08:56,430 --> 00:09:00,420
Myndi einhver vilja vera ósammála, að
kannski er það ekki í raun fasti skipti?

208
00:09:00,420 --> 00:09:03,600
Í hvaða skilningi gætu printf er í gangi
tíma, í raun prentun a band á

209
00:09:03,600 --> 00:09:05,580
á skjánum, að vera eitthvað
önnur en stöðug.

210
00:09:05,580 --> 00:09:07,860
>> Áhorfendur: [inaudible].

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

212
00:09:08,230 --> 00:09:09,300
Svo fer það eftir sjónarhorni okkar.

213
00:09:09,300 --> 00:09:13,390
Ef við hugsum í raun um inntak til
printf eins og að vera band, og

214
00:09:13,390 --> 00:09:16,380
því við að mæla stærð sem
inntak af lengd þess - Svo skulum kalla

215
00:09:16,380 --> 00:09:17,780
að lengd n eins vel -

216
00:09:17,780 --> 00:09:21,990
að öllum líkindum, printf er sjálft stór O í n
því það er að fara að taka þig n stíga

217
00:09:21,990 --> 00:09:24,750
að prenta út hvert þeirra n
stafir, líklega.

218
00:09:24,750 --> 00:09:27,730
Að minnsta kosti að því marki sem við gerum ráð fyrir
að kannski það er að nota fyrir lykkja

219
00:09:27,730 --> 00:09:28,560
undir hetta.

220
00:09:28,560 --> 00:09:30,860
>> En við yrðum að líta á sem
Kóði til að skilja það betur.

221
00:09:30,860 --> 00:09:33,650
Og reyndar, þegar þið byrja
greina eigin reiknirit þinn munt þú

222
00:09:33,650 --> 00:09:34,900
bókstaflega að gera einmitt þetta.

223
00:09:34,900 --> 00:09:37,765
Raða af auga númerið þitt og hugsa
um - allt í lagi, ég hef þetta lykkju

224
00:09:37,765 --> 00:09:41,870
hér eða ég hreiður lykkjur hér,
það er að fara að gera N hlutina n sinnum,

225
00:09:41,870 --> 00:09:46,050
og þú getur raða ástæðu leið
gegnum kóðann, jafnvel ef það er

226
00:09:46,050 --> 00:09:47,980
sauðakóðanum og ekki raunverulegt númer.

227
00:09:47,980 --> 00:09:49,730
>> Og hvað um ómega á n veldi?

228
00:09:49,730 --> 00:09:53,582
Hvað var reiknirit sem í besta
málið enn tók n ferningur skref?

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

230
00:09:54,014 --> 00:09:54,880
>> Áhorfendur: [inaudible].

231
00:09:54,880 --> 00:09:55,900
>> DAVID Malan: Svo val konar.

232
00:09:55,900 --> 00:09:59,150
Vegna þess að í því vandamáli raun minnkað
til þess að aftur, ég veit ekki

233
00:09:59,150 --> 00:10:02,600
Ég hef fundið núverandi minnstu þangað
Ég hef athugað alla fjári þætti.

234
00:10:02,600 --> 00:10:08,050
Sem Omega af, segja, n, við
bara kom upp með eitt.

235
00:10:08,050 --> 00:10:09,300
Innsetning tagi.

236
00:10:09,300 --> 00:10:12,370
Ef listinn verður að vera flokkaður
nú þegar, í besta tilfelli við höfum bara

237
00:10:12,370 --> 00:10:15,090
að gera einn fara í gegnum það,
á hver benda að við erum viss.

238
00:10:15,090 --> 00:10:17,890
Og þá má segja
að vera línuleg, fyrir viss.

239
00:10:17,890 --> 00:10:20,570
>> Hvað um ómega af 1?

240
00:10:20,570 --> 00:10:23,790
Hvað, í besta tilfelli gæti tekið
stöðug nokkur skref?

241
00:10:23,790 --> 00:10:27,220
Svo línuleg leit, ef þú færð bara heppinn
og þáttur sem þú ert að leita

242
00:10:27,220 --> 00:10:31,000
er rétt í byrjun af the listi,
ef það er þar sem þú ert að byrja þína

243
00:10:31,000 --> 00:10:33,070
línuleg traversal af þeim lista.

244
00:10:33,070 --> 00:10:35,180
>> Og þetta er satt af
ýmislegt.

245
00:10:35,180 --> 00:10:37,660
Til dæmis, jafnvel tvöfaldur
Leit er Omega 1..

246
00:10:37,660 --> 00:10:40,310
Því hvað ef þú færð virkilega fjári
heppinn og smack-DAB í miðju

247
00:10:40,310 --> 00:10:42,950
array er fjöldi
þú ert að leita að?

248
00:10:42,950 --> 00:10:45,730
Svo þú getur fengið heppinn þar, eins og heilbrigður.

249
00:10:45,730 --> 00:10:49,190
>> Þetta eitt, loksins, ómega af n log n.

250
00:10:49,190 --> 00:10:52,573
Svo n log n, höfum vér ekki í raun
tala um enn, en -

251
00:10:52,573 --> 00:10:53,300
>> Áhorfendur: Sameina einhverskonar?

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

253
00:10:53,960 --> 00:10:56,920
Það var cliffhanger síðustu tíma,
þar sem við lagt, og við sýndum

254
00:10:56,920 --> 00:10:58,600
sjónrænt, að það eru reiknirit.

255
00:10:58,600 --> 00:11:02,470
Og sameinast einhverskonar bara einn svo
reiknirit sem er í grundvallaratriðum hraðar

256
00:11:02,470 --> 00:11:03,450
en sumir af þessum strákum.

257
00:11:03,450 --> 00:11:07,800
Í raun, sameinast stutt er ekki aðeins í
Besta ræða n log n, í versta

258
00:11:07,800 --> 00:11:09,460
ræða n log n.

259
00:11:09,460 --> 00:11:14,540
Og þegar þú hefur þetta tilviljun
Omega og stór O vera það sama?

260
00:11:14,540 --> 00:11:17,310
Við getum í raun lýsa því sem það er
kallast þeta, þó að það er

261
00:11:17,310 --> 00:11:18,220
lítið sjaldgæfari.

262
00:11:18,220 --> 00:11:21,730
En það þýðir bara tvö mörk,
í þessu tilfelli, eru þau sömu.

263
00:11:21,730 --> 00:11:25,770
>> Svo sameinast raða, hvað þýðir þetta
virkilega sjóða niður fyrir okkur?

264
00:11:25,770 --> 00:11:27,000
Jæja, muna hvatning.

265
00:11:27,000 --> 00:11:30,340
Leyfðu mér að draga upp annað fjör sem
við ekki að líta á síðasta tíma.

266
00:11:30,340 --> 00:11:33,390
Þetta eitt, sama hugmynd, en
það er lítið stærri.

267
00:11:33,390 --> 00:11:36,160
Og ég ætla að fara á undan og benda á
fyrst - við höfum innsetningu konar á

268
00:11:36,160 --> 00:11:39,410
efst til vinstri, þá val tagi,
kúla tegund, a par af öðrum toga -

269
00:11:39,410 --> 00:11:42,670
skel og fljótur - að við höfum ekki talað
um, og hrúga og sameina tegund.

270
00:11:42,670 --> 00:11:47,090
>> Svo að minnsta kosti að reyna að einbeita augun á
þrjár á vinstri og síðan

271
00:11:47,090 --> 00:11:49,120
Mergesort þegar ég smelli
þetta græna ör.

272
00:11:49,120 --> 00:11:51,900
En ég læt þær allar hlaupa, bara til að
gefa þér tilfinningu fyrir fjölbreytileika

273
00:11:51,900 --> 00:11:53,980
reiknirit sem ríkir í heiminum.

274
00:11:53,980 --> 00:11:56,180
Ég ætla að láta þetta hlaupa
fyrir örfáum sekúndum.

275
00:11:56,180 --> 00:11:59,640
Og ef þú einblína augun - Pick
reiknirit, leggja áherslu á það að bara

276
00:11:59,640 --> 00:12:02,970
sekúndur - þú munt byrja að sjá
mynstur sem það er framkvæmd.

277
00:12:02,970 --> 00:12:04,530
>> Sameina tegund, tilkynning, er gert.

278
00:12:04,530 --> 00:12:06,430
Hrúga tegund, fljótur tagi, skel -

279
00:12:06,430 --> 00:12:09,480
svo virðist að við kynntum þrjá
versta reiknirit síðustu viku.

280
00:12:09,480 --> 00:12:12,960
En það er gott að við erum hér í dag til að
líta á sameiningu tagi, sem er eitt af

281
00:12:12,960 --> 00:12:16,500
því auðveldara sjálfur er að líta á, jafnvel
þó það líklega mun sveigja huga þinn

282
00:12:16,500 --> 00:12:17,490
bara svolítið.

283
00:12:17,490 --> 00:12:21,130
Hér getum við séð hversu mikið
val konar sjúga.

284
00:12:21,130 --> 00:12:24,600
>> En á bakhlið er það
mjög auðvelt að framkvæma.

285
00:12:24,600 --> 00:12:28,160
Og kannski fyrir P Set 3, sem er einn af
reiknirit sem þú velur til að innleiða

286
00:12:28,160 --> 00:12:28,960
fyrir venjulegt útgáfu.

287
00:12:28,960 --> 00:12:30,970
Fullkomlega fínn, fullkomlega rétt.

288
00:12:30,970 --> 00:12:35,210
>> En aftur, eins og n fær stór, ef þú
valið að framkvæma a festa reiknirit

289
00:12:35,210 --> 00:12:39,020
eins sameinast raða, eru líkurnar á stærri og
stærri inntak, númer er bara

290
00:12:39,020 --> 00:12:39,800
fara að hlaupa hraðar.

291
00:12:39,800 --> 00:12:41,090
Vefsvæðið þitt er að fara að vinna betur.

292
00:12:41,090 --> 00:12:42,650
Notendur þínir eru að fara til að vera hamingjusamari.

293
00:12:42,650 --> 00:12:45,280
Og svo eru þessi áhrif
í raun að gefa

294
00:12:45,280 --> 00:12:47,350
okkur sumir dýpra hugsun.

295
00:12:47,350 --> 00:12:49,990
>> Þannig að við skulum kíkja á hvað sameinast
tegund er í raun allt um.

296
00:12:49,990 --> 00:12:52,992
The kaldur hlutur er að sameina
tegund er bara þetta.

297
00:12:52,992 --> 00:12:56,300
Þetta er, aftur, það sem við höfum kallað
sauðakóðanum, sauðakóðanum tilvera

298
00:12:56,300 --> 00:12:57,720
English-eins og setningafræði.

299
00:12:57,720 --> 00:12:59,890
Og einfaldleiki er
konar heillandi.

300
00:12:59,890 --> 00:13:02,840
>> Svo á inntak n þætti - svo sem
þýðir bara, hér er fylki.

301
00:13:02,840 --> 00:13:04,000
Það er got n hlutum í það.

302
00:13:04,000 --> 00:13:05,370
Það er allt sem við erum að segja það.

303
00:13:05,370 --> 00:13:07,560
>> Ef n er minna en 2, aftur.

304
00:13:07,560 --> 00:13:08,640
Svo er það bara léttvæg mál.

305
00:13:08,640 --> 00:13:12,580
Ef n er minna en 2, þá augljóslega er það
1 eða 0, en þá sem

306
00:13:12,580 --> 00:13:14,780
er þegar raðað eða nonexistent,
svo bara aftur.

307
00:13:14,780 --> 00:13:15,900
Það er ekkert að gera.

308
00:13:15,900 --> 00:13:18,360
Svo er það einfalt mál að reyta burt.

309
00:13:18,360 --> 00:13:20,110
>> Annars höfum við þrjú skref.

310
00:13:20,110 --> 00:13:23,650
Raða vinstri helming þætti, flokka
rétt helmingur af the frumefni,

311
00:13:23,650 --> 00:13:26,650
og þá sameina raðað helminga.

312
00:13:26,650 --> 00:13:29,400
Hvað er áhugavert hér er að
Ég er svona Punting, ekki satt?

313
00:13:29,400 --> 00:13:32,300
Það er góður af hringlaga skilgreiningu
þessum reiknirit.

314
00:13:32,300 --> 00:13:35,986
Í hvaða skilningi er þetta reiknirit er
skýring hringlaga?

315
00:13:35,986 --> 00:13:37,850
>> Áhorfendur: [inaudible].

316
00:13:37,850 --> 00:13:41,670
>> DAVID Malan: Já, flokkun reiknirit minn,
tveir skrefum hans eru "tegund

317
00:13:41,670 --> 00:13:44,640
eitthvað. "Og svo bidur
spurning, vel, er það sem ég ætla að nota

318
00:13:44,640 --> 00:13:46,460
að raða vinstri helming
og rétt helmingur?

319
00:13:46,460 --> 00:13:49,600
Og fegurð hér er að jafnvel þótt
aftur, þetta er hugur-beygja

320
00:13:49,600 --> 00:13:54,030
hluti hugsanlega er hægt að nota sama
reiknirit til að raða vinstri helminginn.

321
00:13:54,030 --> 00:13:54,700
>> En bíddu í eina mínútu.

322
00:13:54,700 --> 00:13:57,070
Þegar þú ert að segja að raða
vinstri helming, er það tveir

323
00:13:57,070 --> 00:13:58,240
skref að fara að vera næst?

324
00:13:58,240 --> 00:14:00,550
Við munum raða vinstri helmingi
vinstri helmingi og rétt

325
00:14:00,550 --> 00:14:01,420
helmingur af vinstri helming.

326
00:14:01,420 --> 00:14:04,430
Fjandinn, hvernig raða ég þeim tveimur
helminga eða fjórðunga, nú?

327
00:14:04,430 --> 00:14:05,260
>> En það er allt í lagi.

328
00:14:05,260 --> 00:14:07,830
Við höfum flokkun reiknirit hér.

329
00:14:07,830 --> 00:14:10,660
Og jafnvel þó að þú gætir hafa áhyggjur
fyrst er svona óendanlega

330
00:14:10,660 --> 00:14:12,780
lykkja, er það hringrás sem er aldrei
fara til enda - það er að fara að

331
00:14:12,780 --> 00:14:15,770
enda þegar það gerist?

332
00:14:15,770 --> 00:14:16,970
Einu sinni er n minna en 2.

333
00:14:16,970 --> 00:14:19,180
Sem á endanum er að fara að gerast,
því ef þú heldur helminga og

334
00:14:19,180 --> 00:14:23,020
helminga í helminga þessar helminga, örugglega
loksins að þú ert að fara að enda

335
00:14:23,020 --> 00:14:25,350
upp með aðeins 1 eða 0 atriði.

336
00:14:25,350 --> 00:14:28,500
Á hver benda, þetta reiknirit
segir að þú ert búinn.

337
00:14:28,500 --> 00:14:31,020
>> Þannig að raunverulegur galdur í þessu
reiknirit virðist vera í

338
00:14:31,020 --> 00:14:33,470
að stíga skrefið, samruna.

339
00:14:33,470 --> 00:14:37,190
Það einfalda hugmynd bara sameina tvö
hlutir, það er það sem er á endanum að fara

340
00:14:37,190 --> 00:14:40,920
til að leyfa okkur að raða fylki af,
segjum, átta þætti.

341
00:14:40,920 --> 00:14:44,410
Þannig að ég hef átta fleiri streitu kúlur upp
hér, átta stykki af pappír og einn

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

343
00:14:45,500 --> 00:14:46,140
sem ég fæ að halda.

344
00:14:46,140 --> 00:14:46,960
>> [Hlátur]

345
00:14:46,960 --> 00:14:48,970
>> DAVID Malan: Ef við gætum tekið átta
sjálfboðaliðar, og við skulum sjá hvort við getum

346
00:14:48,970 --> 00:14:51,430
spila þetta út, svo.

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

348
00:14:52,500 --> 00:14:53,565
Tölvunarfræði er að fá gaman.

349
00:14:53,565 --> 00:14:54,320
Allt í lagi.

350
00:14:54,320 --> 00:14:57,770
Svo hvernig væri að þú þrjár,
Stærsta hönd þarna.

351
00:14:57,770 --> 00:14:58,580
Fjórir í bakinu.

352
00:14:58,580 --> 00:15:02,220
Og hvernig væri að við munum gera þér
þrjú í þessari röð?

353
00:15:02,220 --> 00:15:03,390
Og fjórir í framan.

354
00:15:03,390 --> 00:15:04,920
Svo þú átta, koma upp.

355
00:15:04,920 --> 00:15:12,060
>> [Hlátur]

356
00:15:12,060 --> 00:15:13,450
>> DAVID Malan: Ég er reyndar
ekki viss hvað það er.

357
00:15:13,450 --> 00:15:14,810
Er það streita kúlur?

358
00:15:14,810 --> 00:15:16,510
Borðið lampar?

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

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

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

362
00:15:20,160 --> 00:15:21,310
Svo koma upp.

363
00:15:21,310 --> 00:15:22,310
Sem langar -

364
00:15:22,310 --> 00:15:23,570
halda á næstunni.

365
00:15:23,570 --> 00:15:24,240
Við skulum sjá.

366
00:15:24,240 --> 00:15:26,460
Og þetta setur þig í stað -

367
00:15:26,460 --> 00:15:27,940
þú ert í stað einn.

368
00:15:27,940 --> 00:15:28,670
Uh-ó, bíddu í eina mínútu.

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

370
00:15:30,760 --> 00:15:31,310
Allt í lagi, við erum góð.

371
00:15:31,310 --> 00:15:35,130
Allt í lagi, svo allir hafa sæti,
en ekki á Google Glass.

372
00:15:35,130 --> 00:15:36,475
Leyfðu mér að biðröð þetta upp.

373
00:15:36,475 --> 00:15:37,115
Hvað er nafn þitt?

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
Allt í lagi, þú færð að líta út eins og
The Geek, ef það er í lagi.

377
00:15:42,000 --> 00:15:44,625
Jæja, ég líka, ég geri ráð fyrir,
fyrir aðeins augnablik.

378
00:15:44,625 --> 00:15:45,875
Allt í lagi, í biðstöðu.

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

380
00:15:48,510 --> 00:15:50,950
Við höfum verið að reyna að koma upp með a
nota málið fyrir Google Glass, og við

381
00:15:50,950 --> 00:15:53,750
hélt að það væri gaman bara að gera
þetta þegar fólk er onstage.

382
00:15:53,750 --> 00:15:57,120
Við munum taka heiminn
frá sjónarhóli þeirra.

383
00:15:57,120 --> 00:15:58,410
Allt í lagi.

384
00:15:58,410 --> 00:15:59,830
Ekki líklega hvað Google ætlað.

385
00:15:59,830 --> 00:16:02,260
Allt í lagi, ef þú dont 'hugur þreytandi
þetta fyrir næstu óþægilega mínútur,

386
00:16:02,260 --> 00:16:03,150
sem myndi vera dásamlegt.

387
00:16:03,150 --> 00:16:08,620
>> Allt í lagi, þannig að við höfum hér á fjölbreytta
þætti, og að array, eins og á

388
00:16:08,620 --> 00:16:11,480
stykki af pappír í þessum fólkinu '
hendur, er nú óflokkað.

389
00:16:11,480 --> 00:16:12,050
>> MICHELLE: Ó, það er svo skrýtið.

390
00:16:12,050 --> 00:16:12,810
>> DAVID Malan: Það er ansi mikið af handahófi.

391
00:16:12,810 --> 00:16:15,760
Og á aðeins augnablik, við erum að fara að reyna
að innleiða Mergesort saman

392
00:16:15,760 --> 00:16:17,950
og sjá hvar þessi lykill innsýn er.

393
00:16:17,950 --> 00:16:21,970
Og bragð hér með sameiningu tagi er
eitthvað sem við höfum ekki gert ráð fyrir enn.

394
00:16:21,970 --> 00:16:24,030
Við þurfum í raun einhvers
fleiri pláss.

395
00:16:24,030 --> 00:16:26,650
Svo hvað er að fara að vera sérstaklega
áhugavert um þetta er að þessi

396
00:16:26,650 --> 00:16:29,270
krakkar eru að fara að flytja í kringum litla
hluti, vegna þess að ég ætla að gera ráð fyrir að

397
00:16:29,270 --> 00:16:31,880
það er auka array af plássi,
segja, rétt fyrir aftan þá.

398
00:16:31,880 --> 00:16:34,570
>> Svo ef þeir eru á bak við stól þeirra,
það er annar array.

399
00:16:34,570 --> 00:16:36,960
Ef þeir sitja hér, það er
aðal array.

400
00:16:36,960 --> 00:16:40,170
En þetta er auðlind sem við höfum
ekki skuldsett svona langt með kúla

401
00:16:40,170 --> 00:16:42,040
tegund, með tegund val,
með Innsetningarröðun.

402
00:16:42,040 --> 00:16:44,600
Muna síðustu viku, allir bara
konar stokkuð á sínum stað.

403
00:16:44,600 --> 00:16:46,840
Þeir vildu ekki nota allir viðbótar minni.

404
00:16:46,840 --> 00:16:49,310
Við gerðum pláss fyrir fólk með
færa fólk í kring.

405
00:16:49,310 --> 00:16:50,580
>> Þannig að þetta er lykillinn innsýn líka.

406
00:16:50,580 --> 00:16:53,410
Það er þetta málamiðlun, almennt í
tölvunarfræði, auðlinda.

407
00:16:53,410 --> 00:16:55,800
Ef þú vilt flýta eitthvað
eins og tími, þú ert að fara að

408
00:16:55,800 --> 00:16:56,900
að greiða verð.

409
00:16:56,900 --> 00:17:00,750
Og einn af þeim verði er mjög oft
rúm, the magn af minni eða harður

410
00:17:00,750 --> 00:17:01,700
pláss sem þú ert að nota.

411
00:17:01,700 --> 00:17:03,640
Eða, hreinskilnislega, að upphæð
tíma forritari.

412
00:17:03,640 --> 00:17:06,700
Hversu mikinn tíma það tekur þig, manna,
til raunverulega framkvæma sumir fleiri

413
00:17:06,700 --> 00:17:07,829
flókið reiknirit.

414
00:17:07,829 --> 00:17:09,760
En í dag, að málamiðlun
er tími og rúm.

415
00:17:09,760 --> 00:17:11,930
>> Þannig að ef þú krakkar gætu bara halda upp þinn
tölur svo við getum séð að þú ert

416
00:17:11,930 --> 00:17:15,839
örugglega passa 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
Þannig að ég ætla að reyna að orchestrate
hlutum, ef þú krakkar geta bara

419
00:17:19,520 --> 00:17:21,800
fylgja leiða minn hér.

420
00:17:21,800 --> 00:17:26,650
>> Svo er ég að fara að innleiða, fyrst,
Fyrsta skrefið í sauðakóðanum, sem er

421
00:17:26,650 --> 00:17:29,440
á inntak n þætti, ef n er
minna en 2, síðan aftur.

422
00:17:29,440 --> 00:17:31,370
Vitanlega, það er ekki
gilda, svo við fara.

423
00:17:31,370 --> 00:17:33,340
Svo raða vinstri helming þætti.

424
00:17:33,340 --> 00:17:36,220
Svo þýðir að ég ætla að einbeita mér
athygli fyrir aðeins augnablik á þessum

425
00:17:36,220 --> 00:17:37,310
fjórir krakkar hér.

426
00:17:37,310 --> 00:17:39,774
Allt í lagi, hvað ég að gera næst?

427
00:17:39,774 --> 00:17:40,570
>> Áhorfendur: Raða vinstri helminginn.

428
00:17:40,570 --> 00:17:42,780
>> DAVID Malan: Svo nú þarf ég að raða
vinstri helmingur þessara manna.

429
00:17:42,780 --> 00:17:45,580
Því aftur, ætla til sjálfur að
Markmiðið er að raða vinstri helminginn.

430
00:17:45,580 --> 00:17:46,440
Hvernig gerir þú það?

431
00:17:46,440 --> 00:17:49,140
Bara fylgja leiðbeiningunum, jafnvel
þó að við erum að gera það aftur.

432
00:17:49,140 --> 00:17:50,160
Svo raða vinstri helminginn.

433
00:17:50,160 --> 00:17:52,030
Nú er ég flokkun Þessir tveir gaurar.

434
00:17:52,030 --> 00:17:53,563
Hvað kemur næst?

435
00:17:53,563 --> 00:17:54,510
>> Áhorfendur: Raða vinstri helminginn.

436
00:17:54,510 --> 00:17:55,460
>> DAVID Malan: Raða vinstri helminginn.

437
00:17:55,460 --> 00:18:00,680
Svo nú eru þetta, þetta sæti hér,
er listi yfir stærð 1.

438
00:18:00,680 --> 00:18:01,365
Og hvað er nafnið þitt aftur?

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 er hér.

441
00:18:03,690 --> 00:18:07,470
Og svo hún er þegar raðað, því
listinn er af stærð 1.

442
00:18:07,470 --> 00:18:09,490
Hvað geri ég næst?

443
00:18:09,490 --> 00:18:13,680
OK, aftur, vegna þess að þessi listi er
stærð 1, sem er minna en 2.

444
00:18:13,680 --> 00:18:14,320
Þá er það næsta skref?

445
00:18:14,320 --> 00:18:17,490
Og nú þú ert að eins konar
backtrack í huga þínum.

446
00:18:17,490 --> 00:18:19,340
>> Raða rétt helming, sem er -

447
00:18:19,340 --> 00:18:19,570
hvað er nafn þitt?

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
Og svo hvað gerum við nú að
Við hafa a listi af stærð 1?

451
00:18:23,210 --> 00:18:24,440
>> Áhorfendur: Return.

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

453
00:18:24,760 --> 00:18:29,540
Við aftur fyrst, og nú þriðja
skref - og ef ég konar sýna það með

454
00:18:29,540 --> 00:18:33,490
faðma tvö sæti nú, nú ég
að sameina þessar tvær einingar.

455
00:18:33,490 --> 00:18:35,530
Svo nú miður, þá þætti
eru út af röð.

456
00:18:35,530 --> 00:18:39,920
En það er þar sem samruna ferli
byrjar að fá sannfærandi.

457
00:18:39,920 --> 00:18:42,410
>> Þannig að ef þú krakkar gætu staðið upp fyrir bara
stund, ég ætla að þú þarft, í

458
00:18:42,410 --> 00:18:44,170
stund, að stíga á bak stólnum þínum.

459
00:18:44,170 --> 00:18:46,480
Og ef Linda, því 2 er
minni en 4, hví ekki

460
00:18:46,480 --> 00:18:48,130
þú koma í kring fyrst?

461
00:18:48,130 --> 00:18:48,690
Stay there.

462
00:18:48,690 --> 00:18:50,520
Svo Linda, kemur þú í kring fyrst.

463
00:18:50,520 --> 00:18:53,820
>> Nú í raun ef það er bara fylki
við gátum bara færa hana í rauntíma

464
00:18:53,820 --> 00:18:55,360
frá þessum stól því svæði.

465
00:18:55,360 --> 00:18:57,770
Svo ímynda sér að tók stöðug
nokkur skref 1..

466
00:18:57,770 --> 00:18:58,480
Og nú -

467
00:18:58,480 --> 00:19:01,490
en við þurfum að setja þig í
í fyrsta staðsetning hér.

468
00:19:01,490 --> 00:19:03,930
>> Og nú ef að þú gætir komið í kring,
eins vel, við erum að fara að

469
00:19:03,930 --> 00:19:06,300
vera í stað tveggja.

470
00:19:06,300 --> 00:19:09,120
Og jafnvel þótt þetta er eins og það er
taka a á meðan, hvað er gott núna er

471
00:19:09,120 --> 00:19:14,710
að vinstri helmingur af
vinstri helmingur er nú raðað.

472
00:19:14,710 --> 00:19:18,010
Svo hvað var næsta skref, ef við nú
baka lengra í sögunni?

473
00:19:18,010 --> 00:19:18,980
>> Áhorfendur: Hægri helmingur.

474
00:19:18,980 --> 00:19:19,900
>> DAVID Malan: Raða rétt helminginn.

475
00:19:19,900 --> 00:19:21,320
Svo þú krakkar ert að gera þetta, eins og heilbrigður.

476
00:19:21,320 --> 00:19:23,510
Svo ef þú gætir standa upp
fyrir aðeins augnablik?

477
00:19:23,510 --> 00:19:25,192
Og hvað er nafnið þitt?

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, svo er Jess nú vinstri
helmingur af hægri helming.

481
00:19:29,720 --> 00:19:31,400
Og svo er hún listi af stærð 1.

482
00:19:31,400 --> 00:19:32,380
Hún er augljóslega raðað.

483
00:19:32,380 --> 00:19:33,070
Og nafn þitt aftur?

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

485
00:19:33,630 --> 00:19:35,340
>> DAVID Malan: Michelle er augljóslega
listi af stærð 1.

486
00:19:35,340 --> 00:19:36,050
Hún er þegar raðað.

487
00:19:36,050 --> 00:19:38,690
Svo nú galdur gerist,
samruna ferli.

488
00:19:38,690 --> 00:19:39,790
Svo hver er að fara að koma fyrst?

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

490
00:19:41,560 --> 00:19:43,280
Svo ef þú gætir komið í kring aftur.

491
00:19:43,280 --> 00:19:47,090
Rýmið sem við höfum í boði fyrir hana núna
er rétt á bak þessum stól hér.

492
00:19:47,090 --> 00:19:51,580
Og nú ef þú gætir komið aftur eins og heilbrigður,
við höfum nú að vera ljóst, tveir

493
00:19:51,580 --> 00:19:53,810
helminga, hver stærð 2 -

494
00:19:53,810 --> 00:19:57,090
og bara fyrir sakir lýsingu, ef þú
gæti gert smá bili -

495
00:19:57,090 --> 00:19:59,780
eitt eftir hálft hér, eina
hægri helming hér.

496
00:19:59,780 --> 00:20:01,160
>> Baka lengra í sögunni.

497
00:20:01,160 --> 00:20:02,270
Hvaða skref er næst?

498
00:20:02,270 --> 00:20:03,030
>> Áhorfendur: Sameina.

499
00:20:03,030 --> 00:20:04,160
>> DAVID Malan: Svo nú verðum við að sameinast.

500
00:20:04,160 --> 00:20:07,490
Svo allt í lagi, svo nú, sem betur fer, við
bara leystur upp fjórum stólum.

501
00:20:07,490 --> 00:20:11,480
Þannig að við höfum notað tvisvar eins mikið minni, en
við getum gefið Flip-flopping milli

502
00:20:11,480 --> 00:20:12,330
tvö fylki.

503
00:20:12,330 --> 00:20:14,190
Svo sem fjöldi er að koma fyrst?

504
00:20:14,190 --> 00:20:14,850
Svo Michelle, vitanlega.

505
00:20:14,850 --> 00:20:16,680
Svo koma í kring og taka
sætið hér.

506
00:20:16,680 --> 00:20:19,120
Og þá er númer 2 augljóslega
næst, svo þú kemur hingað.

507
00:20:19,120 --> 00:20:21,520
Númer 4, númer 6.

508
00:20:21,520 --> 00:20:23,390
Og aftur, jafnvel þó að það sé
lítill hluti af gangandi ræða,

509
00:20:23,390 --> 00:20:26,010
raunverulega, þetta gæti gerst í stað,
með því að færa einn -

510
00:20:26,010 --> 00:20:26,880
OK, vel spilað.

511
00:20:26,880 --> 00:20:28,350
>> [Hlátur]

512
00:20:28,350 --> 00:20:29,680
>> DAVID Malan: Og nú erum við
í nokkuð góðri þjálfun.

513
00:20:29,680 --> 00:20:34,910
The vinstri helmingur allra
inntak hefur nú verið flokkaður.

514
00:20:34,910 --> 00:20:37,370
Allt í lagi, svo þessir krakkar höfðu
kostur á mínum -

515
00:20:37,370 --> 00:20:40,340
hvernig var það á endanum allar stelpur á
vinstri og allir strákar hægri?

516
00:20:40,340 --> 00:20:42,450
>> OK, svo krakkar 'snúum.

517
00:20:42,450 --> 00:20:44,680
Þannig að ég mun ekki ganga í gegnum
þessum leiðbeiningum.

518
00:20:44,680 --> 00:20:46,550
Við munum sjá hvort við getum sækja aftur
sama sauðakóðanum.

519
00:20:46,550 --> 00:20:50,050
Ef þú vilt fara á undan og standa upp,
og þú krakkar, láta mig gefa þú the mic.

520
00:20:50,050 --> 00:20:52,990
Sjá hvort þú getur ekki endurtaka það
við gerðum bara hér á

521
00:20:52,990 --> 00:20:53,880
hinum enda listanum.

522
00:20:53,880 --> 00:20:59,530
Hver þarf að tala fyrst,
byggt á reiknirit?

523
00:20:59,530 --> 00:21:03,210
Svo útskýrt hvað þú ert að gera áður en
þú gerir einhverjar fótur hreyfingar.

524
00:21:03,210 --> 00:21:05,930
>> Ræðumaður 1: Allt í lagi, svo þar
Ég er vinstri helmingur af

525
00:21:05,930 --> 00:21:07,790
vinstri helming, aftur ég.

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

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

528
00:21:09,250 --> 00:21:10,350
>> Ræðumaður 1: Og svo -

529
00:21:10,350 --> 00:21:11,800
>> DAVID Malan: Hver er
The MIC fara næst?

530
00:21:11,800 --> 00:21:12,920
>> Ræðumaður 1: Næsta númer.

531
00:21:12,920 --> 00:21:14,720
>> Ræðumaður 2: Ég er rétt helmingur
á vinstri hluta sem

532
00:21:14,720 --> 00:21:17,830
vinstri helming, og ég aftur.

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

534
00:21:18,050 --> 00:21:18,550
Þú kemur aftur.

535
00:21:18,550 --> 00:21:21,855
Svo nú er það næsta upp fyrir ykkur?

536
00:21:21,855 --> 00:21:23,740
>> Ræðumaður 2: Við viljum sjá hver er minni.

537
00:21:23,740 --> 00:21:24,200
>> DAVID Malan: Einmitt.

538
00:21:24,200 --> 00:21:24,940
Við viljum að sameina.

539
00:21:24,940 --> 00:21:27,590
Rýmið sem við erum að fara að nota til að sameina
þú inn, jafnvel þó þeir séu

540
00:21:27,590 --> 00:21:30,250
augljóslega raðað nú þegar, við erum að fara
að fylgja sömu reiknirit.

541
00:21:30,250 --> 00:21:31,560
Svo fer sem í aftur fyrst?

542
00:21:31,560 --> 00:21:35,720
Sem 3, og síðan 7.

543
00:21:35,720 --> 00:21:38,570
Og nú fer Mic
að þessir krakkar, OK?

544
00:21:38,570 --> 00:21:43,590
>> Ræðumaður 3: Ég er rétt helmingur af
vinstri helming, og n mín er minna en

545
00:21:43,590 --> 00:21:45,048
1, þannig að ég ætla bara að fara að fara -

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

547
00:21:46,380 --> 00:21:49,450
>> Ræðumaður 4: Ég er rétt helmingur af
hægri helmingur hægri helming, og ég er

548
00:21:49,450 --> 00:21:51,740
einnig einn maður, svo ég er
fara til baka.

549
00:21:51,740 --> 00:21:52,990
Svo nú erum við sameinast.

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

551
00:21:55,140 --> 00:21:56,150
>> Ræðumaður 3: Svo við förum aftur.

552
00:21:56,150 --> 00:21:57,160
>> DAVID Malan: Svo þú fara inn aftur.

553
00:21:57,160 --> 00:21:59,200
Svo 5 fer fyrst, síðan 8.

554
00:21:59,200 --> 00:22:01,240
Og nú áhorfendur, sem er
stíga við verðum að nú trekkja

555
00:22:01,240 --> 00:22:02,200
Til baka í huga okkar?

556
00:22:02,200 --> 00:22:02,940
>> Áhorfendur: Sameina.

557
00:22:02,940 --> 00:22:07,270
>> DAVID Malan: Sameina vinstri helming og hægri
helmingur af upprunalegum vinstri helming.

558
00:22:07,270 --> 00:22:08,840
Svo núna -

559
00:22:08,840 --> 00:22:10,520
og bara til að gera þetta skýrar,
gera smá pláss

560
00:22:10,520 --> 00:22:11,690
milli þín tveir gaurar.

561
00:22:11,690 --> 00:22:13,800
Svo nú er að það tveir listar,
vinstri og hægri.

562
00:22:13,800 --> 00:22:18,320
Svo hvernig gera við sameinast nú þú krakkar í
framan sætaröð aftur?

563
00:22:18,320 --> 00:22:19,600
>> 3. fer fyrst.

564
00:22:19,600 --> 00:22:20,850
Þá 5., vitanlega.

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

566
00:22:23,110 --> 00:22:27,330
Þá 7, og nú 8.

567
00:22:27,330 --> 00:22:28,710
OK, og nú erum við?

568
00:22:28,710 --> 00:22:29,650
>> Áhorfendur: Ekki gert.

569
00:22:29,650 --> 00:22:32,440
>> DAVID Malan: Ekki gert, vegna þess að
Vitanlega, það er eitt skref eftir.

570
00:22:32,440 --> 00:22:35,720
En aftur, ástæðan ég er að nota þetta
hrognamál eins og "til baka í huga þínum,"

571
00:22:35,720 --> 00:22:37,160
það er vegna þess að það er í raun
hvað er að gerast.

572
00:22:37,160 --> 00:22:39,610
Við erum að fara í gegnum öll þessi skref,
en við erum konar hlé fyrir

573
00:22:39,610 --> 00:22:42,480
stund, köfun dýpra inn í
reiknirit, stansa um stund,

574
00:22:42,480 --> 00:22:45,840
köfun dýpra inn í reiknirit og
nú verðum við að raða á baka í okkar

575
00:22:45,840 --> 00:22:49,430
huga og losa öllum þessum lögum
sem við höfum svona sett í bið.

576
00:22:49,430 --> 00:22:51,790
>> Svo nú höfum við tvo lista af stærð 4.

577
00:22:51,790 --> 00:22:54,790
Ef þú krakkar gætu staðið upp eitt síðasta skipti
og gera smá pláss hér til

578
00:22:54,790 --> 00:22:57,230
gera ljóst að þetta er vinstri
helmingur af upprunalegu, the

579
00:22:57,230 --> 00:22:58,620
hægri hluta upprunalega.

580
00:22:58,620 --> 00:23:01,060
Hver er fyrsta talan sem við
þarf að draga inn aftur?

581
00:23:01,060 --> 00:23:01,870
Michelle, auðvitað.

582
00:23:01,870 --> 00:23:03,230
>> Þannig að við setjum Michelle hér.

583
00:23:03,230 --> 00:23:05,080
Og hver hefur númer 2?

584
00:23:05,080 --> 00:23:06,440
Númer 2 kemur aftur eins og heilbrigður.

585
00:23:06,440 --> 00:23:07,800
Númer 3?

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

587
00:23:08,510 --> 00:23:16,570
Númer 4, númer 5, númer 6,
númer 7, og númer 8.

588
00:23:16,570 --> 00:23:18,850
>> OK, svo það var eins og a einhver fjöldi
af skrefum, fyrir viss.

589
00:23:18,850 --> 00:23:22,390
En nú skulum sjá hvort við getum ekki staðfest
konar innsæi að þetta

590
00:23:22,390 --> 00:23:26,190
reiknirit grundvallaratriðum, sérstaklega þar sem
n fær mjög stór, eins og við höfum séð

591
00:23:26,190 --> 00:23:29,170
með fjör, er
grundvallaratriðum hraðar.

592
00:23:29,170 --> 00:23:33,400
Svo ég halda þetta reiknirit, í versta
málið og jafnvel í besta tilfelli,

593
00:23:33,400 --> 00:23:36,160
er stór O n sinnum log n.

594
00:23:36,160 --> 00:23:39,160
Það er, það er einhver þáttur um þetta
reiknirit sem tekur n skrefum, en

595
00:23:39,160 --> 00:23:43,110
það er annar þáttur einhversstaðar í
sem endurtekning, að lykkja, sem

596
00:23:43,110 --> 00:23:44,410
tekur log n skrefum.

597
00:23:44,410 --> 00:23:49,154
Getum við sett fingur okkar á hvað þeir
tvær tölur eru að vísa til?

598
00:23:49,154 --> 00:23:51,320
Jæja, þar sem -

599
00:23:51,320 --> 00:23:54,160
Hvar Mic fara?

600
00:23:54,160 --> 00:23:58,660
>> Ræðumaður 1: Myndi þig n vera
brjóta okkur upp í tvo -

601
00:23:58,660 --> 00:23:59,630
deila með tveimur, í meginatriðum.

602
00:23:59,630 --> 00:24:00,120
>> DAVID Malan: Einmitt.

603
00:24:00,120 --> 00:24:03,000
Hvenær við sjáum í hvaða reiknirit svona
langt, það hefur verið þetta mynstur

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

605
00:24:04,200 --> 00:24:05,700
Og það er yfirleitt minnkað
eitthvað sem er

606
00:24:05,700 --> 00:24:07,100
lógaritmískum, skráðu þig stöð 2..

607
00:24:07,100 --> 00:24:10,180
En það gæti virkilega verið nokkuð,
en tengja stöð 2.

608
00:24:10,180 --> 00:24:11,330
>> Nú hvað um n?

609
00:24:11,330 --> 00:24:14,550
Ég get séð að við skipt konar þig
krakkar - skipt þig, skipt þér,

610
00:24:14,550 --> 00:24:15,910
skipt þig, skipt þig.

611
00:24:15,910 --> 00:24:18,760
Hvar er endirinn koma frá?

612
00:24:18,760 --> 00:24:19,810
>> Svo það er samruna.

613
00:24:19,810 --> 00:24:20,610
Vegna hugsa um það.

614
00:24:20,610 --> 00:24:25,420
Þegar þú sameina átta manns saman,
þar helmingur af þeim eru sett af fjórum

615
00:24:25,420 --> 00:24:27,770
og hinn helmingurinn eru önnur
setja af fjórum, hvernig gera þú fara

616
00:24:27,770 --> 00:24:28,820
um að gera að sameina?

617
00:24:28,820 --> 00:24:30,830
Jæja, þið gerði það
nokkuð innsæi.

618
00:24:30,830 --> 00:24:34,140
>> En ef ég gerði í staðinn aðeins meira
methodically, gæti ég hef bent á

619
00:24:34,140 --> 00:24:38,090
að leftmost manneskja fyrst með vinstri minn
hönd, benti á lengst til vinstri mann

620
00:24:38,090 --> 00:24:42,080
þess hluta með hægri hendi minni, og
bara síðar gekk í gegnum

621
00:24:42,080 --> 00:24:46,990
lista, bendir á minnstu frumefni
hvert skipti, færa fingur mína yfir og

622
00:24:46,990 --> 00:24:48,970
yfir og þarf allan listann.

623
00:24:48,970 --> 00:24:51,890
En hvað er lykillinn um þetta samruna
aðferð er ég að bera saman þessar pör

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

625
00:24:53,460 --> 00:24:57,270
Frá hægri hluta og frá vinstri
helmingur, ég aldrei einu sinni backtracking.

626
00:24:57,270 --> 00:25:00,570
>> Svo sameinast sjálft er að taka
ekki meira en n skrefum.

627
00:25:00,570 --> 00:25:03,250
Og hversu oft gerði ég
að gera það að sameina?

628
00:25:03,250 --> 00:25:07,150
Jæja, ekki meira en n, og við bara
sá að með endanlegri sameiningu.

629
00:25:07,150 --> 00:25:13,120
Og svo ef þú gerir eitthvað sem tekur
log n skrefum n sinnum, eða öfugt,

630
00:25:13,120 --> 00:25:15,210
það er að fara að gefa okkur n sinnum log n.

631
00:25:15,210 --> 00:25:16,310
>> Og hvers vegna er þetta betur?

632
00:25:16,310 --> 00:25:19,600
Jæja, ef við vitum nú þegar að skrá þig
n er betri en n - ekki satt?

633
00:25:19,600 --> 00:25:22,590
Við sáum í tvöfaldur leit, símaskrána
dæmi, log n var ákveðið

634
00:25:22,590 --> 00:25:23,760
betri en línulegt.

635
00:25:23,760 --> 00:25:28,420
Svo það þýðir n sinnum log n er
örugglega betur en n sinnum annað

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

637
00:25:30,390 --> 00:25:32,400
Og það er það sem við teljum að lokum.

638
00:25:32,400 --> 00:25:34,928
>> Svo stór umferð lófaklapp, ef
við gátum, fyrir þessar krakkar.

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

640
00:25:38,920 --> 00:25:41,550
>> DAVID Malan: og skilnaði gjafir -
þú getur haldið tölur,

641
00:25:41,550 --> 00:25:44,010
ef þú vilt.

642
00:25:44,010 --> 00:25:45,620
Og skilnaði gjöf þín, eins og venjulega.

643
00:25:45,620 --> 00:25:47,290
Ó, og við munum senda þér
myndefni, Michelle.

644
00:25:47,290 --> 00:25:48,343
Þakka þér.

645
00:25:48,343 --> 00:25:49,250
Allt í lagi.

646
00:25:49,250 --> 00:25:50,400
Hjálp sjálfur til streitu boltanum.

647
00:25:50,400 --> 00:25:54,110
>> Og láta mig draga upp, í millitíðinni,
vinkona Rob Bowden að bjóða

648
00:25:54,110 --> 00:25:59,520
nokkuð mismunandi sýn á þetta,
þar sem þú getur hugsa um þessar

649
00:25:59,520 --> 00:26:01,280
skref gerast í nokkru
mismunandi hátt.

650
00:26:01,280 --> 00:26:04,750
Í staðreynd, the setja-upp fyrir það Rob er um
til að sýna okkur ráð sem við höfum

651
00:26:04,750 --> 00:26:09,030
þegar gert er að deila upp af
stór listi í átta litlum listum,

652
00:26:09,030 --> 00:26:10,570
hver af stærð 1.

653
00:26:10,570 --> 00:26:13,350
>> Þannig að við erum að breyta því sauðakóðanum A
svolítið bara til að raða í fá á

654
00:26:13,350 --> 00:26:15,320
Kjarni hugmynd um hvernig sameiningu verk.

655
00:26:15,320 --> 00:26:17,600
En gangi tíma hvað
hann er að fara að gera er enn

656
00:26:17,600 --> 00:26:19,110
að fara að vera sú sama.

657
00:26:19,110 --> 00:26:23,540
Og aftur, setja upp hér er sú að hann er
hafin með átta lista af stærð 1.

658
00:26:23,540 --> 00:26:27,730
Svo þú hefur misst hluta þar sem hann er
í raun gert að log n, log n, log n

659
00:26:27,730 --> 00:26:31,205
deila um inntak.

660
00:26:31,205 --> 00:26:32,120
>> [Vídeó spilun]

661
00:26:32,120 --> 00:26:33,615
>> -Það er það fyrir skref eitt.

662
00:26:33,615 --> 00:26:38,270
Fyrir sporinu ítrekað
sameinast pör af listum.

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

664
00:26:39,210 --> 00:26:41,270
Aðeins hljóð kemur
út af tölvunni minni.

665
00:26:41,270 --> 00:26:42,520
Við skulum reyna þetta aftur.

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

667
00:26:45,330 --> 00:26:48,310
>> -Bara geðþótta velja hvaða -
nú höfum við fjóra lista.

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

669
00:26:51,590 --> 00:26:52,120
Læra áður.

670
00:26:52,120 --> 00:26:53,040
>> DAVID Malan: Það sem við förum.

671
00:26:53,040 --> 00:27:00,510
>> -Merging 108 og 15, enda við
upp með lista 15, 108.

672
00:27:00,510 --> 00:27:07,170
Sameiningu 50 og 4, við
endað með 4, 50.

673
00:27:07,170 --> 00:27:12,990
Sameiningu 8 og 42, við
endað með 8, 42.

674
00:27:12,990 --> 00:27:19,970
Og sameina 23 og 16, við
endar með 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Nú allir listar okkar eru stærð 2.

676
00:27:23,270 --> 00:27:26,690
Takið eftir að hver af
fjórir listar er raðað.

677
00:27:26,690 --> 00:27:29,450
Þannig að við getum byrjað að sameina
pör af lista aftur.

678
00:27:29,450 --> 00:27:38,420
Að sameina 15 og 108 og 4 og 50, við
Fyrsta taka 4, þá 15, þá

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

680
00:27:41,500 --> 00:27:50,610
Sameina 8, 42 og 16, 23, taka við fyrst
8, þá 16, þá 23,

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

682
00:27:52,700 --> 00:27:57,600
>> Svo nú höfum við bara tveir listar stærð
4, sem hver um sig er vel flokkað.

683
00:27:57,600 --> 00:28:01,170
Svo nú erum við að sameina þessar tvær listum.

684
00:28:01,170 --> 00:28:11,835
Fyrst, við tökum 4, þá erum við að taka á
8, þá erum við að taka 15, þá 16, þá

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

686
00:28:19,456 --> 00:28:19,872
>> [END vídeó spilun]

687
00:28:19,872 --> 00:28:23,430
>> DAVID Malan: Aftur, tilkynning, aldrei hann
snert á tilteknu bolla oftar en einu sinni

688
00:28:23,430 --> 00:28:24,860
eftir að fara út fyrir hann.

689
00:28:24,860 --> 00:28:26,200
Svo hann er aldrei endurtaka.

690
00:28:26,200 --> 00:28:29,850
Svo hann er alltaf að færa til hliðar,
og það er þar sem við fengum n okkar.

691
00:28:29,850 --> 00:28:33,290
>> Hvers vegna ekki láta mig draga upp einn fjör
sem við sáum fyrr, en í þetta skiptið

692
00:28:33,290 --> 00:28:35,110
með áherslu eingöngu á sameiningu tagi.

693
00:28:35,110 --> 00:28:38,030
Leyfðu mér að fara á undan og zoom
í á þetta hér.

694
00:28:38,030 --> 00:28:42,530
Fyrst láta mig velja af handahófi inntak,
stækka þetta, og þú getur raða á sjá

695
00:28:42,530 --> 00:28:46,600
hvað við tók sem sjálfsagðan hlut, fyrr,
sameinast tegund er í raun að gera.

696
00:28:46,600 --> 00:28:50,330
>> Svo eftir því að þú færð þessi helminga eða
þessar fjórðu eða þessir áttundu hlutar sem

697
00:28:50,330 --> 00:28:53,140
vandamál sem allt í einu
byrja að taka góða mynd.

698
00:28:53,140 --> 00:28:57,070
Og svo að lokum, að sjá þig á
enda sem Bam,

699
00:28:57,070 --> 00:28:58,860
allt er sameinað saman.

700
00:28:58,860 --> 00:29:01,690
>> Svo þetta eru bara þrír mismunandi
tekur á sömu hugmynd.

701
00:29:01,690 --> 00:29:05,980
En lykillinn innsýn, rétt eins og skipta
og sigra í fyrsta bekk,

702
00:29:05,980 --> 00:29:10,640
var að við ákváðum að einhvern veginn skipta
vandamálið í eitthvað stórt, í

703
00:29:10,640 --> 00:29:14,760
eitthvað svoleiðis eins í anda,
en minni og minni og minni

704
00:29:14,760 --> 00:29:15,660
og minni.

705
00:29:15,660 --> 00:29:18,420
>> Nú annað skemmtileg leið til að raða á hugsa
um þessum, jafnvel þótt það sé ekki

706
00:29:18,420 --> 00:29:20,520
fara að gefa þér sama innsæi
skilningur, er

707
00:29:20,520 --> 00:29:21,640
Eftirfarandi fjör.

708
00:29:21,640 --> 00:29:25,400
Þannig að þetta er myndband sem einhver setti saman
sem tengist mismunandi

709
00:29:25,400 --> 00:29:29,970
hljóðum með mismunandi rekstri
innsetning tagi, fyrir sameiningu tagi, og

710
00:29:29,970 --> 00:29:31,150
fyrir a par af öðrum.

711
00:29:31,150 --> 00:29:32,330
Svo í augnablikinu, ég er að fara að lemja Spila.

712
00:29:32,330 --> 00:29:33,600
Það er um eina mínútu löng.

713
00:29:33,600 --> 00:29:37,410
Og jafnvel þó að þú getur enn séð
mynstur að gerast, í þetta sinn sem þú getur

714
00:29:37,410 --> 00:29:41,420
einnig heyra hvernig þessi reiknirit eru
framkvæma á annan hátt og með

715
00:29:41,420 --> 00:29:43,950
nokkuð mismunandi mynstur.

716
00:29:43,950 --> 00:29:45,830
>> Þetta er innsetning tagi.

717
00:29:45,830 --> 00:29:50,400
>> [Tónar LEIKA]

718
00:29:50,400 --> 00:29:52,400
>> DAVID Malan: Það aftur er að reyna
að setja hver þáttur

719
00:29:52,400 --> 00:29:52,900
inn þar sem það tilheyrir.

720
00:29:52,900 --> 00:29:54,628
Þetta er kúla tegund.

721
00:29:54,628 --> 00:30:10,097
>> [Tónar LEIKA]

722
00:30:10,097 --> 00:30:13,630
>> DAVID Malan: Og þú getur raða á líður
hversu tiltölulega lítið að vinna það er að gera

723
00:30:13,630 --> 00:30:15,834
á hverju skrefi.

724
00:30:15,834 --> 00:30:20,470
Þetta er það sem tediousness hljómar eins.

725
00:30:20,470 --> 00:30:21,472
>> [Tónar LEIKA]

726
00:30:21,472 --> 00:30:25,222
>> DAVID Malan: Þetta er val tagi,
þar við að velja frumefni sem við viljum með því að

727
00:30:25,222 --> 00:30:28,845
fara í gegnum aftur og aftur og aftur
og setja það í upphafi.

728
00:30:28,845 --> 00:30:37,674
>> [Tónar LEIKA]

729
00:30:37,674 --> 00:30:43,970
>> DAVID Malan: Þetta er steypa tegund, sem
þú getur í raun að byrja að líða.

730
00:30:43,970 --> 00:30:51,810
>> [Tónar LEIKA]

731
00:30:51,810 --> 00:30:54,770
>> [Hlátur]

732
00:30:54,770 --> 00:30:58,395
>> DAVID Malan: Eitthvað sem heitir dvergur
tegund, sem við höfum ekki horft á.

733
00:30:58,395 --> 00:31:13,630
>> [Tónar LEIKA]

734
00:31:13,630 --> 00:31:17,910
>> DAVID Malan: Svo láta mig sjá, nú,
annars hugar eins og þú ert vonandi af

735
00:31:17,910 --> 00:31:21,110
tónlist, ef ég get miði lítið
hluti af stærðfræði hér.

736
00:31:21,110 --> 00:31:24,850
Þannig að það er Fjórða leiðin sem við getum
hugsa um hvað það þýðir að þetta

737
00:31:24,850 --> 00:31:29,210
aðgerðir til að vera hraðari en sjálfur
að við höfum séð áður.

738
00:31:29,210 --> 00:31:32,470
Og ef þú ætlar að koma á námskeiðið frá
A stærðfræði bakgrunnur, þú

739
00:31:32,470 --> 00:31:36,030
raunverulega vita kannski nú þegar að þú
getur smellu inn orð á þessari tækni -

740
00:31:36,030 --> 00:31:40,400
þ.e. endurkvæmni, fall
sem kallar einhvern veginn sig.

741
00:31:40,400 --> 00:31:44,780
>> Og aftur, muna að Mergesort
sauðakóðanum var endurkvæma í skilningi

742
00:31:44,780 --> 00:31:48,460
að eitt af skrefum Mergesort skips
var að hringja svona -

743
00:31:48,460 --> 00:31:49,740
það er, sjálft.

744
00:31:49,740 --> 00:31:52,480
En sem betur fer, vegna þess að við haldið
starf tegund, eða sameina flokka,

745
00:31:52,480 --> 00:31:55,880
sérstaklega á minni og minni
og minni lista, loksins við

746
00:31:55,880 --> 00:32:00,005
botninum þökk hvað við munum kalla
grunn tilfelli, the harður-dulmáli mál sem

747
00:32:00,005 --> 00:32:04,270
sagði að ef listinn er lítið, minna en 2
í því tilfelli, bara aftur strax.

748
00:32:04,270 --> 00:32:07,550
Ef við ekki hafa það sérstaka mál, sem
reiknirit myndi aldrei botn út,

749
00:32:07,550 --> 00:32:11,010
og þú myndi örugglega fá inn í
Infinite Loop sannarlega að eilífu.

750
00:32:11,010 --> 00:32:14,330
>> En geri ráð fyrir að við vildum nú setja
nokkrar tölur um þetta, aftur, með n

751
00:32:14,330 --> 00:32:15,660
og stærð inntak.

752
00:32:15,660 --> 00:32:18,680
Og ég vildi spyrja þig, hvað er
heildartíminn þátt í

753
00:32:18,680 --> 00:32:19,800
gangi Mergesort?

754
00:32:19,800 --> 00:32:22,960
Eða almennt, hvað er
kostnaður við það í tíma?

755
00:32:22,960 --> 00:32:24,730
>> Jæja það er nokkuð auðvelt að mæla það.

756
00:32:24,730 --> 00:32:29,010
Ef n er minna en 2, þann tíma sem
í flokka n þætti,

757
00:32:29,010 --> 00:32:30,480
þar sem n er 2, er 0.

758
00:32:30,480 --> 00:32:31,410
Vegna þess að við aftur bara.

759
00:32:31,410 --> 00:32:32,510
Það er engin vinna til að gera.

760
00:32:32,510 --> 00:32:35,660
Nú öllum líkindum, kannski er það eitt skref eða tvö
skref til að reikna út hversu mikið af

761
00:32:35,660 --> 00:32:38,420
vinna, en það er nógu nálægt til 0 að
Ég ætla bara að fara að segja engin vinna er

762
00:32:38,420 --> 00:32:40,940
krafist ef listinn er svo lítill
að uninteresting.

763
00:32:40,940 --> 00:32:42,580
>> En þetta mál er áhugavert.

764
00:32:42,580 --> 00:32:47,320
Endurkvæma Málið var útibú
The sauðakóðanum sem sagt annað, flokka

765
00:32:47,320 --> 00:32:52,000
vinstri helming, raða rétt
helmingur, sameina tvo helminga.

766
00:32:52,000 --> 00:32:55,530
Nú hvers vegna er þetta tjáning
tákna sem kostnað?

767
00:32:55,530 --> 00:32:58,690
Jæja, T í n þýðir bara
tími til að raða n þætti.

768
00:32:58,690 --> 00:33:03,070
Og þá á hægri hönd hlið af the
jafngildir skilti þarna, T á n skipt

769
00:33:03,070 --> 00:33:06,600
eftir 2 er vísað til kostnaðar við hvað?

770
00:33:06,600 --> 00:33:07,570
Flokkun vinstri helminginn.

771
00:33:07,570 --> 00:33:10,990
Hin T af n deilt með 2 er
væntanlega að vísa til kostnaðar við

772
00:33:10,990 --> 00:33:12,390
raða rétt helminginn.

773
00:33:12,390 --> 00:33:14,590
>> Og þá plús n?

774
00:33:14,590 --> 00:33:15,420
Er samruni.

775
00:33:15,420 --> 00:33:19,120
Vegna þess að ef þú hefur tvo lista, einn af
stærð n yfir 2 og annar af stærð n

776
00:33:19,120 --> 00:33:22,580
yfir 2, þú þarft að í raun snerta
hver af þessum þáttum, rétt eins og Rob

777
00:33:22,580 --> 00:33:24,990
snert hvert bolla, og bara
eins og við bent á hvert af

778
00:33:24,990 --> 00:33:26,310
sjálfboðaliðar á sviðinu.

779
00:33:26,310 --> 00:33:28,790
Svo er n kostnað af samruna.

780
00:33:28,790 --> 00:33:31,780
>> Nú því miður, þetta uppskrift
er einnig sjálft endurkvæma.

781
00:33:31,780 --> 00:33:36,390
Svo ef spurði, ef n er, segjum,
16, ef það er 16 manns á sviðinu

782
00:33:36,390 --> 00:33:40,670
eða 16 bollar í the vídeó, hversu margir alls
skref tekur það að raða þeim

783
00:33:40,670 --> 00:33:41,550
með sameiningu tagi?

784
00:33:41,550 --> 00:33:45,790
Það er í raun ekki augljóst svar,
því nú þú þarft að raða á

785
00:33:45,790 --> 00:33:48,500
endurkvæmur svara þessari formúlu.

786
00:33:48,500 --> 00:33:51,190
>> En það er allt í lagi, vegna þess að láta mig leggja
að við gera eftirfarandi.

787
00:33:51,190 --> 00:33:56,670
Tíma þátt til að raða 16 manns eða
16 bollar er að fara að vera fulltrúa

788
00:33:56,670 --> 00:33:58,020
almennt T af 16.

789
00:33:58,020 --> 00:34:01,400
En það jafngildir, í samræmi við okkar
fyrri uppskrift, 2 sinnum sú upphæð

790
00:34:01,400 --> 00:34:04,780
tíma það tekur að raða
8 bollar auk 16.

791
00:34:04,780 --> 00:34:08,590
Og aftur, plús 16 er kominn tími til að sameinast,
og tvisvar sinnum T á 8 er

792
00:34:08,590 --> 00:34:10,790
tími til að raða vinstri helming og hægri helmingur.

793
00:34:10,790 --> 00:34:11,989
>> En aftur, þetta er ekki nóg.

794
00:34:11,989 --> 00:34:13,210
Við verðum að kafa í dýpri.

795
00:34:13,210 --> 00:34:16,409
Þetta þýðir að við verðum að svara
spurning, hvað er T af 8?

796
00:34:16,409 --> 00:34:19,610
Jæja T af 8 er bara 2
sinnum T á 4 plús 8.

797
00:34:19,610 --> 00:34:20,520
Jæja, hvað er T í 4?

798
00:34:20,520 --> 00:34:23,780
T á 4 er bara 2 sinnum T á 2 plús 4.

799
00:34:23,780 --> 00:34:25,489
Jæja, hvað er T í 2?

800
00:34:25,489 --> 00:34:29,030
T af 2 er bara 2 sinnum T á 1 plús 2.

801
00:34:29,030 --> 00:34:31,940
>> Og aftur, við erum konar að fá
fastur í þessari lotu.

802
00:34:31,940 --> 00:34:34,790
En það er um að lemja það
svokallaða grunn tilfelli.

803
00:34:34,790 --> 00:34:37,310
Vegna þess að það er T 1, gerði við kröfu?

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

805
00:34:37,810 --> 00:34:39,730
Svo nú loksins getum við vinna aftur á bak.

806
00:34:39,730 --> 00:34:44,290
>> Ef T 1. er 0, ég get nú farið aftur upp einn
lína til þennan gaur hérna, og ég get

807
00:34:44,290 --> 00:34:46,330
stinga í 0 fyrir T frá 1..

808
00:34:46,330 --> 00:34:51,770
Svo það þýðir að það jafngildir 2 sinnum núll,
annars þekkt sem 0, auk 2.

809
00:34:51,770 --> 00:34:53,739
Og svo er að allt tjáning 2..

810
00:34:53,739 --> 00:34:58,740
>> Nú ef ég taka T í 2, sem svar
er 2, stinga því inn í miðju línu, T

811
00:34:58,740 --> 00:35:02,740
af 4, sem gefur mér 2 sinnum
2 plus 4, þannig að 8.

812
00:35:02,740 --> 00:35:07,080
Ef ég stinga þá í 8 til fyrri
lína, sem gefur mér 2 sinnum 8, 16.

813
00:35:07,080 --> 00:35:12,470
Og ef við höldum áfram þá að með
24, að bæta í 16, fáum við loksins

814
00:35:12,470 --> 00:35:13,820
gildi 64..

815
00:35:13,820 --> 00:35:18,480
>> Nú þegar í sjálfu konar talar
ekkert í n merki, the

816
00:35:18,480 --> 00:35:20,700
stór O, the ómega sem við höfum
verið að tala um.

817
00:35:20,700 --> 00:35:24,890
En það kemur í ljós að 64 er örugglega
16, the stærð af the inntak,

818
00:35:24,890 --> 00:35:27,110
tengja stöð 2 af 16.

819
00:35:27,110 --> 00:35:30,200
Og ef þetta er svolítið framandi, bara
hugsa til baka, og það mun koma aftur

820
00:35:30,200 --> 00:35:30,700
til þín á endanum.

821
00:35:30,700 --> 00:35:33,775
Ef þetta er að tengja stöð 2, það er eins og 2
hækkuð í það sem gefur þér 16?

822
00:35:33,775 --> 00:35:36,380
Ó, það er 4, svo það er 16 sinnum 4..

823
00:35:36,380 --> 00:35:39,380
>> Og aftur er það ekki máli ef þetta
er tegund af hazy minni núna.

824
00:35:39,380 --> 00:35:43,720
En nú, að taka á trú
að 16 Log 16 er 64.

825
00:35:43,720 --> 00:35:46,590
Og svo reyndar með þessari einföldu Sanity
athuga, höfum við staðfest -

826
00:35:46,590 --> 00:35:48,250
en ekki reynst formlega -

827
00:35:48,250 --> 00:35:52,800
að keyra tími sameinast
tegund er örugglega n log n.

828
00:35:52,800 --> 00:35:53,790
>> Svo ekki slæmt.

829
00:35:53,790 --> 00:35:57,260
Það er örugglega betra en að
reiknirit sem við höfum séð hingað til, og

830
00:35:57,260 --> 00:36:00,710
það er vegna þess að við höfum skuldsett, einn,
tækni sem kallast endurkvæmni.

831
00:36:00,710 --> 00:36:03,880
En meira áhugavert en það, sem
hugmyndin að deila og sigra.

832
00:36:03,880 --> 00:36:07,460
Aftur, sannarlega viku 0 efni sem
jafnvel nú er endurtekin í

833
00:36:07,460 --> 00:36:08,740
meira sannfærandi hátt.

834
00:36:08,740 --> 00:36:11,750
>> Nú skemmtilegur lítill æfa, ef þú hefur
aldrei gert þetta - og þú sennilega

835
00:36:11,750 --> 00:36:14,660
myndi ekki hafa, því svona eðlilegt
fólk held ekki að gera þetta.

836
00:36:14,660 --> 00:36:20,650
En ef ég fer á google.com og ef
Ég vil læra eitthvað um

837
00:36:20,650 --> 00:36:22,356
endurkvæmni, Enter.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [Hlátur]

840
00:36:29,058 --> 00:36:32,030
[MEIRA hlátur]

841
00:36:32,030 --> 00:36:33,385
DAVID Malan: Bad brandari hægt að breiða út.

842
00:36:33,385 --> 00:36:34,450
[Hlátur]

843
00:36:34,450 --> 00:36:36,970
DAVID Malan: Bara ef, það er þarna.

844
00:36:36,970 --> 00:36:38,710
Ég vissi ekki að stafa það rangt,
og það er brandari.

845
00:36:38,710 --> 00:36:40,810
Allt í lagi.

846
00:36:40,810 --> 00:36:42,950
Útskýra það að fólk við hliðina á þér ef
það hefur ekki alveg smellt bara ennþá.

847
00:36:42,950 --> 00:36:47,650
En endurkvæmni, almennt, vísar
til að vinna að virka starf

848
00:36:47,650 --> 00:36:51,430
sig, eða fleiri almennt, deila með
vandamál í eitthvað sem hægt er að

849
00:36:51,430 --> 00:36:56,220
leyst piecemeal með því að leysa eins
fulltrúa vandamál.

850
00:36:56,220 --> 00:36:58,400
>> Breyting gír Jæja, við skulum
fyrir aðeins augnablik.

851
00:36:58,400 --> 00:37:00,840
Við eins og að enda á ákveðnum cliffhangers,
þannig að við skulum byrja að setja

852
00:37:00,840 --> 00:37:05,870
sviðið, í nokkrar mínútur,
á mjög einfaldri hugmynd -

853
00:37:05,870 --> 00:37:07,620
sem á að skipta tvo þætti, ekki satt?

854
00:37:07,620 --> 00:37:10,040
Öll þessi reiknirit sem við höfum verið
að tala um á síðustu tveimur

855
00:37:10,040 --> 00:37:12,420
fyrirlestrar sér sumir
konar skipta.

856
00:37:12,420 --> 00:37:14,630
Í dag var visualized af þeim fá
upp úr stólum sínum og

857
00:37:14,630 --> 00:37:18,570
ganga um, en í kóða, við vildi
bara taka stak úr einu fylki

858
00:37:18,570 --> 00:37:20,370
og plop það í annað.

859
00:37:20,370 --> 00:37:21,880
>> Svo hvernig við förum að gera þetta?

860
00:37:21,880 --> 00:37:24,850
Jæja, láttu mig fara á undan og skrifa
a fljótur program hér.

861
00:37:24,850 --> 00:37:31,600
Ég ætla að fara á undan og gera
þetta á eftirfarandi hátt.

862
00:37:31,600 --> 00:37:33,910
Við skulum kalla þetta -

863
00:37:33,910 --> 00:37:38,070
Hvað viljum við að kalla þetta einn?

864
00:37:38,070 --> 00:37:38,650
>> Reyndar ekki.

865
00:37:38,650 --> 00:37:39,420
Leyfðu mér að baka.

866
00:37:39,420 --> 00:37:41,220
Ég vil ekki að gera það
cliffhanger enn.

867
00:37:41,220 --> 00:37:42,270
Það mun spilla gaman.

868
00:37:42,270 --> 00:37:43,600
Skulum gera þetta í staðinn.

869
00:37:43,600 --> 00:37:47,430
>> Segjum að ég vil skrifa smá
forrit og það nær nú þetta

870
00:37:47,430 --> 00:37:48,700
Hugmyndin um endurkvæmni.

871
00:37:48,700 --> 00:37:50,370
Ég fékk svona á undan mér þar.

872
00:37:50,370 --> 00:37:51,420
Ég ætla að gera eftirfarandi.

873
00:37:51,420 --> 00:38:00,220
>> Fyrst, eru fljótleg af venjulegu io.h,
og jafnframt fela í sér að cs50.h.

874
00:38:00,220 --> 00:38:03,200
Og þá ætla ég að fara á undan
og lýsa int helstu ógilt

875
00:38:03,200 --> 00:38:04,360
á hefðbundinn hátt.

876
00:38:04,360 --> 00:38:07,920
Ég sá að ég hef misnamed skrána, svo
láta mig bæta bara. c eftirnafn hér svo

877
00:38:07,920 --> 00:38:09,510
að við getum þýða það almennilega.

878
00:38:09,510 --> 00:38:10,970
Byrja á þessum valkosti.

879
00:38:10,970 --> 00:38:13,290
>> Og virka ég vil skrifa, alveg
einfaldlega er, sá sem spyr

880
00:38:13,290 --> 00:38:16,210
notandi fyrir a tala og þá bætir upp
allar tölur á milli að

881
00:38:16,210 --> 00:38:19,920
númer og segja, 0.

882
00:38:19,920 --> 00:38:22,510
Svo fyrst ég ætla að fara á undan
og lýsa INT n.

883
00:38:22,510 --> 00:38:24,760
Þá vil ég afrita nokkur númer sem
við höfum notað um tíma.

884
00:38:24,760 --> 00:38:26,660
Þó eitthvað sé satt.

885
00:38:26,660 --> 00:38:28,000
Ég kem aftur til að í smástund.

886
00:38:28,000 --> 00:38:29,010
>> Hvað vil ég að gera?

887
00:38:29,010 --> 00:38:33,460
Mig langar að segja printf jákvæð
heiltala vinsamlegast.

888
00:38:33,460 --> 00:38:36,130
Og þá ætla ég að
segja n fær fá int.

889
00:38:36,130 --> 00:38:38,800
Svo aftur, sumir boilerplate númer
sem við höfum notað áður.

890
00:38:38,800 --> 00:38:40,810
Og ég ætla að gera þetta
á meðan n er minna en 1.

891
00:38:40,810 --> 00:38:44,120
Þannig að þetta mun tryggja að notandinn
gefur mér jákvæð heiltala.

892
00:38:44,120 --> 00:38:45,490
>> Og nú ætla ég að gera eftirfarandi.

893
00:38:45,490 --> 00:38:51,020
Mig langar að bæta upp allar tölur
á milli 1 og og n, eða 0 og n,

894
00:38:51,020 --> 00:38:52,570
equivalently, til að fá heildar summa.

895
00:38:52,570 --> 00:38:55,100
Svo stóra Sigma tákn
sem þú gætir muna.

896
00:38:55,100 --> 00:38:59,050
Þannig að ég ætla að gera þetta með fyrsta starf
fall kallast Sigma,

897
00:38:59,050 --> 00:39:06,030
liggur það í n, og þá ætla ég að
segja printf, svarið er rétt þar.

898
00:39:06,030 --> 00:39:08,180
>> Svo í stuttu máli, ég fæ og
int frá notandanum.

899
00:39:08,180 --> 00:39:09,280
Ég tryggja að það er jákvætt.

900
00:39:09,280 --> 00:39:12,700
Ég lýsi breytilega heitir svar
tegund int og geyma í henni aftur

901
00:39:12,700 --> 00:39:15,610
verðmæti Sigma, sem liggur í N sem inntak.

902
00:39:15,610 --> 00:39:17,060
Og þá er ég að prenta út það svar.

903
00:39:17,060 --> 00:39:19,550
>> Því miður, jafnvel þó að Sigma hljóð
eins og eitthvað sem gæti verið í

904
00:39:19,550 --> 00:39:24,040
The math.h skrá, yfirlýsing þess,
það er í raun ekki.

905
00:39:24,040 --> 00:39:24,690
Svo er það í lagi.

906
00:39:24,690 --> 00:39:26,170
Ég get framkvæma þetta sjálfur.

907
00:39:26,170 --> 00:39:29,160
Ég ætla að framkvæma aðgerð sem kallast
Sigma, og það er að fara að taka

908
00:39:29,160 --> 00:39:29,900
breytu -

909
00:39:29,900 --> 00:39:32,100
skulum kalla bara það m, bara
svo það er öðruvísi.

910
00:39:32,100 --> 00:39:35,910
Og svo upp hér, ég ætla að segja,
vel, ef m er minna en 1 - þetta er

911
00:39:35,910 --> 00:39:38,180
mjög uninteresting program.

912
00:39:38,180 --> 00:39:41,700
Þannig að ég ætla að fara á undan og
strax aftur 0.

913
00:39:41,700 --> 00:39:45,920
Það bara ekki skynsamleg að bæta upp alla
tölurnar milli 1 og m ef m

914
00:39:45,920 --> 00:39:48,470
er sjálft 0 eða neikvæð.

915
00:39:48,470 --> 00:39:50,900
>> Og þá ætla ég að fara á undan
og gera þetta mjög iteratively.

916
00:39:50,900 --> 00:39:53,090
Ég ætla að gera þessa tegund af gamla skólanum,
og ég ætla að fara á undan

917
00:39:53,090 --> 00:39:57,150
og segja að ég ætla að
lýsa summu til að vera 0.

918
00:39:57,150 --> 00:39:59,630
Þá er ég að fara að hafa
á fyrir lykkja á int -

919
00:39:59,630 --> 00:40:02,820
og láta mig gera það til að passa starfsemi okkar
dreifingu kóða, svo þú hafa a afrit

920
00:40:02,820 --> 00:40:07,500
heima. int i fær 1 á allt að
i er minna en eða jafnt og m.

921
00:40:07,500 --> 00:40:09,430
ég plús plús.

922
00:40:09,430 --> 00:40:11,430
Og þá inni í þessu fyrir lykkju -

923
00:40:11,430 --> 00:40:12,440
við erum næstum þarna -

924
00:40:12,440 --> 00:40:15,810
summan fær summan plús 1.

925
00:40:15,810 --> 00:40:17,670
Og þá er ég að fara að skila summa.

926
00:40:17,670 --> 00:40:19,420
>> Svo ég gerði þetta fljótt,
alveg vísu.

927
00:40:19,420 --> 00:40:22,775
En aftur, helsta hlutverk er nokkuð
einfalt, byggt á númerið við höfum

928
00:40:22,775 --> 00:40:23,190
skrifað svona langt.

929
00:40:23,190 --> 00:40:25,610
Notar tvöfalda lykkju til að fá jákvæð
int frá notandanum.

930
00:40:25,610 --> 00:40:29,870
Ég fara þá að int til nýtt hlutverk
kallað Sigma, að kalla það, aftur, n.

931
00:40:29,870 --> 00:40:33,100
Og ég að geyma aftur gildi, svarið
frá svarta kassanum nú

932
00:40:33,100 --> 00:40:35,460
þekktur sem Sigma, í breytu
kallað svar.

933
00:40:35,460 --> 00:40:36,580
Þá vil ég prenta það.

934
00:40:36,580 --> 00:40:39,090
>> Ef við höldum áfram nú söguna,
hvernig er Sigma framkvæmd?

935
00:40:39,090 --> 00:40:40,840
Ég að leggja til að framkvæma eins og hér segir.

936
00:40:40,840 --> 00:40:43,560
Fyrst, smá villa-stöðva
til að tryggja að notandi er ekki

937
00:40:43,560 --> 00:40:46,480
Messías með mér og farið í
nokkur neikvæð eða 0 virði.

938
00:40:46,480 --> 00:40:49,710
Þá vil ég lýsa yfir breytu sem heitir
summa og setja það í 0.

939
00:40:49,710 --> 00:40:55,910
>> Og nú er ég að byrja að fara frá ég er jafnt
1 alla leið upp að og að meðtöldum m,

940
00:40:55,910 --> 00:41:00,130
vegna þess að ég vil að fela alla
tölur frá eitt til m, innifalið.

941
00:41:00,130 --> 00:41:04,350
Og inni í þetta fyrir lykkju, ég bara
summan fær hvað sem það er nú, auk

942
00:41:04,350 --> 00:41:08,900
Gildi i.

943
00:41:08,900 --> 00:41:10,370
Að viðbættu virði i.

944
00:41:10,370 --> 00:41:14,090
>> Sem innskot, ef þú hefur ekki séð þetta
áður, það er einhver nokkur dæmi um setningarleg sykur

945
00:41:14,090 --> 00:41:14,870
fyrir þessari línu.

946
00:41:14,870 --> 00:41:21,120
Ég get umrita þetta sem plús jafngildir i,
bara til að spara mér nokkrum mínútum

947
00:41:21,120 --> 00:41:22,570
og til að líta svolítið kælir.

948
00:41:22,570 --> 00:41:23,140
En það er allt.

949
00:41:23,140 --> 00:41:24,660
Það er virkni sama.

950
00:41:24,660 --> 00:41:26,710
>> Því miður, þetta númer er
ekki að fara að safna saman enn.

951
00:41:26,710 --> 00:41:31,600
Ef ég hlaupa gera Sigma 0, hvernig am
Ég ætla að fá öskraði á?

952
00:41:31,600 --> 00:41:33,473
Hvað er það að fara að ekki eins?

953
00:41:33,473 --> 00:41:35,740
>> Áhorfendur: [inaudible].

954
00:41:35,740 --> 00:41:37,800
>> DAVID Malan: Já, ég vissi ekki lýsa
virka upp efst, ekki satt?

955
00:41:37,800 --> 00:41:40,590
C er góður af heimskur, þannig að það bara
gerir það sem þú segir að hún geri, og þú

956
00:41:40,590 --> 00:41:41,880
að gera það í þessari röð.

957
00:41:41,880 --> 00:41:45,910
Og svo ef ég högg inn hér ætla ég að
fá viðvörun um Sigma óbeina

958
00:41:45,910 --> 00:41:46,860
yfirlýsingu.

959
00:41:46,860 --> 00:41:48,120
>> Ó, ekki vandamál.

960
00:41:48,120 --> 00:41:50,370
Ég get farið upp á toppinn, og ég get
segja, allt í lagi, bíddu í eina mínútu.

961
00:41:50,370 --> 00:41:54,240
Sigma er fall sem skilar
int og það gerir ráð fyrir að

962
00:41:54,240 --> 00:41:56,620
int sem inntak, semíkommu.

963
00:41:56,620 --> 00:41:59,550
Eða ég gæti sett alla virka
hér að ofan helstu, en almennt, myndi ég

964
00:41:59,550 --> 00:42:02,260
mæli gegn því, vegna þess að það er
gott að hafa ávallt helstu efst svo

965
00:42:02,260 --> 00:42:06,310
þú getur kafa rétt í og ​​vita hvað
program er að gera með því að lesa helstu fyrst.

966
00:42:06,310 --> 00:42:07,930
>> Svo nú láta mig hreinsa skjáinn.

967
00:42:07,930 --> 00:42:09,330
Endurgerð Sigma 0.

968
00:42:09,330 --> 00:42:10,340
Allt virðist kíkja.

969
00:42:10,340 --> 00:42:11,970
Leyfðu mér að hlaupa Sigma 0.

970
00:42:11,970 --> 00:42:12,770
Jákvæð Inter.

971
00:42:12,770 --> 00:42:15,580
Ég skal gefa það fjölda
3. að halda það einfalt.

972
00:42:15,580 --> 00:42:18,710
Svo sem ætti að gefa mér 3
plús 2 plus 1, þannig að 6.

973
00:42:18,710 --> 00:42:20,750
Sláðu og örugglega ég fá 6.

974
00:42:20,750 --> 00:42:21,820
>> Ég get gert eitthvað stærra -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Rétt eins snertir, ætla ég að gera
eitthvað fáránlegt eins og mjög stór

977
00:42:27,690 --> 00:42:30,375
númer, Ó, að raunverulega í uppnámi út -

978
00:42:30,375 --> 00:42:31,600
ha, ég held ekki það er rétt.

979
00:42:31,600 --> 00:42:32,810
Við skulum sjá.

980
00:42:32,810 --> 00:42:34,060
Skulum raunverulega skipta með það.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> Það er vandamál.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
Hvað er að gerast?

985
00:42:44,970 --> 00:42:46,050
The merkjamál er ekki svo slæmt.

986
00:42:46,050 --> 00:42:48,470
Það er samt línuleg.

987
00:42:48,470 --> 00:42:50,810
Whistling er góð áhrif, þó.

988
00:42:50,810 --> 00:42:52,060
Hvað er að gerast?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> Ekki viss um að ef ég heyrði það.

991
00:42:55,620 --> 00:42:57,620
Svo kemur í ljós - og
þetta er eins og til hliðar.

992
00:42:57,620 --> 00:42:59,400
Þetta er ekki algerlega að því
Hugmyndin um endurkvæmni.

993
00:42:59,400 --> 00:43:02,480
Það kemur í ljós, vegna þess að ég er að reyna að
tákna svo stór tala, mest

994
00:43:02,480 --> 00:43:06,980
líklega það er verið að mistúlka
af C sem ekki jákvæð tala,

995
00:43:06,980 --> 00:43:09,980
en neikvæð tala.

996
00:43:09,980 --> 00:43:12,690
>> Við höfum ekki talað um þetta, en það
reynist það eru neikvæðar tölur

997
00:43:12,690 --> 00:43:14,210
í heiminum í viðbót
að jákvæðar tölur.

998
00:43:14,210 --> 00:43:16,290
Og leið sem þú getur
tákna neikvæð tala

999
00:43:16,290 --> 00:43:19,530
raun er, þú nota einn
sérstaka hluti til að sýna

1000
00:43:19,530 --> 00:43:20,400
jákvæð yfir neikvæð.

1001
00:43:20,400 --> 00:43:22,950
Það er lítið flóknara en það,
en það er grundvallar hugmynd.

1002
00:43:22,950 --> 00:43:26,740
>> Svo því miður, ef C er ruglingslegt einn
af þeim bitum sem í raun þýðir,

1003
00:43:26,740 --> 00:43:30,790
ó, þetta er neikvæð tala, lykkja mitt
hér, til dæmis, er í raun aldrei

1004
00:43:30,790 --> 00:43:31,740
fara að segja.

1005
00:43:31,740 --> 00:43:33,850
Þannig að ef ég væri í raun prentun eitthvað
aftur og aftur, myndum við

1006
00:43:33,850 --> 00:43:34,650
sjá í heild einhver fjöldi.

1007
00:43:34,650 --> 00:43:36,220
En aftur, þetta er að auki the benda.

1008
00:43:36,220 --> 00:43:38,590
Þetta er í raun bara eins konar
vitsmunalegum forvitni sem við munum koma

1009
00:43:38,590 --> 00:43:39,550
aftur að lokum.

1010
00:43:39,550 --> 00:43:43,400
En nú, þetta er rétt
framkvæmd ef við gerum ráð fyrir að

1011
00:43:43,400 --> 00:43:45,970
notandi mun veita ints
að passa innan ints.

1012
00:43:45,970 --> 00:43:49,370
>> En ég halda því fram að þetta númer, hreinskilnislega,
mætti ​​gera svo miklu meira einfaldlega.

1013
00:43:49,370 --> 00:43:54,060
Ef markmiðið hendi er að taka númer
eins m og bæta upp allt í

1014
00:43:54,060 --> 00:43:59,510
tölur á henni og 1, eða öfugt
á milli 1 og það, kröfu I

1015
00:43:59,510 --> 00:44:03,380
sem ég get fengið lánað þessa hugmynd að sameina
raða átti, sem var að taka vandamál

1016
00:44:03,380 --> 00:44:05,660
af þessari stærð og deila honum
í eitthvað minni.

1017
00:44:05,660 --> 00:44:09,875
Kannski ekki helminginn, en minni en
representatively sama.

1018
00:44:09,875 --> 00:44:12,130
Sama hugmynd, en minni vandamál.

1019
00:44:12,130 --> 00:44:15,470
>> Þannig að ég er í raun - Leyfðu mér að spara þessa skrá
með aðra útgáfu númer.

1020
00:44:15,470 --> 00:44:17,670
Við munum kalla þetta útgáfu
1 stað þess að 0.

1021
00:44:17,670 --> 00:44:20,790
Og ég halda því fram að ég get í raun
reimplement þetta í þessari tegund af

1022
00:44:20,790 --> 00:44:22,160
hugur-beygja hátt.

1023
00:44:22,160 --> 00:44:23,710
>> Ég ætla að láta hluta af því einn.

1024
00:44:23,710 --> 00:44:27,710
Ég ætla að segja ef m er minna
en eða jafnvel jafnt og 0 -

1025
00:44:27,710 --> 00:44:29,280
Ég ætla bara að fara að vera svolítið
meira anal að þessu sinni

1026
00:44:29,280 --> 00:44:30,520
með stöðva villa mína -

1027
00:44:30,520 --> 00:44:33,190
Ég ætla að fara á undan og aftur 0.

1028
00:44:33,190 --> 00:44:34,490
Þetta er handahófskennt.

1029
00:44:34,490 --> 00:44:37,500
Ég er bara einfaldlega að ákveða hvort notandi
gefur mér neikvæð tala, ég

1030
00:44:37,500 --> 00:44:41,490
aftur 0, og þeir ættu að hafa lesið
skjölin nánar.

1031
00:44:41,490 --> 00:44:42,170
>> Annað -

1032
00:44:42,170 --> 00:44:44,070
taka eftir hvað ég ætla að gera.

1033
00:44:44,070 --> 00:44:49,260
Annars er ég að fara að skila m plús -

1034
00:44:49,260 --> 00:44:51,010
hvað er sigma m?

1035
00:44:51,010 --> 00:44:56,710
Jæja, sigma m plús m mínus 1,
plús m mínus 2, plús m mínus 3.

1036
00:44:56,710 --> 00:44:58,030
Ég vil ekki að skrifa öll þessi út.

1037
00:44:58,030 --> 00:44:59,120
Af hverju ekki ég bara Punt?

1038
00:44:59,120 --> 00:45:05,080
Endurkvæmur kalla mig með örlítið
minni vandamál, semíkommu,

1039
00:45:05,080 --> 00:45:06,840
og kalla það einn dag?

1040
00:45:06,840 --> 00:45:07,040
>> Ekki satt?

1041
00:45:07,040 --> 00:45:10,980
Nú hér líka, gætir þú fundið eða hafa áhyggjur
að þetta er óendanlega lykkju sem ég er

1042
00:45:10,980 --> 00:45:15,450
Örvandi, þar sem ég er að innleiða
Sigma með því að kalla Sigma.

1043
00:45:15,450 --> 00:45:20,342
En það er fullkomlega í lagi, vegna þess að ég
hélt undan bætt hvaða línur?

1044
00:45:20,342 --> 00:45:22,600
>> Áhorfendur: [inaudible].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID Malan: 23-26, sem
er ef ástand mitt.

1046
00:45:25,430 --> 00:45:28,390
Vegna þess að það er gott um
Frádráttur hér, því ég halda

1047
00:45:28,390 --> 00:45:31,180
fötlun sigma minni vandamál, minni
vandamál, minni - það er ekki

1048
00:45:31,180 --> 00:45:31,870
helmingur the stærð.

1049
00:45:31,870 --> 00:45:34,380
Það er bara barn skref minni,
en það er allt í lagi.

1050
00:45:34,380 --> 00:45:38,050
Vegna lokum munum við vinna
leið okkar niður í 1 eða 0.

1051
00:45:38,050 --> 00:45:41,630
Og þegar við högg 0, Sigma er ekki
fara að kalla sig lengur.

1052
00:45:41,630 --> 00:45:43,590
Það er að fara strax aftur á 0.

1053
00:45:43,590 --> 00:45:47,960
>> Svo áhrif, ef þú konar vindur þetta
upp í huga þinn, er að bæta m plús

1054
00:45:47,960 --> 00:45:52,740
m mínus 1, auk m mínus 2, plús m mínus
3, auk punktur, punktur, punktur, m mínus

1055
00:45:52,740 --> 00:45:57,820
m, að lokum að gefa þér 0, og
áhrif er að lokum að bæta öllum

1056
00:45:57,820 --> 00:45:59,070
þetta saman.

1057
00:45:59,070 --> 00:46:02,380
Þannig að við höfum ekki, með endurkvæmni,
leysa vandamál sem við

1058
00:46:02,380 --> 00:46:03,470
gat ekki leyst áður.

1059
00:46:03,470 --> 00:46:06,840
Reyndar útgáfa 0 af þessu, og hvert
vandamál hingað til, hefur verið leysanlegt

1060
00:46:06,840 --> 00:46:09,980
með bara að nota fyrir lykkjur eða á meðan
lykkjur eða svipuð býr.

1061
00:46:09,980 --> 00:46:13,150
>> En endurkvæmni, eflaust ég, gefur okkur
aðra leið til að hugsa um

1062
00:46:13,150 --> 00:46:17,010
vandamál, þar ef við getum tekið
vandamál, skipta því frá eitthvað

1063
00:46:17,010 --> 00:46:22,340
nokkuð stór í eitthvað nokkuð
minni, halda ég að við getum leyst það

1064
00:46:22,340 --> 00:46:26,040
kannski svolítið meira glæsilegur í skilmálar
af hönnun, með minna númeri,

1065
00:46:26,040 --> 00:46:30,980
og kannski jafnvel leysa vandamál sem myndi
vera erfiðara, eins og við munum að lokum

1066
00:46:30,980 --> 00:46:33,280
sjá, leysa eingöngu iteratively.

1067
00:46:33,280 --> 00:46:35,980
>> En cliffhanger sem ég gerði
langar að yfirgefa okkur á var þetta.

1068
00:46:35,980 --> 00:46:40,720
Leyfðu mér að fara á undan og opna
upp skrá úr -

1069
00:46:40,720 --> 00:46:44,300
reyndar, láta mig fara og
gera þetta alvöru hratt.

1070
00:46:44,300 --> 00:46:46,875
Leyfðu mér að fara á undan og leggja
eftirfarandi.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Meðal kóða dag er þetta skrá hér.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Þessi maður hér, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Þannig að þetta er heimskur lítill forrit sem
Ég þeyttum upp þessi krafa til gera

1076
00:47:06,260 --> 00:47:06,940
eftirfarandi.

1077
00:47:06,940 --> 00:47:10,140
Í helstu, lýsir það fyrst að
int heitir x og gefur það

1078
00:47:10,140 --> 00:47:11,100
verðmæti 1.

1079
00:47:11,100 --> 00:47:13,520
Þá segir það að int y og
gefur það gildi 2.

1080
00:47:13,520 --> 00:47:15,310
Þá prentar það út hvað x og y er.

1081
00:47:15,310 --> 00:47:17,781
Þá segir það, skipta, punktur punktur punktur.

1082
00:47:17,781 --> 00:47:21,670
>> Þá segist hann vera að hringja aðgerð
kallað skipti, sem liggur í x og

1083
00:47:21,670 --> 00:47:24,290
Y, þá hugmynd sem er að vonandi
x og y mun koma aftur

1084
00:47:24,290 --> 00:47:25,620
öðruvísi, hið gagnstæða.

1085
00:47:25,620 --> 00:47:27,110
Þá kröfu skipti!

1086
00:47:27,110 --> 00:47:28,420
með upphrópunarmerki.

1087
00:47:28,420 --> 00:47:30,190
Þá prentar það út x og y.

1088
00:47:30,190 --> 00:47:33,480
>> En það kemur í ljós að þetta er mjög
einföld sýning niður

1089
00:47:33,480 --> 00:47:35,570
hér er í raun þrjótur.

1090
00:47:35,570 --> 00:47:38,870
Jafnvel þó að ég er að lýsa yfir tímabundið
breyta og tímabundið setja í

1091
00:47:38,870 --> 00:47:42,010
það, þá er ég reassigning
að þá er gildið b -

1092
00:47:42,010 --> 00:47:45,080
sem finnst sanngjarnt, vegna þess að ég hef
vistuð afrit af í afleysingamanneskja.

1093
00:47:45,080 --> 00:47:48,410
Þá er ég að uppfæra b á jafn
hvað var í afleysingamanneskja.

1094
00:47:48,410 --> 00:47:51,610
Þessi tegund af leikur skel flytja
í b-og b-inn að því að nota þetta

1095
00:47:51,610 --> 00:47:54,360
miðju-maður heitir afleysingamanneskja finnst
fullkomlega sanngjarn.

1096
00:47:54,360 --> 00:47:57,270
>> En ég halda því fram að þegar ég keyra þetta
kóða, eins og ég geri núna -

1097
00:47:57,270 --> 00:47:59,490
láta mig fara á undan og límdu hana í hér.

1098
00:47:59,490 --> 00:48:01,995
Ég kalla þetta noswap.c.

1099
00:48:01,995 --> 00:48:05,630
Og eins og nafnið gefur til kynna, þetta er ekki
að fara að vera rétt program.

1100
00:48:05,630 --> 00:48:09,460
Gerðu noswap. / Engin skipti.

1101
00:48:09,460 --> 00:48:12,110
x er 1, y er 2, skipta um, skipti.

1102
00:48:12,110 --> 00:48:14,220
x er 1, y er 2..

1103
00:48:14,220 --> 00:48:16,920
Þetta er í grundvallaratriðum rangt, jafnvel
þótt þetta virðist fullkomlega

1104
00:48:16,920 --> 00:48:17,730
sanngjarnt að mér.

1105
00:48:17,730 --> 00:48:21,330
Og það er ástæða, en við erum ekki
fara að koma í ljós ástæðu bara ennþá.

1106
00:48:21,330 --> 00:48:24,610
>> Fyrir nú seinni cliffhanger ég vildi
að yfirgefa þig með er þetta, sem

1107
00:48:24,610 --> 00:48:27,120
tilkynning af tegund á afsláttarmiða þau.

1108
00:48:27,120 --> 00:48:31,590
Nýsköpun okkar með seint daga á þessu ári
hefur valdið a non-léttvæg númer

1109
00:48:31,590 --> 00:48:33,830
spurningum, sem var
ekki ætlun okkar.

1110
00:48:33,830 --> 00:48:36,590
Ætlunin þessara afsláttarmiða númerin,
þar ef þú hluti af vandamálinu

1111
00:48:36,590 --> 00:48:39,850
setja snemma, þannig að fá auka dag,
var virkilega til að hjálpa ykkur að hjálpa

1112
00:48:39,850 --> 00:48:42,420
sjálfur byrja snemma, flokka
af því incentivizing þig.

1113
00:48:42,420 --> 00:48:44,880
Hjálpar okkur að dreifa álaginu yfir
skrifstofa klst betur þannig að

1114
00:48:44,880 --> 00:48:45,740
það er tegund af vinna-vinna.

1115
00:48:45,740 --> 00:48:48,860
>> Því miður, held ég leiðbeiningar mínum
hafa ekki verið, hingað til, mjög skýr, svo

1116
00:48:48,860 --> 00:48:52,230
Ég fór aftur um helgina og uppfærð
The sérstakur í stærri, bolder texta

1117
00:48:52,230 --> 00:48:53,600
útskýra skotum eins og þessir.

1118
00:48:53,600 --> 00:48:56,900
Og bara til að segja það meira opinberlega, með
vanræksla, vandamál setur eru vegna Fimmtudagur

1119
00:48:56,900 --> 00:48:58,400
á hádegi, og á kennsluáætlun.

1120
00:48:58,400 --> 00:49:02,030
Ef þú byrjar snemma, klára hluta af
vandamálið sett með miðvikudag klukkan 12:00

1121
00:49:02,030 --> 00:49:05,170
PM, sá hluti sem snýr að afsláttarmiða
kóða, hugmyndin er að þú geta lengja

1122
00:49:05,170 --> 00:49:07,710
Frestur fyrir the
P sett til föstudagsins.

1123
00:49:07,710 --> 00:49:10,890
Það er, hluti af örlítið hluti af P
sett miðað við það sem venjulega er

1124
00:49:10,890 --> 00:49:13,200
stærri vandamál, og þú kaupir
sjálfur auka dag.

1125
00:49:13,200 --> 00:49:15,190
Aftur fær það þig til að hugsa um
vandamálið sett, fær þig til

1126
00:49:15,190 --> 00:49:16,380
skrifstofa klst fyrr.

1127
00:49:16,380 --> 00:49:20,670
En númer afsláttarmiða vandamálið er enn
krafist, jafnvel ef þú ekki senda það.

1128
00:49:20,670 --> 00:49:23,340
>> En meira compellingly er þetta.

1129
00:49:23,340 --> 00:49:26,520
(STAGE hvísl) Og þessir gott fólk að fara
snemma eru ađ sjá eftir því.

1130
00:49:26,520 --> 00:49:28,620
Eins eru gott fólk á svölunum.

1131
00:49:28,620 --> 00:49:32,510
Ég afsökunar fyrirfram að fólkinu á
svalir ástæðum sem verður

1132
00:49:32,510 --> 00:49:33,920
hreinsa í aðeins augnablik.

1133
00:49:33,920 --> 00:49:37,050
>> Þannig að við erum lánsöm að hafa einn af
Fyrrum CS50 er höfuð kennslu félagar á

1134
00:49:37,050 --> 00:49:39,302
fyrirtæki sem heitir dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
Þeir hafa mjög ríkulega gefið sem
afsláttarmiða kóða hér fyrir þennan mikið pláss,

1136
00:49:45,500 --> 00:49:48,180
sem er upp úr
venjulega 2 gígabæta.

1137
00:49:48,180 --> 00:49:51,740
Svo það sem ég hélt að við myndum gera á þessu
Lokastaða í huga er að gera a hluti af a uppljóstrun,

1138
00:49:51,740 --> 00:49:55,380
þannig að í aðeins augnablik, munum við sýna
sigurvegari og hver hefur afsláttarmiða

1139
00:49:55,380 --> 00:49:57,980
númer sem þú getur þá farið til þeirra
website, slá það í, og voila, fá

1140
00:49:57,980 --> 00:50:01,370
allt miklu meira Dropbox pláss fyrir þinn
tæki og persónulegum skrám.

1141
00:50:01,370 --> 00:50:05,690
>> Og fyrst, sem langar til að taka þátt
í þessa teikningu?

1142
00:50:05,690 --> 00:50:09,630
OK, nú gerir það enn meira gaman.

1143
00:50:09,630 --> 00:50:14,010
Sá sem fær þessa 25-gígabæti
afsláttarmiða kóða - sem er langt

1144
00:50:14,010 --> 00:50:16,150
meira sannfærandi en seint
dagar nú, kannski -

1145
00:50:16,150 --> 00:50:20,620
er sá sem situr ofan á
sæti draga undir sem er

1146
00:50:20,620 --> 00:50:21,620
að afsláttarmiða númer.

1147
00:50:21,620 --> 00:50:23,480
Þú getur nú að líta undir
sæti draga þinn.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [Vídeó spilun]

1150
00:50:29,680 --> 00:50:31,620
>> -Einn, tveir, þrír.

1151
00:50:31,620 --> 00:50:35,015
>> [Öskrandi]

1152
00:50:35,015 --> 00:50:35,985
>> -Þú færð bíl!

1153
00:50:35,985 --> 00:50:36,670
Þú færð bíl!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID Malan: Við munum sjá
þér á miðvikudag.

1155
00:50:37,970 --> 00:50:38,904
>> -Þú færð bíl!

1156
00:50:38,904 --> 00:50:39,371
Þú færð bíl!

1157
00:50:39,371 --> 00:50:40,305
Þú færð bíl!

1158
00:50:40,305 --> 00:50:41,706
Þú færð bíl!

1159
00:50:41,706 --> 00:50:43,107
Þú færð bíl!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID Malan: Svalir fólkinu, koma
niður hér að framan,

1161
00:50:45,530 --> 00:50:46,866
þar sem við höfum aukahlutir.

1162
00:50:46,866 --> 00:50:50,282
>> -Allir fær bíl!

1163
00:50:50,282 --> 00:50:52,234
Hjá öllum bíl!

1164
00:50:52,234 --> 00:50:52,722
>> [END vídeó spilun]

1165
00:50:52,722 --> 00:50:54,590
>> Sögumaður: Á næsta CS50 -

1166
00:50:54,590 --> 00:51:00,374
>> Ræðumaður 5: Oh my gosh gosh gosh gosh
gosh gosh gosh gosh gosh gosh -

1167
00:51:00,374 --> 00:51:02,106
>> [UKELELE Leikrit]