1
00:00:00,000 --> 00:00:11,904
>> [TÓNLIST spila]

2
00:00:11,904 --> 00:00:12,910
>> Prófessor: Allt í lagi.

3
00:00:12,910 --> 00:00:16,730
Þetta er CS50 og þetta er
í lok viku þrjú.

4
00:00:16,730 --> 00:00:20,230
Þannig að við erum hér í dag, ekki í Sanders
Theater stað í Weldner Library.

5
00:00:20,230 --> 00:00:23,170
Inni sem er stúdíó
þekktur sem Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
eða eigum við að segja Studio H, eða eigum vér
við say-- ef þú njóta að brandari,

7
00:00:28,310 --> 00:00:30,540
það er í raun frá
bekkjarfélaga, Mark, á netinu,

8
00:00:30,540 --> 00:00:32,420
sem lagði eins mikið í gegnum Twitter.

9
00:00:32,420 --> 00:00:34,270
Nú er það kaldur um
að vera hér í stúdíó

10
00:00:34,270 --> 00:00:38,410
er að ég er umkringdur þessum græna
veggir, grænt skjár eða chromakey,

11
00:00:38,410 --> 00:00:43,290
svo að segja, sem þýðir að CS50 er
framleiðslu lið, unbeknownst til mín

12
00:00:43,290 --> 00:00:47,380
núna, gæti verið að setja
mig mest hvar sem er í heiminum,

13
00:00:47,380 --> 00:00:48,660
fyrir betri eða verri.

14
00:00:48,660 --> 00:00:51,800
>> Nú liggur það á undan, vandamál setja
tvö er í höndum þínum fyrir þessa viku,

15
00:00:51,800 --> 00:00:53,830
en með Heimadæmi
þrír þetta næstu viku,

16
00:00:53,830 --> 00:00:56,600
þú verður að vera áskorun með
svokallaða leikur af 15,

17
00:00:56,600 --> 00:00:58,960
gamall aðila hag að
þú might muna að fá

18
00:00:58,960 --> 00:01:02,030
sem barn sem hefur a heild búnt
af tölum sem getur renna upp, niður,

19
00:01:02,030 --> 00:01:05,790
vinstri og hægri, og það er eitt bil
innan ráðgáta, í sem þú

20
00:01:05,790 --> 00:01:07,840
geta í raun renna þessir ráðgáta stykki.

21
00:01:07,840 --> 00:01:11,150
Einhvern sem þú færð þetta
þraut í sumum hálf handahófi,

22
00:01:11,150 --> 00:01:12,940
og markmiðið er að
raða það, toppur til botn,

23
00:01:12,940 --> 00:01:16,310
vinstri til hægri, frá einu
alla leið upp í gegnum 15.

24
00:01:16,310 --> 00:01:19,360
>> Því miður, framkvæmd
þú munt hafa á hendi

25
00:01:19,360 --> 00:01:21,590
er að fara að vera hugbúnaður
byggt, ekki líkamlega.

26
00:01:21,590 --> 00:01:25,280
Þú ert í raun að fara að þurfa að skrifa
númer sem nemandi eða notandi getur

27
00:01:25,280 --> 00:01:26,760
spila leikinn 15.

28
00:01:26,760 --> 00:01:29,030
Og í raun, í spjallþráð
útgáfa af leiknum af 15,

29
00:01:29,030 --> 00:01:32,155
þú munt vera erfitt að hrinda í framkvæmd,
ekki bara að leika þetta gamla skólanum

30
00:01:32,155 --> 00:01:35,010
leikur, heldur leysa
af því, að innleiða guð ham,

31
00:01:35,010 --> 00:01:38,280
svo að segja, sem í raun
leysa þraut fyrir mönnum,

32
00:01:38,280 --> 00:01:41,080
því að veita þeim vott,
eftir vott, eftir vísbending.

33
00:01:41,080 --> 00:01:42,280
Svo meira á því í næstu viku.

34
00:01:42,280 --> 00:01:43,720
En það er það sem er framundan.

35
00:01:43,720 --> 00:01:47,610
>> Fyrir nú muna að fyrr í þessari viku
við höfðum þetta cliffhanger, ef þú vilt,

36
00:01:47,610 --> 00:01:52,560
þar sá besti sem við vorum að gera flokkun
vitur var efri mörk stór eða n

37
00:01:52,560 --> 00:01:53,210
veldi.

38
00:01:53,210 --> 00:01:56,520
Með öðrum orðum, kúla raða,
Val tegund, innsetning flokka,

39
00:01:56,520 --> 00:01:59,120
öllum þeim, en mismunandi
í framkvæmd þeirra,

40
00:01:59,120 --> 00:02:03,480
dreifstýringu inn í n veldi gangi
tími í mjög versta tilfelli.

41
00:02:03,480 --> 00:02:06,010
Og gerum við ráð almennt að
mjög versta tilfelli fyrir flokkun

42
00:02:06,010 --> 00:02:08,814
er eitt sem inntak þitt
eru alveg aftur á bak.

43
00:02:08,814 --> 00:02:11,980
Og reyndar, það tók alveg nokkur skref
að framkvæma hvert þessara reiknirit.

44
00:02:11,980 --> 00:02:15,110
>> Nú á mjög lok bekknum
muna, samanborið við kúla konar

45
00:02:15,110 --> 00:02:19,390
gegn Val tagi gegn einum öðrum
sem við kölluðum mergesort á þeim tíma,

46
00:02:19,390 --> 00:02:22,120
og ég leggja til að það tekur
Kosturinn við lexíu frá viku

47
00:02:22,120 --> 00:02:24,060
núll, skipta og sigra.

48
00:02:24,060 --> 00:02:28,810
Og einhvern veginn ná einhvers konar
lógaritmískum hlaupandi tími lokum,

49
00:02:28,810 --> 00:02:31,024
í stað þess að eitthvað
það er eingöngu stigs.

50
00:02:31,024 --> 00:02:33,440
Og það er ekki alveg lógaritmískum,
það er dálítið meira en það.

51
00:02:33,440 --> 00:02:36,520
En ef þú manst frá bekknum,
það var miklu, miklu hraðar.

52
00:02:36,520 --> 00:02:38,210
Við skulum taka a líta á þar sem við var horfið.

53
00:02:38,210 --> 00:02:41,880

54
00:02:41,880 --> 00:02:45,370
>> Bubble konar móti vali
konar móti sameiningu tagi.

55
00:02:45,370 --> 00:02:47,700
Nú þeir eru allir hlaupandi í
kenning, á sama tíma.

56
00:02:47,700 --> 00:02:50,510
The CPU er í gangi á sama hraða.

57
00:02:50,510 --> 00:02:54,990
En þú getur fundið hvernig leiðinlegur þetta
er mjög fljótt að fara að verða,

58
00:02:54,990 --> 00:02:58,790
og hversu hratt, þegar við sprauta
smá viku núll er reiknirit,

59
00:02:58,790 --> 00:03:00,080
getum við að hraða hlutum upp.

60
00:03:00,080 --> 00:03:01,630
>> Svo árangur konar lítur ótrúlega.

61
00:03:01,630 --> 00:03:05,220
Hvernig getum við nýta það til þess
að raða tölur hraðar.

62
00:03:05,220 --> 00:03:07,140
Jæja við skulum hugsa til baka
að efnið sem við

63
00:03:07,140 --> 00:03:10,380
hafði aftur í viku núll, að af
leita að einhverjum í símaskránni,

64
00:03:10,380 --> 00:03:12,380
og muna að
sauðakóðanum sem við lagt,

65
00:03:12,380 --> 00:03:14,560
um sem við getum fundið
einhver eins og Mike Smith,

66
00:03:14,560 --> 00:03:16,310
horfði smá eitthvað eins og this.

67
00:03:16,310 --> 00:03:20,820
>> Nú taka a líta einkum
á línu 7 og 8, og 10 og 11,

68
00:03:20,820 --> 00:03:25,240
sem örva þessi lykkja, þar sem við haldið
fara aftur til línu 3 aftur og aftur,

69
00:03:25,240 --> 00:03:26,520
og aftur.

70
00:03:26,520 --> 00:03:31,790
En það kemur í ljós að við getum skoðað
Þetta reiknirit, hér í sauðakóða,

71
00:03:31,790 --> 00:03:33,620
aðeins meira heildrænt.

72
00:03:33,620 --> 00:03:35,960
Í raun, hvað ég er að leita
á hér á skjánum,

73
00:03:35,960 --> 00:03:41,180
er reiknirit til að leita að
Mike Smith meðal sumir setja af síðum.

74
00:03:41,180 --> 00:03:45,520
Og reyndar, gætum við einfalda þetta
reiknirit í þeim línum 7 og 8,

75
00:03:45,520 --> 00:03:49,860
og 10 og 11 til að bara segja þetta,
sem ég hef kynnt hér í gulum.

76
00:03:49,860 --> 00:03:52,210
Með öðrum orðum, ef Mike
Smith er fyrr í bókinni,

77
00:03:52,210 --> 00:03:55,004
við þurfum ekki að tilgreina skref
skref nú hvernig á að fara að finna hann.

78
00:03:55,004 --> 00:03:56,920
Við þurfum ekki að tilgreina
til að fara aftur til línu 3,

79
00:03:56,920 --> 00:03:58,960
hvers vegna er það ekki bara í staðinn,
segja, almennt,

80
00:03:58,960 --> 00:04:01,500
leita Mike í
vinstri hluta bókarinnar.

81
00:04:01,500 --> 00:04:03,960
>> Hins vegar ef Mike er
reyndar seinna í bókinni,

82
00:04:03,960 --> 00:04:07,540
Hvers vegna eigum við ekki að vitna bara unquote leit
fyrir Mike í hægri hluta bókarinnar.

83
00:04:07,540 --> 00:04:11,030
Með öðrum orðum, hvers vegna er það ekki bara
konar punt að okkur að segja,

84
00:04:11,030 --> 00:04:13,130
leita Mike í þessu
hlutmengi af bókinni,

85
00:04:13,130 --> 00:04:16,279
og fara með hana til núverandi okkar
reiknirit til að segja okkur

86
00:04:16,279 --> 00:04:18,750
hvernig á að leita að Mike í
að vinstri hluta bókarinnar.

87
00:04:18,750 --> 00:04:20,750
Með öðrum orðum, okkar
reiknirit virkar hvort sem það er

88
00:04:20,750 --> 00:04:24,670
a símaskrá þessa þykkt, þetta
þykkt, eða þykkt af neinu tagi.

89
00:04:24,670 --> 00:04:27,826
Þannig að við getum endurkvæmt
skilgreina þetta reiknirit.

90
00:04:27,826 --> 00:04:29,950
Með öðrum orðum, á
skjár hér er reiknirit

91
00:04:29,950 --> 00:04:33,130
til að leita að Mike Smith
meðal síðum símaskránni.

92
00:04:33,130 --> 00:04:37,410
Svo í línu 7 og 10, við skulum
bara segja einmitt það.

93
00:04:37,410 --> 00:04:40,250
Og ég nota þetta hugtak í smá stund
síðan, og reyndar, endurkvæmni

94
00:04:40,250 --> 00:04:42,450
er tískuorð nú,
og það er þetta ferli

95
00:04:42,450 --> 00:04:47,210
um að gera eitthvað cyclical með einhvern veginn
með kóða sem þú hefur nú þegar,

96
00:04:47,210 --> 00:04:49,722
og kalla það aftur,
og aftur, og aftur.

97
00:04:49,722 --> 00:04:51,930
Nú það er að fara að vera mikilvægur
sem við botn einhvern veginn

98
00:04:51,930 --> 00:04:53,821
út, og gera það ekki óendanlega lengi.

99
00:04:53,821 --> 00:04:56,070
Annars erum við að fara að
hafa örugglega óendanlega lykkju.

100
00:04:56,070 --> 00:04:59,810
En við skulum sjá hvort við getum fengið lánað þessa hugmynd
af endurkvæmni, gera eitthvað aftur

101
00:04:59,810 --> 00:05:03,600
og aftur og aftur, til að leysa
flokkunarröðina vandamál með sameinast

102
00:05:03,600 --> 00:05:05,900
raða, allt skilvirkari.

103
00:05:05,900 --> 00:05:06,970
>> Þannig að ég gef þér Mergesort.

104
00:05:06,970 --> 00:05:07,920
Við skulum taka a líta.

105
00:05:07,920 --> 00:05:10,850
Svo er hér sauðakóðanum með
sem við gætum framkvæma flokkun,

106
00:05:10,850 --> 00:05:12,640
nota þessa reiknirit sem kallast Mergesort.

107
00:05:12,640 --> 00:05:13,880
Og það er einfaldlega þetta.

108
00:05:13,880 --> 00:05:15,940
Á inntak n þætti,
í öðrum orðum, ef þú ert

109
00:05:15,940 --> 00:05:18,830
gefið n þætti og númer og
bréf eða hvað inntak er,

110
00:05:18,830 --> 00:05:22,430
ef þú ert að gefa n þætti, ef
n er minna en 2, bara aftur.

111
00:05:22,430 --> 00:05:22,930
Ekki satt?

112
00:05:22,930 --> 00:05:26,430
Vegna þess að ef n er minna en 2 og þá
þýðir að minn listi af þáttum

113
00:05:26,430 --> 00:05:30,446
er annað hvort af stærð 0 eða 1, og
í báðum þessum léttvæg tilvikum,

114
00:05:30,446 --> 00:05:31,570
listinn er þegar raðað.

115
00:05:31,570 --> 00:05:32,810
Ef það er enginn listi, það er flokkað.

116
00:05:32,810 --> 00:05:35,185
Og ef það er listi af lengd
1, það er augljóslega flokkað.

117
00:05:35,185 --> 00:05:38,280
Svo reiknirit þarf aðeins að
raunverulega gera eitthvað áhugavert,

118
00:05:38,280 --> 00:05:40,870
ef við höfum tvö eða fleiri
þættir gefið okkur.

119
00:05:40,870 --> 00:05:42,440
Svo skulum líta á galdra þá.

120
00:05:42,440 --> 00:05:47,500
Else raða vinstri helming þætti,
þá raða rétt helminginn af þáttum,

121
00:05:47,500 --> 00:05:49,640
síðan sameinað flokkuð helminga.

122
00:05:49,640 --> 00:05:52,440
Og hvað er góður af huga beygja
hér, er að ég í raun ekki

123
00:05:52,440 --> 00:05:56,190
virðast hafa sagt þér
eitthvað strax, ekki satt?

124
00:05:56,190 --> 00:05:59,560
Allt sem ég hef sagt er, fá lista yfir
n þættir, raða vinstri helming,

125
00:05:59,560 --> 00:06:01,800
þá hægri helminginn, þá
sameina flokkuð helminga,

126
00:06:01,800 --> 00:06:03,840
en þar er í raun leyndarmál sósu?

127
00:06:03,840 --> 00:06:05,260
Hvar er reiknirit?

128
00:06:05,260 --> 00:06:09,150
Jæja það kemur í ljós að þeim tveimur línum
fyrst raða vinstri helmingi þætti,

129
00:06:09,150 --> 00:06:13,970
og svoleiðis hægri helminginn af þáttum,
eru endurkvæma símtöl, svo að segja.

130
00:06:13,970 --> 00:06:16,120
>> Eftir allt saman, í þetta
tímapunktur, ég hef

131
00:06:16,120 --> 00:06:18,950
reiknirit sem til
raða a heild búnt af þætti?

132
00:06:18,950 --> 00:06:19,450
Já.

133
00:06:19,450 --> 00:06:20,620
Það er hérna.

134
00:06:20,620 --> 00:06:25,180
Það er hérna á skjánum, og
svo ég geti notað það sama mengi skrefum

135
00:06:25,180 --> 00:06:28,500
að raða vinstri helming,
og ég get hægri helminginn.

136
00:06:28,500 --> 00:06:30,420
Og reyndar, aftur, og aftur.

137
00:06:30,420 --> 00:06:34,210
Svo einhvern veginn eða annan, og við munum fljótlega
sjá þetta, töfra mergesort

138
00:06:34,210 --> 00:06:37,967
er fellt í að mjög endanleg
lína, sameina flokkuð helminga.

139
00:06:37,967 --> 00:06:39,300
Og það virðist nokkuð innsæi.

140
00:06:39,300 --> 00:06:41,050
Þú tekur tvo helminga, og þér,
einhvern veginn, sameina þær saman,

141
00:06:41,050 --> 00:06:43,260
og við munum sjá þetta
concretely í smá stund.

142
00:06:43,260 --> 00:06:45,080
>> En þetta er heill reiknirit.

143
00:06:45,080 --> 00:06:46,640
Og við skulum sjá nákvæmlega hvers vegna.

144
00:06:46,640 --> 00:06:50,912
Jæja ætla að við erum gefið þetta sama
átta þættir hér á skjáinn einn

145
00:06:50,912 --> 00:06:53,120
til átta, en þeir eru
í því er virðist af handahófi.

146
00:06:53,120 --> 00:06:55,320
Og markmiðið sem fyrir hendi er
að raða þessum þætti.

147
00:06:55,320 --> 00:06:58,280
Jæja hvernig get ég farið um
gera það með, aftur,

148
00:06:58,280 --> 00:07:00,407
Mergesort, eins og á þessari sauðakóðanum?

149
00:07:00,407 --> 00:07:02,740
Og aftur, ingrain þetta í
hugur þinn, fyrir aðeins augnablik.

150
00:07:02,740 --> 00:07:05,270
Fyrsta tilfelli er nokkuð
léttvæg, ef það er minna en 2,

151
00:07:05,270 --> 00:07:07,060
bara aftur, það er engin vinna að vera.

152
00:07:07,060 --> 00:07:09,290
Svo í raun er það bara þrír
skref til að virkilega halda í huga.

153
00:07:09,290 --> 00:07:11,081
Aftur, og aftur, ég er
fara til að vilja hafa

154
00:07:11,081 --> 00:07:13,980
að raða vinstri helming,
raða rétt helminginn,

155
00:07:13,980 --> 00:07:15,890
og síðan einu sinni þeirra
tvennt eru flokkuð,

156
00:07:15,890 --> 00:07:18,710
Ég vil sameina þá saman
í eitt raðaða listanum.

157
00:07:18,710 --> 00:07:19,940
Svo halda að í huga.

158
00:07:19,940 --> 00:07:21,310
>> Svo hér er upprunalega lista.

159
00:07:21,310 --> 00:07:23,510
Skulum meðhöndla þetta sem
array, eins og við byrjuðum að

160
00:07:23,510 --> 00:07:25,800
í viku tvö, sem er
Samhangandi blokk af minni.

161
00:07:25,800 --> 00:07:28,480
Í þessu tilfelli, sem inniheldur átta
tölur, aftur til baka til baka.

162
00:07:28,480 --> 00:07:30,700
Og við skulum nú eiga mergesort.

163
00:07:30,700 --> 00:07:33,300
Svo ég vil fyrst að raða
vinstri helminginn af þessum lista,

164
00:07:33,300 --> 00:07:37,370
og við skulum því
áherslu á 4, 8, 6, og 2.

165
00:07:37,370 --> 00:07:41,000
>> Nú hvernig get ég farið um
flokkun lista yfir stærð 4?

166
00:07:41,000 --> 00:07:45,990
Jæja ég verð að íhuga nú
flokkun vinstri á vinstri helming.

167
00:07:45,990 --> 00:07:47,720
Aftur, við skulum baka fyrir aðeins augnablik.

168
00:07:47,720 --> 00:07:51,010
Ef sauðakóðanum er þetta,
og ég er að gefa átta þætti,

169
00:07:51,010 --> 00:07:53,230
8 er augljóslega meiri
en eða jafnt og 2.

170
00:07:53,230 --> 00:07:54,980
Svo með fyrsta tilfelli á ekki við.

171
00:07:54,980 --> 00:07:58,120
Svo til að raða átta þætti, ég fyrst
raða vinstri helming þætti,

172
00:07:58,120 --> 00:08:01,930
þá er ég að raða rétt helminginn, þá er ég sameinast
tveir röðuðu helminga, hver stærð 4.

173
00:08:01,930 --> 00:08:02,470
OK.

174
00:08:02,470 --> 00:08:07,480
>> En ef þú hefur bara sagt mér, raða
vinstri helming, sem er nú á stærð 4,

175
00:08:07,480 --> 00:08:09,350
hvernig get ég raða vinstri helminginn?

176
00:08:09,350 --> 00:08:11,430
Jæja ef ég á
inntak af fjórum þáttum,

177
00:08:11,430 --> 00:08:14,590
Ég raða fyrst vinstri
Tveir, þá hægra tveir,

178
00:08:14,590 --> 00:08:16,210
og þá er ég sameinast þeim saman.

179
00:08:16,210 --> 00:08:18,700
Svo aftur, verður það svolítið
af huga beygja leikur hér,

180
00:08:18,700 --> 00:08:21,450
vegna þess að þú, eins konar, að
muna hvar þú ert í sögunni,

181
00:08:21,450 --> 00:08:23,620
en í lok dagsins,
veitt nein fjölda staka,

182
00:08:23,620 --> 00:08:25,620
þú vilt fyrst að raða í
vinstri helminginn og svo hægri helming,

183
00:08:25,620 --> 00:08:26,661
þá sameinast þeim saman.

184
00:08:26,661 --> 00:08:28,630
Við skulum byrja á að gera einmitt það.

185
00:08:28,630 --> 00:08:30,170
Hér er inntak átta þáttum.

186
00:08:30,170 --> 00:08:31,910
Nú erum við að horfa á vinstri helming hér.

187
00:08:31,910 --> 00:08:33,720
Hvernig get ég raða fjóra þætti?

188
00:08:33,720 --> 00:08:35,610
Jæja ég raða fyrsta vinstri helming.

189
00:08:35,610 --> 00:08:37,720
Nú hvernig ég raða vinstri helminginn?

190
00:08:37,720 --> 00:08:39,419
Jæja ég hef fengið tvo þætti.

191
00:08:39,419 --> 00:08:41,240
Svo skulum raða þessum tveimur þáttum.

192
00:08:41,240 --> 00:08:44,540
2 er meiri en eða
sama sem 2, að sjálfsögðu.

193
00:08:44,540 --> 00:08:46,170
Þannig að fyrsta tilfelli á ekki við.

194
00:08:46,170 --> 00:08:49,010
>> Þannig að ég hef nú að raða vinstri
helmingur af þessum tveimur þáttum.

195
00:08:49,010 --> 00:08:50,870
Vinstri helmingur, auðvitað, er bara 4.

196
00:08:50,870 --> 00:08:54,020
Svo hvernig get ég raða lista yfir einn þáttur?

197
00:08:54,020 --> 00:08:57,960
Jæja nú, að sérstakt stöð tilfelli
upp efst, svo að segja, gildir.

198
00:08:57,960 --> 00:09:01,470
1 er minna en 2, og mín
Listinn er reyndar í stærð 1.

199
00:09:01,470 --> 00:09:02,747
Svo ég aftur bara.

200
00:09:02,747 --> 00:09:03,580
Ég geri ekki neitt.

201
00:09:03,580 --> 00:09:06,770
Og reyndar, líta á það sem ég hef
gert, 4 er þegar raðað.

202
00:09:06,770 --> 00:09:09,220
Eins og ég er nú þegar
hluta vel hér.

203
00:09:09,220 --> 00:09:11,750
>> Nú virðist sem eins konar heimskur
kröfu, en það er satt.

204
00:09:11,750 --> 00:09:13,700
4 er listi af stærð 1,.

205
00:09:13,700 --> 00:09:15,090
Það er þegar raðað.

206
00:09:15,090 --> 00:09:16,270
Það er vinstri helmingur.

207
00:09:16,270 --> 00:09:18,010
Nú er ég að raða rétt helminginn.

208
00:09:18,010 --> 00:09:22,310
Inntak mitt er einn þáttur, 8
álíka, þegar raðað.

209
00:09:22,310 --> 00:09:25,170
Stupid, of, en aftur,
þetta grundvallarregla

210
00:09:25,170 --> 00:09:28,310
er að fara að leyfa okkur að nú byggja
ofan á þetta með góðum árangri.

211
00:09:28,310 --> 00:09:32,260
4 flokkaður, 8 er raðað, nú
hvað var það síðasta skrefið?

212
00:09:32,260 --> 00:09:35,330
Svo þriðja og síðasta skrefið, allir
skipti sem þú ert að flokka lista, muna,

213
00:09:35,330 --> 00:09:38,310
var að sameina tvo helminga,
vinstri og hægri.

214
00:09:38,310 --> 00:09:39,900
Svo skulum gera einmitt það.

215
00:09:39,900 --> 00:09:41,940
Vinstri helmingur mín er, að sjálfsögðu, 4.

216
00:09:41,940 --> 00:09:43,310
Hægri helming minn er 8.

217
00:09:43,310 --> 00:09:44,100
>> Svo skulum gera þetta.

218
00:09:44,100 --> 00:09:46,410
Fyrst ég ætla að úthluta
sumir fleiri minni,

219
00:09:46,410 --> 00:09:48,680
að ég tákna hér,
sem bara annar fylking,

220
00:09:48,680 --> 00:09:49,660
sem er nógu stór til að passa þetta.

221
00:09:49,660 --> 00:09:52,243
En þú getur ímyndað nær
að rétthyrningur endilangri,

222
00:09:52,243 --> 00:09:53,290
ef við þurfum meira seinna.

223
00:09:53,290 --> 00:09:58,440
Hvernig tek ég 4 og 8, og sameinast
þessir tveir listar stærð 1 saman?

224
00:09:58,440 --> 00:10:00,270
Hér líka, frekar einfalt.

225
00:10:00,270 --> 00:10:03,300
4 kemur fyrst, þá kemur 8.

226
00:10:03,300 --> 00:10:07,130
Vegna þess að ef ég vil raða
vinstri helminginn og svo hægri helming,

227
00:10:07,130 --> 00:10:09,900
og þá sameinast þessar tvær helminga
saman, í raðaða röð,

228
00:10:09,900 --> 00:10:11,940
4 kemur fyrst, þá kemur 8.

229
00:10:11,940 --> 00:10:15,810
>> Þannig að við virðast vera að framfarir, jafnvel
þó að ég hafi ekki gert neina raunverulegu starfi.

230
00:10:15,810 --> 00:10:17,800
En muna þar sem við erum í sögunni.

231
00:10:17,800 --> 00:10:19,360
Við tók upphaflega átta þætti.

232
00:10:19,360 --> 00:10:21,480
Við raðað vinstri helming, sem er 4.

233
00:10:21,480 --> 00:10:24,450
Þá erum við flokkuð vinstri helming
á vinstri hluta, sem var 2.

234
00:10:24,450 --> 00:10:25,270
Og hér erum við að fara.

235
00:10:25,270 --> 00:10:26,920
Við erum búin með þessi skref.

236
00:10:26,920 --> 00:10:29,930
>> Þannig að ef við höfum raðað í
vinstri helmingi 2, nú erum við

237
00:10:29,930 --> 00:10:32,130
að raða rétt helminginn af 2.

238
00:10:32,130 --> 00:10:35,710
Svo er hægri helminginn af 2
þessi tvö gildi hér, 6 og 2.

239
00:10:35,710 --> 00:10:40,620
Svo skulum við taka nú inntak stærð
2, og raða vinstri helming, og þá

240
00:10:40,620 --> 00:10:42,610
hægri helminginn, og þá
sameina þær saman.

241
00:10:42,610 --> 00:10:45,722
Jæja hvernig ég raða lista af stærð
1, sem inniheldur bara númer 6?

242
00:10:45,722 --> 00:10:46,430
Ég er nú þegar gert.

243
00:10:46,430 --> 00:10:48,680
Listinn yfir stærð 1 er raðað.

244
00:10:48,680 --> 00:10:52,140
>> Hvernig get ég raða annan lista af
stærð 1, svonefnd hægri helminginn.

245
00:10:52,140 --> 00:10:54,690
Jæja það líka, er þegar raðað.

246
00:10:54,690 --> 00:10:56,190
Talan 2 er einn.

247
00:10:56,190 --> 00:11:00,160
Svo nú hef ég tvo helminga, vinstri og
rétt, ég þarf að sameina þá saman.

248
00:11:00,160 --> 00:11:01,800
Leyfðu mér að gefa mér smá auka pláss.

249
00:11:01,800 --> 00:11:05,580
Og setja 2 í það,
þá 6 í það, þannig

250
00:11:05,580 --> 00:11:10,740
flokkun þessi listi, vinstri og hægri,
og sameina það saman, að lokum.

251
00:11:10,740 --> 00:11:12,160
Þannig að ég er í örlítið betra form.

252
00:11:12,160 --> 00:11:16,250
Ég er ekki búinn, því greinilega 4, 8, 2,
6 er ekki endanleg röðun sem ég vil.

253
00:11:16,250 --> 00:11:20,640
En ég hef nú tvo lista af stærð 2, sem
hafa bæði, hver um sig, verið raðað.

254
00:11:20,640 --> 00:11:24,580
Svo nú ef þú til baka í huga þinnar
auga, hvar did sem yfirgefa okkur?

255
00:11:24,580 --> 00:11:28,520
Ég byrjaði með átta þætti, svo ég
tálga það niður á vinstri hluta 4,

256
00:11:28,520 --> 00:11:31,386
þá vinstri helminginn af 2, og
þá hægri helminginn af 2,

257
00:11:31,386 --> 00:11:34,510
Ég kláraði því flokkun vinstri
helmingur af 2, og hægri helminginn af 2,

258
00:11:34,510 --> 00:11:37,800
svo er það þriðja og síðasta skrefið hér?

259
00:11:37,800 --> 00:11:41,290
Ég verð að sameinast saman
tveir listar stærð 2.

260
00:11:41,290 --> 00:11:42,040
Svo skulum við fara á undan.

261
00:11:42,040 --> 00:11:43,940
Og á skjánum hér, gefa
mig sumir fleiri minni,

262
00:11:43,940 --> 00:11:47,170
þótt tæknilega, eftir að ég hef
got a heild búnt af auðu plássi upp efst

263
00:11:47,170 --> 00:11:47,670
þar.

264
00:11:47,670 --> 00:11:50,044
Ef ég vil vera sérstaklega
duglegur rúm vitur,

265
00:11:50,044 --> 00:11:52,960
Ég gæti bara byrja að færa þætti
fram og til baka, efst og neðst.

266
00:11:52,960 --> 00:11:55,460
En bara fyrir sjón skýrleika,
Ég ætla að setja það niður fyrir,

267
00:11:55,460 --> 00:11:56,800
að halda gott og hreint.

268
00:11:56,800 --> 00:11:58,150
>> Svo ég hef fengið tvo lista af stærð 2.

269
00:11:58,150 --> 00:11:59,770
Fyrsti listi er 4 og 8.

270
00:11:59,770 --> 00:12:01,500
Annað listi hefur 2 og 6.

271
00:12:01,500 --> 00:12:03,950
Skulum sameinast þeim
saman í raðaða röð.

272
00:12:03,950 --> 00:12:09,910
2, að sjálfsögðu, kemur fyrst,
þá 4, þá 6, þá 8.

273
00:12:09,910 --> 00:12:12,560
Og nú erum við virðist vera að fá
einhvers staðar áhugavert.

274
00:12:12,560 --> 00:12:15,720
Nú hef ég raðað helmingur
lista, og tilviljun, það er

275
00:12:15,720 --> 00:12:18,650
allar sléttar tölur, en það
er reyndar bara tilviljun.

276
00:12:18,650 --> 00:12:22,220
Og ég nú hafa raðað vinstri
helmingur, þannig að það er 2, 4, 6 og 8.

277
00:12:22,220 --> 00:12:23,430
Ekkert er út af röð.

278
00:12:23,430 --> 00:12:24,620
Það er eins og framfarir.

279
00:12:24,620 --> 00:12:26,650
>> Nú er hún eins og ég hef
verið að tala eilífu nú,

280
00:12:26,650 --> 00:12:29,850
svo er það að koma í ljós hvort þetta
reiknirit er reyndar skilvirkari.

281
00:12:29,850 --> 00:12:31,766
En við erum að fara í gegnum
það frábær skipulega.

282
00:12:31,766 --> 00:12:34,060
A tölva, að sjálfsögðu,
myndi gera það svona.

283
00:12:34,060 --> 00:12:34,840
Svo Hvar erum við?

284
00:12:34,840 --> 00:12:36,180
Við byrjuðum með átta þætti.

285
00:12:36,180 --> 00:12:37,840
Ég flokkaður vinstri helming af 4.

286
00:12:37,840 --> 00:12:39,290
Ég virðist vera búinn með það.

287
00:12:39,290 --> 00:12:42,535
Svo nú er næsta skref að
raða hægri helminginn af 4.

288
00:12:42,535 --> 00:12:44,410
Og þessi hluti sem við getum farið
í gegnum smá meira

289
00:12:44,410 --> 00:12:47,140
fljótt, þótt þú ert
velkomið að baka eða gera hlé, bara

290
00:12:47,140 --> 00:12:49,910
hugsa um það á
eigin hraða, en það

291
00:12:49,910 --> 00:12:53,290
við höfum nú er tækifæri til að
gera nákvæmlega sama reiknirit á fjórum

292
00:12:53,290 --> 00:12:54,380
mismunandi númer.

293
00:12:54,380 --> 00:12:57,740
>> Svo skulum við fara á undan, og leggja áherslu á
hægri helminginn, sem við erum hér.

294
00:12:57,740 --> 00:13:01,260
Vinstri helmingur þess sem
hægri helming, og nú

295
00:13:01,260 --> 00:13:04,560
vinstri helminginn af vinstri
helmingur þess hægri hluta,

296
00:13:04,560 --> 00:13:08,030
og hvernig get ég raða lista af stærð
1 sem inniheldur bara númer 1?

297
00:13:08,030 --> 00:13:09,030
Það er nú þegar gert.

298
00:13:09,030 --> 00:13:11,830
Hvernig á ég að gera það sama fyrir lista
af stærð 1, sem inniheldur bara 7?

299
00:13:11,830 --> 00:13:12,840
Það er nú þegar gert.

300
00:13:12,840 --> 00:13:16,790
Skref þrjú fyrir þennan hálfleik þá
er að sameina þessar tvær þættir

301
00:13:16,790 --> 00:13:20,889
í nýja lista af stærð 2, 1 og 7.

302
00:13:20,889 --> 00:13:23,180
Virðast ekki hafa gert allt
það mikið áhugavert að vinna.

303
00:13:23,180 --> 00:13:24,346
Við skulum sjá hvað gerist næst.

304
00:13:24,346 --> 00:13:29,210
Ég flokkaður bara vinstri helming af þeim
hægri helminginn af upprunalegu inntak mína.

305
00:13:29,210 --> 00:13:32,360
Nú skulum raða rétt
helmingur, sem inniheldur 5 og 3.

306
00:13:32,360 --> 00:13:35,740
Við skulum aftur líta á vinstri
helmingur, raðað, hægri helming, raðað,

307
00:13:35,740 --> 00:13:39,120
og sameinast þessir tveir saman,
í sumum viðbótarrými,

308
00:13:39,120 --> 00:13:41,670
3 kemur fyrst, þá kemur 5.

309
00:13:41,670 --> 00:13:46,190
Og svo nú höfum við raðað í
vinstri helminginn af hægri hluta

310
00:13:46,190 --> 00:13:49,420
af upprunalegu vandamál, og
hægri helminginn af hægri hluta

311
00:13:49,420 --> 00:13:50,800
af upprunalegu vandamálinu.

312
00:13:50,800 --> 00:13:52,480
Hvað er þriðja og síðasta skrefið?

313
00:13:52,480 --> 00:13:54,854
Vel að sameina þessa tvo helminga saman.

314
00:13:54,854 --> 00:13:57,020
Svo láta mig fá mér nokkrar
auka rúm, en, aftur, ég

315
00:13:57,020 --> 00:13:58,699
gæti verið að nota þessi vara rúm upp efst.

316
00:13:58,699 --> 00:14:00,490
En við erum að fara að halda
það einfalt sjónrænt.

317
00:14:00,490 --> 00:14:07,070
Leyfðu mér að sameinast í núna 1 og
þá 3, og síðan 5, og síðan 7.

318
00:14:07,070 --> 00:14:10,740
Þar yfirgefa mig nú með
hægri helminginn af upprunalegu vandamálinu

319
00:14:10,740 --> 00:14:12,840
það er fullkomlega raðað.

320
00:14:12,840 --> 00:14:13,662
>> Svo er það?

321
00:14:13,662 --> 00:14:16,120
Mér finnst eins og ég halda að segja að
sömu hlutina aftur og aftur,

322
00:14:16,120 --> 00:14:18,700
en það er hugsandi af
staðreynd að við erum að nota endurkvæmni.

323
00:14:18,700 --> 00:14:21,050
Ferlið við að nota An
reiknirit aftur, og aftur,

324
00:14:21,050 --> 00:14:23,940
á smærri hlutmengja í
upprunalega vandamálið.

325
00:14:23,940 --> 00:14:27,580
Svo ég nú hafa vinstri flokkuð
helmingur af upprunalegu vandamálinu.

326
00:14:27,580 --> 00:14:30,847
Ég er með rétt flokkaður helmingur
af upprunalegu vandamálinu.

327
00:14:30,847 --> 00:14:32,180
Hvað er þriðja og síðasta skrefið?

328
00:14:32,180 --> 00:14:33,590
Oh, það er samruna.

329
00:14:33,590 --> 00:14:34,480
Svo skulum gera það.

330
00:14:34,480 --> 00:14:36,420
Skulum úthluta sumir viðbótar
minni, en guð minn, við

331
00:14:36,420 --> 00:14:37,503
gæti sett það hvar sem nú.

332
00:14:37,503 --> 00:14:40,356
Við höfum svo mikið pláss í boði
að okkur, en við munum halda það einfalt.

333
00:14:40,356 --> 00:14:42,730
Í stað þess að fara til baka og
fram með upprunalegu minni okkar,

334
00:14:42,730 --> 00:14:44,480
við skulum bara gera það
sjónrænt hérna fyrir neðan,

335
00:14:44,480 --> 00:14:47,240
til að ljúka upp sameina
vinstri helminginn og hægri helminginn.

336
00:14:47,240 --> 00:14:49,279
>> Svo með því að sameina, hvað þarf ég að gera?

337
00:14:49,279 --> 00:14:50,820
Ég vil taka þætti í röð.

338
00:14:50,820 --> 00:14:53,230
Svo að horfa á vinstri helming,
Ég sé fyrsta talan er 2.

339
00:14:53,230 --> 00:14:55,230
Ég lít á hægri hluta,
Ég sé fyrstu töluna

340
00:14:55,230 --> 00:14:58,290
er 1, svo augljóslega sem
Fjöldi ég vil að slíta út,

341
00:14:58,290 --> 00:15:00,430
og setja fyrst í endanlegri listanum mínum?

342
00:15:00,430 --> 00:15:01,449
Að sjálfsögðu, 1.

343
00:15:01,449 --> 00:15:02,990
Nú vil ég að biðja um að sömu spurningu.

344
00:15:02,990 --> 00:15:05,040
Á vinstri hluta, ég hef
enn fékk númer 2.

345
00:15:05,040 --> 00:15:07,490
Á hægri hluta,
Ég hef fengið fjölda 3.

346
00:15:07,490 --> 00:15:08,930
Hver einn vil ég að velja?

347
00:15:08,930 --> 00:15:11,760
Auðvitað, númer 2 og
nú eftir frambjóðendur

348
00:15:11,760 --> 00:15:13,620
eru 4 til vinstri, 3 til hægri.

349
00:15:13,620 --> 00:15:15,020
Skulum auðvitað velja 3.

350
00:15:15,020 --> 00:15:18,020
Nú frambjóðendur eru 4 á
vinstri, 5 á hægri.

351
00:15:18,020 --> 00:15:19,460
Við, að sjálfsögðu, að velja 4.

352
00:15:19,460 --> 00:15:21,240
6 á vinstri, 5 til hægri.

353
00:15:21,240 --> 00:15:22,730
Við, að sjálfsögðu, að velja 5.

354
00:15:22,730 --> 00:15:25,020
6 á vinstri, 7 hægri.

355
00:15:25,020 --> 00:15:29,320
Við valið 6, og þá erum við
velja 7, og þá erum við að velja 8.

356
00:15:29,320 --> 00:15:30,100
Voila.

357
00:15:30,100 --> 00:15:34,370
>> Svo a gríðarstór tala af orðum síðar, við
hafa raðað þessum lista yfir átta þætti

358
00:15:34,370 --> 00:15:38,450
inn lista af eitt gegnum átta,
sem er vaxandi með hverju skrefi,

359
00:15:38,450 --> 00:15:40,850
en hversu mikill tími fór
það taka okkur að gera það.

360
00:15:40,850 --> 00:15:43,190
Jæja ég hef vísvitandi
sem mælt er fyrir það út á myndrænan

361
00:15:43,190 --> 00:15:46,330
hér, svo að við getum konar
sjá eða meta skiptingu

362
00:15:46,330 --> 00:15:49,060
í sigra sem hefur verið að gerast.

363
00:15:49,060 --> 00:15:52,830
>> Reyndar ef þú horfir aftur á kjölfar,
Ég hef skilið allar þessar punktalínurnar

364
00:15:52,830 --> 00:15:55,660
í stað eigenda, þú getur,
konar, skoða, í öfugri röð,

365
00:15:55,660 --> 00:15:58,800
ef þú lítur svona aftur í
Saga nú, upprunalega listanum mínum

366
00:15:58,800 --> 00:16:00,250
er, að sjálfsögðu, af stærð 8.

367
00:16:00,250 --> 00:16:03,480
Og þá áður, ég var
að takast á við tveir listar stærð 4,

368
00:16:03,480 --> 00:16:08,400
og þá fjórar skrár yfir stærð 2,
og þá átta listar stærð 1.

369
00:16:08,400 --> 00:16:10,151
>> Svo hvað þýðir þetta,
konar, minna þig á?

370
00:16:10,151 --> 00:16:11,858
Jæja, reyndar eitthvað af
reiknirit sem við höfum

371
00:16:11,858 --> 00:16:14,430
horfði á svona langt þar sem við
skipta, og skipta, og skipta,

372
00:16:14,430 --> 00:16:19,500
halda að hafa hlutina aftur og
aftur, leiðir í þessu almenna hugmynd.

373
00:16:19,500 --> 00:16:23,100
Og svo er það eitthvað
lógaritmískum gerast hér.

374
00:16:23,100 --> 00:16:26,790
Og það er ekki alveg log n, en
það er Logarythmiskur hluti

375
00:16:26,790 --> 00:16:28,280
að það sem við höfum bara gert.

376
00:16:28,280 --> 00:16:31,570
>> Nú skulum íhuga hvernig það í raun er.

377
00:16:31,570 --> 00:16:34,481
Svo log n, aftur var
mikill hlaupandi tíma,

378
00:16:34,481 --> 00:16:36,980
þegar við gerðum eitthvað eins
Tvíundarleit, eins og við nú kalla það,

379
00:16:36,980 --> 00:16:40,090
deilum og sigra stefnu
um sem við fundum Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Nú tæknilega.

381
00:16:41,020 --> 00:16:43,640
Það er Log stöð 2 af N, jafnvel
þó í flestum stærðfræði bekkjum,

382
00:16:43,640 --> 00:16:45,770
10 er yfirleitt grunn sem þú tekur.

383
00:16:45,770 --> 00:16:48,940
En tölva vísindamenn næstum alltaf
hugsa og tala í skilmálar af grunn 2,

384
00:16:48,940 --> 00:16:52,569
þannig að við yfirleitt bara segja þig inn á
n, í stað þess að log undirstaða 2 af N,

385
00:16:52,569 --> 00:16:55,110
en þeir eru nákvæmlega eitt og
sama í heimi tölva

386
00:16:55,110 --> 00:16:57,234
vísindi, og eins og innskot,
það er stöðug þáttur

387
00:16:57,234 --> 00:17:01,070
munur á milli tveggja, svo það er
moot engu að síður, til að fá meiri formlega ástæðum.

388
00:17:01,070 --> 00:17:04,520
>> En nú, hvað við umönnun
um er þetta dæmi.

389
00:17:04,520 --> 00:17:08,520
Svo skulum ekki sannað með fordæmi, en á
kosti nota dæmi um tölur

390
00:17:08,520 --> 00:17:10,730
hendi sem andleg heilbrigði stöðva, ef þú vilt.

391
00:17:10,730 --> 00:17:14,510
Svo áður uppskrift var Log stöð
2 n, en það er n í þessu tilfelli.

392
00:17:14,510 --> 00:17:18,526
Ég hafði n upprunalega tölur, eða 8
af upprunalega númerið sérstaklega.

393
00:17:18,526 --> 00:17:20,359
Nú það hefur verið smá
meðan, en ég er nokkuð

394
00:17:20,359 --> 00:17:25,300
viss um að skrá þig inn stöð 2
af verðmæti 8 er 3,

395
00:17:25,300 --> 00:17:29,630
og reyndar hvað er gott um það er
að 3 er einmitt sá fjöldi skipta

396
00:17:29,630 --> 00:17:33,320
að þú getur deilt lista
lengd 8 aftur og aftur,

397
00:17:33,320 --> 00:17:36,160
og aftur, þar til þú ert vinstri
með lista af aðeins stærð 1.

398
00:17:36,160 --> 00:17:36,660
Ekki satt?

399
00:17:36,660 --> 00:17:40,790
8 fer til 4, fer í 2,
fer til 1, og það er

400
00:17:40,790 --> 00:17:43,470
hugsandi um nákvæmlega sem
mynd sem við höfðum bara í smá stund síðan.

401
00:17:43,470 --> 00:17:47,160
Svo smá geðheilsan stöðva um hvar
lógariþmi er í raun að ræða.

402
00:17:47,160 --> 00:17:50,180
>> Svo nú, hvað er að ræða hér? n.

403
00:17:50,180 --> 00:17:53,440
Svo eftir að hver
þegar ég skipt á listanum,

404
00:17:53,440 --> 00:17:58,260
að vísu í öfugri röð í sögu
hér, ég var enn að gera n hlutina.

405
00:17:58,260 --> 00:18:02,320
Sem sameina skref þarf að
Ég snerti hver og einn af tölum,

406
00:18:02,320 --> 00:18:05,060
í því skyni að renna henni í
viðeigandi stað.

407
00:18:05,060 --> 00:18:10,760
Svo jafnvel þótt hæð þessu
skýringarmynd af stærð log n n eða 3,

408
00:18:10,760 --> 00:18:13,860
sérstaklega, með öðrum orðum,
Ég gerði þrjú svið hér.

409
00:18:13,860 --> 00:18:18,800
Hversu mikið verk gerði ég lárétt
eftir þessari töflu í hvert skipti?

410
00:18:18,800 --> 00:18:21,110
>> Jæja, ég gerði n þrep
vinna, vegna þess að ef ég hef

411
00:18:21,110 --> 00:18:24,080
fékk fjóra þætti og fjóra þætti,
og ég þarf að sameina þá saman.

412
00:18:24,080 --> 00:18:26,040
Ég þarf að fara í gegnum
þessir fjórir og þessir fjórir,

413
00:18:26,040 --> 00:18:28,123
að lokum að sameina þá
aftur í átta þáttum.

414
00:18:28,123 --> 00:18:32,182
Ef öfugt ég hef fengið átta fingur
hérna, sem ég er ekki, og átta

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- Ef ég hef
fékk fjóra fingur hérna,

416
00:18:34,390 --> 00:18:37,380
sem ég, fjórir fingur
hérna, sem ég geri,

417
00:18:37,380 --> 00:18:40,590
þá er það sama
dæmi eins og áður, ef ég geri

418
00:18:40,590 --> 00:18:44,010
hafa átta fingur þó í
alls, sem ég get, svona, gera.

419
00:18:44,010 --> 00:18:47,950
Ég er einmitt að gera hér,
þá get ég örugglega

420
00:18:47,950 --> 00:18:50,370
Sameina öll af þessum listum
af stærð 1 saman.

421
00:18:50,370 --> 00:18:54,050
En ég hef vissulega að líta
á hverju frumefni nákvæmlega einu sinni.

422
00:18:54,050 --> 00:18:59,640
Svo er hæð þessa ferlis log n,
breidd þessu ferli, svo að segja,

423
00:18:59,640 --> 00:19:02,490
er n, svo hvað við virðumst
að hafa, að lokum er

424
00:19:02,490 --> 00:19:06,470
a hlaupandi tími stærð n sinnum log n.

425
00:19:06,470 --> 00:19:08,977
>> Með öðrum orðum, skipt við
listi, Log n sinnum,

426
00:19:08,977 --> 00:19:11,810
en í hvert sinn sem við gerðum það, við höfðum
að snerta hver og einn af þeim þáttum

427
00:19:11,810 --> 00:19:13,560
í því skyni að sameina þá
allt saman, sem

428
00:19:13,560 --> 00:19:18,120
var n skref, þannig að við höfum n sinnum log n,
eða eins og a tölva vísindamaður myndi segja,

429
00:19:18,120 --> 00:19:20,380
slík-, sem
væri stórt orð

430
00:19:20,380 --> 00:19:22,810
til að lýsa efri
bundið á keyra tíma,

431
00:19:22,810 --> 00:19:28,010
við erum að keyra í stóru o
log n tíma, svo að segja.

432
00:19:28,010 --> 00:19:31,510
>> Nú er þetta mikilvæg, því
muna hvað gangi sinnum voru

433
00:19:31,510 --> 00:19:34,120
með kúla tagi, og val
flokka, og innsetning tegund,

434
00:19:34,120 --> 00:19:38,200
og jafnvel fáir aðrir sem eru til,
n veldi var þar sem við vorum á.

435
00:19:38,200 --> 00:19:39,990
Og þú getur, eins konar, sjá þetta hér.

436
00:19:39,990 --> 00:19:45,720
Ef n veldi er augljóslega n sinnum
n, en hér höfum við n sinnum log n,

437
00:19:45,720 --> 00:19:48,770
og við vitum nú þegar frá viku
núll, það log n, vegna lógaritmískrar,

438
00:19:48,770 --> 00:19:50,550
er betra en eitthvað línuleg.

439
00:19:50,550 --> 00:19:52,930
Eftir allt saman, muna myndina
með rauða og gula

440
00:19:52,930 --> 00:19:56,500
og græna línur sem við Drew, sem
grænt lógaritmískum lína var mun lægra.

441
00:19:56,500 --> 00:20:00,920
Og þess vegna, miklu betur og hraðar
en beinar gulu og rauðu línanna,

442
00:20:00,920 --> 00:20:05,900
n sinnum log n er reyndar betra,
en n sinnum N, eða n veldi.

443
00:20:05,900 --> 00:20:09,110
>> Þannig að við virðast hafa
bent reiknirit sameinast

444
00:20:09,110 --> 00:20:11,870
tagi sem keyrir í miklu
festa tíma, og örugglega,

445
00:20:11,870 --> 00:20:16,560
þess vegna, fyrr í þessari viku, þegar
Við sáum að keppni milli kúla

446
00:20:16,560 --> 00:20:20,750
tegund, val flokka, og sameinast
raða, mergesort virkilega, virkilega unnið.

447
00:20:20,750 --> 00:20:23,660
Og reyndar, við vissum ekki einu sinni að bíða
fyrir kúla flokka og val tagi

448
00:20:23,660 --> 00:20:24,790
að klára.

449
00:20:24,790 --> 00:20:27,410
>> Nú skulum taka eitt annað skot
á þessu, frá örlítið meira

450
00:20:27,410 --> 00:20:31,030
formleg sjónarmið, bara í
ræða, þetta endurómar betur

451
00:20:31,030 --> 00:20:33,380
en að hærra stigi umræðu.

452
00:20:33,380 --> 00:20:34,880
Svo hér er reiknirit aftur.

453
00:20:34,880 --> 00:20:36,770
Við skulum spyrja okkur
hvað hlaupandi tími

454
00:20:36,770 --> 00:20:39,287
er þetta reiknirit ýmsar ráðstafanir?

455
00:20:39,287 --> 00:20:41,620
Skulum skipta því í fyrsta
málið og annað mál.

456
00:20:41,620 --> 00:20:46,280
The EF og annað í IF ræða,
Ef n er minna en 2, bara aftur.

457
00:20:46,280 --> 00:20:47,580
Líður eins föstu tíma.

458
00:20:47,580 --> 00:20:50,970
Það er, eins konar, eins tveimur skrefum,
Ef n er minna en 2, síðan aftur.

459
00:20:50,970 --> 00:20:54,580
En eins og ég sagði á mánudag,
föstu tíma, eða stór eða 1,

460
00:20:54,580 --> 00:20:57,130
getur verið tvö skref, þrjú
skref, jafnvel 1.000 skrefum.

461
00:20:57,130 --> 00:20:59,870
Það sem skiptir máli er að það sé
stöðug tala af skrefum.

462
00:20:59,870 --> 00:21:03,240
Svo gula hápunktur sauðakóðanum
hér liggur í, við munum kalla það,

463
00:21:03,240 --> 00:21:04,490
fasti tími.

464
00:21:04,490 --> 00:21:06,780
Svo fleiri formlega og
við erum að fara to-- þetta

465
00:21:06,780 --> 00:21:09,910
verður að hve miklu leyti við
formlega þennan rétt now-- T frá n,

466
00:21:09,910 --> 00:21:15,030
gangi tími vandamál
sem tekur n somethings sem inntak,

467
00:21:15,030 --> 00:21:19,150
jafngildir stór eða einn,
Ef n er minna en 2 pm.

468
00:21:19,150 --> 00:21:20,640
Svo það er skilyrt á það.

469
00:21:20,640 --> 00:21:24,150
Svo til að vera skýr, ef n er minna en
2, við höfum mjög stuttan lista, þá

470
00:21:24,150 --> 00:21:29,151
gangi tíma, T af n, þar sem n er
1 eða 0, í þetta mjög sérstaka tilviki,

471
00:21:29,151 --> 00:21:30,650
það er bara að fara að vera stöðug tími.

472
00:21:30,650 --> 00:21:32,691
Það er að fara að taka einn
stíga, tvö skref, hvað sem er.

473
00:21:32,691 --> 00:21:33,950
Það er ákveðinn fjölda af skrefum.

474
00:21:33,950 --> 00:21:38,840
>> Svo safaríkur hluti hlýtur að vera í
hinn raunin í sauðakóðanum.

475
00:21:38,840 --> 00:21:40,220
The ELSE ræða.

476
00:21:40,220 --> 00:21:44,870
Raða eftir helmingur þætti, flokka rétt
helmingur þætti, sameinast flokkuð helminga.

477
00:21:44,870 --> 00:21:46,800
Hversu langan tíma tekur hver af þeim skrefum taka?

478
00:21:46,800 --> 00:21:49,780
Jæja, ef keyra
kominn tími til að raða n þætti

479
00:21:49,780 --> 00:21:53,010
er, við skulum kalla það mjög
generically, T af N,

480
00:21:53,010 --> 00:21:55,500
þá flokka vinstri
helmingur af þeim þáttum

481
00:21:55,500 --> 00:21:59,720
er góður af eins og að segja,
T n deilt með 2,

482
00:21:59,720 --> 00:22:03,000
og álíka flokka rétt helminginn
þætti er góður af eins og að segja,

483
00:22:03,000 --> 00:22:06,974
T af N skipt 2, og þá
sameina flokkuð helminga.

484
00:22:06,974 --> 00:22:08,890
Jæja ef ég hef fengið nokkrar
Fjöldi staka hér,

485
00:22:08,890 --> 00:22:11,230
eins fjögur og sumir tala
þætti hér, eins og fjórir,

486
00:22:11,230 --> 00:22:14,650
og ég verð að sameinast hvert af þessum fjórum
í, og hver af þessum fjórum í, einn

487
00:22:14,650 --> 00:22:17,160
á eftir öðrum, þannig að
lokum Ég hef átta þætti.

488
00:22:17,160 --> 00:22:20,230
Mér finnst eins og það er stór eða af n skrefum?

489
00:22:20,230 --> 00:22:23,500
Ef ég hef fengið n fingur og hvert
þá þarf að sameinast í stað,

490
00:22:23,500 --> 00:22:25,270
það er eins og önnur n skrefum.

491
00:22:25,270 --> 00:22:27,360
>> Svo reyndar formulaically,
við getum tjáð þetta,

492
00:22:27,360 --> 00:22:29,960
að vísu smá skelfing í fyrstu
sýn, en það er eitthvað

493
00:22:29,960 --> 00:22:31,600
sem fangar einmitt þessi rökfræði.

494
00:22:31,600 --> 00:22:35,710
Keyrslutíminn, T af N, að ef n
er meiri en eða jafnt og 2.

495
00:22:35,710 --> 00:22:42,500
Í þessu tilviki, að annað tilfelli, er T n
deilt með 2, auk T af N deilt með 2,

496
00:22:42,500 --> 00:22:45,320
auk stór O af N, sum
línuleg tala af skrefum,

497
00:22:45,320 --> 00:22:51,630
kannski einmitt n, kannski 2 sinnum
n, en það er um það bil, til n.

498
00:22:51,630 --> 00:22:54,060
Svo það líka er, hvernig við getum
tjá þetta formulaically.

499
00:22:54,060 --> 00:22:56,809
Nú þú vildi ekki vita þetta nema
þú hefur skráð það í huga þínum,

500
00:22:56,809 --> 00:22:58,710
eða líta upp í
aftur á kennslubók, sem

501
00:22:58,710 --> 00:23:00,501
gæti hafa smá
Cheat Sheet á enda,

502
00:23:00,501 --> 00:23:03,940
en þetta er reyndar að fara að
gefa okkur a stór eða af n log n,

503
00:23:03,940 --> 00:23:06,620
vegna þess að endurkoma sem
þú sérð hér á skjánum,

504
00:23:06,620 --> 00:23:09,550
ef þú gerðir í raun það út, með
óendanlega mörg dæmi,

505
00:23:09,550 --> 00:23:13,000
eða þú gerðir það formulaically, þú myndir
sjá að þetta, því þetta formúlu

506
00:23:13,000 --> 00:23:17,100
sjálft er endurkvæma, með t af
n yfir eitthvað hægra megin,

507
00:23:17,100 --> 00:23:21,680
og t n yfir á vinstri, þetta getur
í raun verið lýst, að lokum,

508
00:23:21,680 --> 00:23:24,339
eins stór fara af n log n.

509
00:23:24,339 --> 00:23:26,130
Ef ekki sannfærður, það er
fínt fyrir nú, bara

510
00:23:26,130 --> 00:23:28,960
taka á trú, að það er, örugglega,
hvað það endurkomu leiðir til,

511
00:23:28,960 --> 00:23:31,780
en þetta er bara aðeins meira af a
stærðfræði nálgun til að leita

512
00:23:31,780 --> 00:23:36,520
á gangi þegar mergesort
miðað sauðakóðanum þess einn.

513
00:23:36,520 --> 00:23:39,030
>> Nú skulum taka a hluti af a
breather frá allt að,

514
00:23:39,030 --> 00:23:41,710
og taka a líta á a
víst fyrrverandi öldungadeildarþingmaður, sem

515
00:23:41,710 --> 00:23:44,260
getur litið svolítið þekki,
sem settist niður með Eiríki Google

516
00:23:44,260 --> 00:23:48,410
Schmidt, fyrir nokkru, fyrir viðtal
á sviðinu, fyrir framan a heild búnt

517
00:23:48,410 --> 00:23:53,710
af fólki, tala á endanum um
umræða, það er nokkuð núna þekki.

518
00:23:53,710 --> 00:23:54,575
Við skulum taka a líta.

519
00:23:54,575 --> 00:24:01,020

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt: Nú Senator,
þú ert hér á Google,

521
00:24:03,890 --> 00:24:09,490
og ég eins og til hugsa af
formennsku sem atvinnuviðtal.

522
00:24:09,490 --> 00:24:11,712
Nú er erfitt að fá vinnu sem forseti.

523
00:24:11,712 --> 00:24:12,670
PRESIDENT OBAMA: Hægri.

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt: Og þú ert
fara að gera [inaudible] nú.

525
00:24:13,940 --> 00:24:15,523
Það er líka erfitt að fá vinnu á Google.

526
00:24:15,523 --> 00:24:17,700
PRESIDENT OBAMA: Hægri.

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt: Við hafa spurningar,
og við biðjum frambjóðendur spurningum okkar,

528
00:24:21,330 --> 00:24:24,310
og þetta er frá Larry Schwimmer.

529
00:24:24,310 --> 00:24:25,890
>> PRESIDENT OBAMA: OK.

530
00:24:25,890 --> 00:24:27,005
>> Eric Schmidt: Hvað?

531
00:24:27,005 --> 00:24:28,130
Þú krakkar hugsa ég grínast?

532
00:24:28,130 --> 00:24:30,590
Það er hérna.

533
00:24:30,590 --> 00:24:33,490
Hvað er skilvirkasta leiðin til að
raða milljón 32 bita heiltölur?

534
00:24:33,490 --> 00:24:37,560

535
00:24:37,560 --> 00:24:38,979
>> PRESIDENT OBAMA: Well--

536
00:24:38,979 --> 00:24:41,020
Eric Schmidt: Stundum,
kannski Fyrirgefðu, maybe--

537
00:24:41,020 --> 00:24:42,750
Obama forseti: Nei, nei,
nei, nei, nei, think-- I

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt: Það er ekki it--

539
00:24:43,240 --> 00:24:45,430
PRESIDENT OBAMA: I
held, ég held kúla

540
00:24:45,430 --> 00:24:46,875
raða væri röng leið til að fara.

541
00:24:46,875 --> 00:24:49,619

542
00:24:49,619 --> 00:24:50,535
Eric Schmidt: Komdu.

543
00:24:50,535 --> 00:24:52,200
Hver sagði honum þetta?

544
00:24:52,200 --> 00:24:54,020
OK.

545
00:24:54,020 --> 00:24:55,590
Ég gerði ekki tölvunarfræði on--

546
00:24:55,590 --> 00:24:58,986
>> PRESIDENT OBAMA: Við höfum
fékk njósnara okkar í það.

547
00:24:58,986 --> 00:24:59,860
Prófessor: Allt í lagi.

548
00:24:59,860 --> 00:25:03,370
Við skulum fara á bak okkur nú
fræðilega heim reiknirita

549
00:25:03,370 --> 00:25:06,520
í aðfelluþrýstingi greiningu
þeirra, og aftur sumum efni

550
00:25:06,520 --> 00:25:09,940
frá viku núll og einn, og í byrjun
að fjarlægja nokkur þjálfun hjól,

551
00:25:09,940 --> 00:25:10,450
ef þú vilt.

552
00:25:10,450 --> 00:25:13,241
Svo að þú skiljir virkilega
lokum frá grunni, það er

553
00:25:13,241 --> 00:25:16,805
fara á undir hetta, þegar þér
skrifa, safna saman og keyrt forrit.

554
00:25:16,805 --> 00:25:19,680
Muna einkum að þetta var
fyrsta C program við skoðuðum,

555
00:25:19,680 --> 00:25:22,840
Canonical, einfalt forrit
konar, tiltölulega séð,

556
00:25:22,840 --> 00:25:24,620
þar sem, það prentar, Hello World.

557
00:25:24,620 --> 00:25:27,610
Og muna að ég sagði, að þetta ferli
að kóðinn fer í gegnum

558
00:25:27,610 --> 00:25:28,430
er nákvæmlega þetta.

559
00:25:28,430 --> 00:25:31,180
Þú tekur kóðann þinn, fara
það í gegnum þýðanda, eins Clang,

560
00:25:31,180 --> 00:25:34,650
og út kemur mótmæla kóða, sem
gæti litið svona út, núll og sjálfur

561
00:25:34,650 --> 00:25:37,880
að CPU í tölvunni, Mið
vinnslu eining eða heila,

562
00:25:37,880 --> 00:25:39,760
lokum skilur.

563
00:25:39,760 --> 00:25:42,460
>> Það kemur í ljós að það er
hluti af einföldun,

564
00:25:42,460 --> 00:25:44,480
að við erum nú í
stöðu til að stríða í sundur

565
00:25:44,480 --> 00:25:46,720
að skilja hvað er í raun verið
fara á undir hetta

566
00:25:46,720 --> 00:25:48,600
hvert skipti sem þú keyrir
Clang, eða oftast

567
00:25:48,600 --> 00:25:53,040
hvert skipti sem þú gerir áætlun,
nota Gera og CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
Einkum, efni eins
þetta er fyrsta mynda,

569
00:25:56,760 --> 00:25:58,684
Þegar þú saman fyrst program.

570
00:25:58,684 --> 00:26:00,600
Með öðrum orðum, þegar þú
taka kóðann þinn

571
00:26:00,600 --> 00:26:04,390
og þýða það, hvað er fyrsta
að outputted með Clang

572
00:26:04,390 --> 00:26:06,370
er eitthvað þekktur sem samkoma kóða.

573
00:26:06,370 --> 00:26:08,990
Og í raun, það lítur út nákvæmlega eins og þetta.

574
00:26:08,990 --> 00:26:11,170
>> Ég rak stjórn á the
stjórn lína fyrr.

575
00:26:11,170 --> 00:26:16,260
Clang DASH höfuðborgarsvæðisins hello.c,
og þetta skapaði skrá

576
00:26:16,260 --> 00:26:19,490
fyrir mig heitir hello.s,
inni sem var nákvæmlega

577
00:26:19,490 --> 00:26:22,290
þessi innihald og aðeins meira
ofan og aðeins meira neðan,

578
00:26:22,290 --> 00:26:25,080
en ég hef sett juiciest
upplýsingar hér á skjánum.

579
00:26:25,080 --> 00:26:29,190
Og ef þú lítur vel, munt þú sjá
að minnsta kosti nokkur kunnugleg leitarorð.

580
00:26:29,190 --> 00:26:31,330
Við höfum helsta efst.

581
00:26:31,330 --> 00:26:35,140
Við höfum printf niður í miðju.

582
00:26:35,140 --> 00:26:38,670
Og við höfum líka halló heimur
sviga n í gæsalöppum þarna fyrir neðan.

583
00:26:38,670 --> 00:26:42,450
>> Og allt annað hér
er mjög lágt leiðbeiningar

584
00:26:42,450 --> 00:26:45,500
að CPU the tölva 'skilur.

585
00:26:45,500 --> 00:26:50,090
CPU leiðbeiningar sem færa minni
um, að hlaða strengir frá minni,

586
00:26:50,090 --> 00:26:52,750
og að lokum, prenta
sem er á skjánum.

587
00:26:52,750 --> 00:26:56,780
Nú gerist það þó eftir
þetta samkoma kóða er mynda?

588
00:26:56,780 --> 00:26:59,964
Lokum, þú, örugglega,
enn búa mótmæla kóða.

589
00:26:59,964 --> 00:27:02,630
En þau skref sem hafa í raun
verið að fara á undir hetta

590
00:27:02,630 --> 00:27:04,180
líta aðeins meira eins og þetta.

591
00:27:04,180 --> 00:27:08,390
Kóðinn verður samkoma númer,
sem þá verður mótmæla kóða,

592
00:27:08,390 --> 00:27:11,930
og aðgerðir orð hér eru að
Þegar þú saman kóðann þinn,

593
00:27:11,930 --> 00:27:16,300
út kemur samkoma kóða, og þá
þegar þú saman samkoma númerið þitt,

594
00:27:16,300 --> 00:27:17,800
út kemur mótmæla kóða.

595
00:27:17,800 --> 00:27:20,360
>> Nú er Clang frábær háþróuð,
eins mikið af vistþýðendur,

596
00:27:20,360 --> 00:27:23,151
og það er öllum þessum skrefum
saman, og það er ekki endilega

597
00:27:23,151 --> 00:27:25,360
framleiðsla allir millistig
skrár sem þú getur jafnvel sjá.

598
00:27:25,360 --> 00:27:28,400
Það safnar bara hlutina,
sem er almennt hugtak sem

599
00:27:28,400 --> 00:27:30,000
lýsir þessu öllu ferlinu.

600
00:27:30,000 --> 00:27:32,000
En ef þú vilt virkilega
að vera sérstaklega, það er

601
00:27:32,000 --> 00:27:34,330
mikið meira að fara á það eins og heilbrigður.

602
00:27:34,330 --> 00:27:38,860
>> En við skulum íhuga nú einnig að jafnvel
sem frábær einfalt forrit, hello.c,

603
00:27:38,860 --> 00:27:40,540
kallað virka.

604
00:27:40,540 --> 00:27:41,870
Það heitir printf.

605
00:27:41,870 --> 00:27:46,900
En ég hafði ekki skrifað printf, örugglega,
sem kemur með c, svo að segja.

606
00:27:46,900 --> 00:27:51,139
Það er aðgerð muna það er
lýst í venjulegu io.h, sem

607
00:27:51,139 --> 00:27:53,180
er haus skrá, sem
er umræða sem við munum í raun

608
00:27:53,180 --> 00:27:55,780
kafa í meira dýpi áður en langur.

609
00:27:55,780 --> 00:27:58,000
En haus skrá er
yfirleitt í fylgd

610
00:27:58,000 --> 00:28:02,920
með kóða skrá, kóðinn skrá, svo
mikið eins og það er til staðlað io.h.

611
00:28:02,920 --> 00:28:05,930
>> Einhvern síðan, einhver,
eða einhvers, skrifaði einnig

612
00:28:05,930 --> 00:28:11,040
skrá sem heitir staðall io.c, í
sem í raun skilgreiningar,

613
00:28:11,040 --> 00:28:15,220
eða útfærslur printf,
og bunches annarra aðgerðir,

614
00:28:15,220 --> 00:28:16,870
eru í raun skrifuð.

615
00:28:16,870 --> 00:28:22,140
Svo í ljósi þess, ef við teljum með
hér á vinstri, hello.c, að þegar

616
00:28:22,140 --> 00:28:26,250
saman, gefur okkur hello.s, jafnvel þótt
Clang ekki trufla sparnaður í stað

617
00:28:26,250 --> 00:28:31,360
við getum séð það, og að samkoma kóða
fær saman í hello.o, sem

618
00:28:31,360 --> 00:28:34,630
er reyndar sjálfgefið nafn
gefið þegar þú saman uppspretta

619
00:28:34,630 --> 00:28:39,350
kóða í hlut kóða, en eru ekki
alveg tilbúin að framkvæma það enn,

620
00:28:39,350 --> 00:28:41,460
því eitt skref
þarf að gerast, og hefur

621
00:28:41,460 --> 00:28:44,440
verið að gerast undanfarin
vikur, kannski Unbeknownst þig.

622
00:28:44,440 --> 00:28:47,290
>> Sérstaklega einhversstaðar
í CS50 IDE, og þetta,

623
00:28:47,290 --> 00:28:49,870
of, verður hluti af óákveðinn greinir í ensku
einföldun um stund,

624
00:28:49,870 --> 00:28:54,670
það er, eða var á þeim tíma,
skrá sem heitir staðall io.c,

625
00:28:54,670 --> 00:28:58,440
að einhver unnin í
staðall io.s eða sem nemur,

626
00:28:58,440 --> 00:29:02,010
að einhver svo saman
í venjulegu io.o,

627
00:29:02,010 --> 00:29:04,600
eða það kemur í ljós í a
örlítið öðruvísi skrá

628
00:29:04,600 --> 00:29:07,220
snið sem geta haft mismunandi
skrá eftirnafn öllu leyti,

629
00:29:07,220 --> 00:29:11,720
en í orði og eðli, nákvæmlega
þeir stíga þurfti að gerast í einhverri mynd.

630
00:29:11,720 --> 00:29:14,060
Sem er að segja, að nú
þegar ég er að skrifa forrit,

631
00:29:14,060 --> 00:29:17,870
hello.c, sem bara segir, halló heimur,
og ég er að nota kóðann einhvers annars

632
00:29:17,870 --> 00:29:22,480
eins printf, sem var einu sinni á
tími, í skrá sem kallast staðall io.c,

633
00:29:22,480 --> 00:29:26,390
þá einhvern veginn verð ég að taka minn
mótmæla kóða, núll mínir og sjálfur,

634
00:29:26,390 --> 00:29:29,260
og hlut sem viðkomandi
númeri, eða núll og sjálfur,

635
00:29:29,260 --> 00:29:34,970
og einhvern veginn tengja þá saman í
Eitt síðasta skrá, sem heitir halló, sem

636
00:29:34,970 --> 00:29:38,070
hefur alla núll og
sjálfur frá meginvirkni minn,

637
00:29:38,070 --> 00:29:40,830
og öllum núllum
og sjálfur fyrir printf.

638
00:29:40,830 --> 00:29:44,900
>> Og reyndar, að síðustu ferli er
kallað, tengir mótmæla kóðann þinn.

639
00:29:44,900 --> 00:29:47,490
Framleiðsla sem
er executable skrá.

640
00:29:47,490 --> 00:29:49,780
Svo í sanngirni, á
lok dagsins, ekkert

641
00:29:49,780 --> 00:29:52,660
hefur breyst síðan viku eitt, þegar við
byrjaði fyrst að setja saman áætlanir.

642
00:29:52,660 --> 00:29:55,200
Reyndar, allt þetta hefur verið
gerast undir hetta,

643
00:29:55,200 --> 00:29:57,241
en nú erum við í aðstöðu
þar sem við getum í raun

644
00:29:57,241 --> 00:29:58,794
stríða í sundur þessar mismunandi skrefum.

645
00:29:58,794 --> 00:30:00,710
Og reyndar, í lok
dagsins, við erum enn

646
00:30:00,710 --> 00:30:04,480
vinstri með núll og sjálfur, sem
er í raun frábær segue nú

647
00:30:04,480 --> 00:30:08,620
til annars getu C, að
við höfum ekki þurft að nýta líklegast

648
00:30:08,620 --> 00:30:11,250
hingað til, þekktur sem Bita rekstraraðila.

649
00:30:11,250 --> 00:30:15,220
Með öðrum orðum, svona langt, hvenær sem við höfum
fjallað gögnum í C eða breytur í C,

650
00:30:15,220 --> 00:30:17,660
við höfum haft það eins
stafir og flýtur og ins

651
00:30:17,660 --> 00:30:21,990
og þráir og tveggja manna og þess háttar, en
Allir sem eru að minnsta kosti átta bitar.

652
00:30:21,990 --> 00:30:25,550
Við höfum aldrei tekist að
vinna einstaka bita,

653
00:30:25,550 --> 00:30:28,970
jafnvel þótt einstaka hluti, við
veist, getur táknað 0 og 1.

654
00:30:28,970 --> 00:30:32,640
Nú kemur í ljós að í C, þú
Hægt er að fá aðgang að einstökum bitum,

655
00:30:32,640 --> 00:30:35,530
ef þú veist setningafræði,
sem að fá á þá.

656
00:30:35,530 --> 00:30:38,010
>> Svo skulum taka a líta
á Bita rekstraraðila.

657
00:30:38,010 --> 00:30:41,700
Svo á myndinni hér eru nokkur tákn sem
við höfum, eins konar, eins konar, séð áður.

658
00:30:41,700 --> 00:30:45,580
Ég sé merkið, lóðrétt
Bar, og sumir aðrir sem vel,

659
00:30:45,580 --> 00:30:49,430
og muna að merkið merkið
er eitthvað sem við höfum séð áður.

660
00:30:49,430 --> 00:30:54,060
Rökrétt AND, þar sem þú þarft
tveir þeirra saman, eða rökrétt OR

661
00:30:54,060 --> 00:30:56,300
rekstraraðila, þar sem þú
hafa tvö lóðrétt bars.

662
00:30:56,300 --> 00:31:00,550
Bita rekstraraðila, sem við munum
sjá starfa á bita fyrir sig,

663
00:31:00,550 --> 00:31:03,810
bara að nota einn merkið, a
einn lóðrétt strik, sem bendillinn tákn

664
00:31:03,810 --> 00:31:06,620
kemur næst, litla
tilda, og síðan til vinstri

665
00:31:06,620 --> 00:31:08,990
krappi vinstri krappi, eða
hægri hornklofi hægri hornklofi.

666
00:31:08,990 --> 00:31:10,770
Hvert þessara hafa mismunandi merkingu.

667
00:31:10,770 --> 00:31:11,950
>> Í raun, við skulum taka a líta.

668
00:31:11,950 --> 00:31:16,560
Við skulum fara gamla skóla í dag, og nota
a snerta skjár frá fyrra,

669
00:31:16,560 --> 00:31:18,002
þekktur sem hvítt borð.

670
00:31:18,002 --> 00:31:19,710
Og þetta tússtöflu
er að fara að leyfa okkur

671
00:31:19,710 --> 00:31:27,360
að tjá nokkrar nokkuð einföld tákn,
eða öllu heldur sumir nokkuð einföld uppskrift,

672
00:31:27,360 --> 00:31:29,560
að við getum þá á endanum
skiptimynt, í því skyni

673
00:31:29,560 --> 00:31:33,230
til að fá aðgang einstaklingur
bitar innan C program.

674
00:31:33,230 --> 00:31:34,480
Með öðrum orðum, við skulum gera þetta.

675
00:31:34,480 --> 00:31:37,080
Fyrsta tala skulum fyrir a
stund um merkið,

676
00:31:37,080 --> 00:31:39,560
sem er Bita AND.

677
00:31:39,560 --> 00:31:42,130
Með öðrum orðum, þetta er
rekstraraðili sem gerir

678
00:31:42,130 --> 00:31:45,930
mig að hafa vinstri-hönd breytu
Venjulega, og hægri handar breytu,

679
00:31:45,930 --> 00:31:50,640
eða einstaklingur gildi, að ef við AND
þá saman, gefur mér endanlega niðurstöðu.

680
00:31:50,640 --> 00:31:51,560
Svo hvað ég meina?

681
00:31:51,560 --> 00:31:54,840
Ef í forriti, þú þarft breytu
sem geymir einn af þessum gildum,

682
00:31:54,840 --> 00:31:58,000
eða við skulum halda það einfalt, og bara
skrifa út núll og sjálfur sig,

683
00:31:58,000 --> 00:32:00,940
hér er hvernig merkið rekstraraðila virkar.

684
00:32:00,940 --> 00:32:06,400
0 merkið 0 er að fara að jafna 0.

685
00:32:06,400 --> 00:32:07,210
Nú er ástæðan fyrir því?

686
00:32:07,210 --> 00:32:09,291
>> Það er mjög svipað
Boolean tjáning,

687
00:32:09,291 --> 00:32:10,540
sem við höfum rætt svona langt.

688
00:32:10,540 --> 00:32:15,800
Ef þú heldur að eftir allt, 0 er
rangar, 0 er ósatt, falskur og falskur

689
00:32:15,800 --> 00:32:18,720
er, eins og við höfum rætt
rökrétt, einnig rangar.

690
00:32:18,720 --> 00:32:20,270
Þannig að við fáum 0 hér eins og heilbrigður.

691
00:32:20,270 --> 00:32:24,390
Ef þú tekur 0 merkið
1, vel það líka,

692
00:32:24,390 --> 00:32:29,890
er að fara að vera 0, því að til þess
vinstri hönd tjáning til að vera satt eða 1,

693
00:32:29,890 --> 00:32:32,360
það þyrfti að vera satt og rétt.

694
00:32:32,360 --> 00:32:36,320
En hér höfum við rangar
og satt, eða 0 og 1.

695
00:32:36,320 --> 00:32:42,000
Nú aftur: Ef við höfum 1 merkið
0, það líka, er að fara að vera 0,

696
00:32:42,000 --> 00:32:47,240
og ef við höfum 1 merkið 1,
loksins höfum við í 1 hluti.

697
00:32:47,240 --> 00:32:50,340
Svo í öðrum orðum, við erum ekki að gera
eitthvað áhugavert við þetta rekstraraðila

698
00:32:50,340 --> 00:32:51,850
bara enn, þetta merkið rekstraraðila.

699
00:32:51,850 --> 00:32:53,780
Það er Bita AND.

700
00:32:53,780 --> 00:32:57,290
En þetta eru innihaldsefni
um sem við getum gert

701
00:32:57,290 --> 00:32:59,240
áhugavert, eins og við munum sjá fljótlega.

702
00:32:59,240 --> 00:33:02,790
>> Nú skulum líta á bara einn
lóðrétt strik hérna til hægri.

703
00:33:02,790 --> 00:33:06,710
Ef ég er með 0 hluti og ég
OR það með, Bita

704
00:33:06,710 --> 00:33:11,030
OR rekstraraðila, annar 0 hluti,
það er að fara að gefa mér 0.

705
00:33:11,030 --> 00:33:17,540
Ef ég tek í 0 hluti og eða það með
1 hluti, þá er ég að fara að fá 1.

706
00:33:17,540 --> 00:33:19,830
Og í raun, bara til
skýrleika, láta mig fara aftur,

707
00:33:19,830 --> 00:33:23,380
þannig að lóðrétt barir mínir
eru ekki skakkur fyrir 1 er.

708
00:33:23,380 --> 00:33:26,560
Leyfðu mér að umrita öll
1 mín er svolítið meira

709
00:33:26,560 --> 00:33:32,700
greinilega, svo að við sjáum næst, ef ég
hafa a 1 eða 0, það er að fara til vera a 1,

710
00:33:32,700 --> 00:33:39,060
og ef ég er með 1 eða 1 sem,
of, er að fara til vera a 1.

711
00:33:39,060 --> 00:33:42,900
Svo er hægt að sjá rökrétt að OR
Rekstraraðili hegðar sér mjög öðruvísi.

712
00:33:42,900 --> 00:33:48,070
Þetta gefur mér 0 OR 0 gefur mér 0, en
annan hvern samsetning gefur mér 1.

713
00:33:48,070 --> 00:33:52,480
Svo lengi sem ég hef eitt 1 á
uppskrift, niðurstaðan er að fara að vera 1.

714
00:33:52,480 --> 00:33:55,580
>> Með því móti við og
Rekstraraðili, merkið,

715
00:33:55,580 --> 00:34:00,940
ef ég hef tvær 1 er í
jöfnu, ég fæ reyndar 1 út.

716
00:34:00,940 --> 00:34:02,850
Nú er það nokkur annar
eins og þær eru vel.

717
00:34:02,850 --> 00:34:04,810
Einn af þeim er lítið annað að ræða.

718
00:34:04,810 --> 00:34:07,980
Svo láta mig fara á undan og eyða
þetta til að losa upp pláss.

719
00:34:07,980 --> 00:34:13,020

720
00:34:13,020 --> 00:34:16,460
Og við skulum taka a líta á the
bendillinn tákn, fyrir aðeins augnablik.

721
00:34:16,460 --> 00:34:18,210
Þetta er yfirleitt
eðli þú getur slegið

722
00:34:18,210 --> 00:34:21,420
á hljómborð halda Shift og
þá einn af tölum topp Bandaríkjunum þinn

723
00:34:21,420 --> 00:34:22,250
hljómborð.

724
00:34:22,250 --> 00:34:26,190
>> Þannig að þetta er eingöngu
OR rekstraraðila, einkarétt OR.

725
00:34:26,190 --> 00:34:27,790
Þannig að við sáum bara eða rekstraraðila.

726
00:34:27,790 --> 00:34:29,348
Þetta er eingöngu eða rekstraraðila.

727
00:34:29,348 --> 00:34:30,639
Hvað er í raun munurinn?

728
00:34:30,639 --> 00:34:34,570
Jæja við skulum líta bara á formúluna,
og nota þetta sem hráefni lokum.

729
00:34:34,570 --> 00:34:37,690
0 XOR 0.

730
00:34:37,690 --> 00:34:39,650
Ég ætla að segja er alltaf 0.

731
00:34:39,650 --> 00:34:41,400
Það er skilgreiningin á XOR.

732
00:34:41,400 --> 00:34:47,104
0 XOR 1 er að fara að vera 1.

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 er að fara að vera 1,
og 1 XOR 1 er að fara að vera?

734
00:34:58,810 --> 00:34:59,890
Rangt?

735
00:34:59,890 --> 00:35:00,520
Eða hægri?

736
00:35:00,520 --> 00:35:01,860
Ég veit það ekki.

737
00:35:01,860 --> 00:35:02,810
0.

738
00:35:02,810 --> 00:35:04,700
Nú hvað er að gerast hér?

739
00:35:04,700 --> 00:35:06,630
Jæja hugsa um
Nafn þessa rekstraraðila.

740
00:35:06,630 --> 00:35:09,980
Exclusive OR, svo sem
nafn, svona bendir,

741
00:35:09,980 --> 00:35:13,940
svarið er bara að fara að vera
1 ef inntak eru einir,

742
00:35:13,940 --> 00:35:15,560
eingöngu öðruvísi.

743
00:35:15,560 --> 00:35:18,170
Svo hér inntak eru
sama, þannig að framleiðsla er 0.

744
00:35:18,170 --> 00:35:20,700
Hér aðföngin eru
sama, þannig að framleiðsla er 0.

745
00:35:20,700 --> 00:35:25,640
Hér eru útgangar eru mismunandi, þau
eru einir, og svo að framleiðsla er 1.

746
00:35:25,640 --> 00:35:28,190
Svo það er mjög svipað og
Og það er mjög svipuð,

747
00:35:28,190 --> 00:35:32,760
eða öllu heldur er það mjög svipað
OR, en aðeins í sérstakri hátt.

748
00:35:32,760 --> 00:35:36,210
Þessi er ekki lengur 1,
vegna þess að við höfum tvær 1 er,

749
00:35:36,210 --> 00:35:38,621
og ekki eingöngu, bara einn af þeim.

750
00:35:38,621 --> 00:35:39,120
Allt í lagi.

751
00:35:39,120 --> 00:35:40,080
Hvað um hina?

752
00:35:40,080 --> 00:35:44,220
Jæja tilda, á meðan er
reyndar gott og einfalt, sem betur fer.

753
00:35:44,220 --> 00:35:46,410
Og þetta er unary
rekstraraðila, sem þýðir

754
00:35:46,410 --> 00:35:50,400
það er beitt til aðeins einn inntak,
einn operand, svo að segja.

755
00:35:50,400 --> 00:35:51,800
Ekki til vinstri og hægri.

756
00:35:51,800 --> 00:35:56,050
Með öðrum orðum, ef þú tekur Tilde af
0, svarið verður hið gagnstæða.

757
00:35:56,050 --> 00:35:59,710
Og ef þú tekur tilda af 1,
Svarið verður hið gagnstæða.

758
00:35:59,710 --> 00:36:02,570
Svo er tilda rekstraraðila
leið ávinnst aðeins,

759
00:36:02,570 --> 00:36:06,000
eða ósvífni aðeins frá
0 til 1, eða 1 til 0.

760
00:36:06,000 --> 00:36:09,820
>> Og það skilur okkur að lokum
með aðeins tvo síðustu rekstraraðila,

761
00:36:09,820 --> 00:36:13,840
svokölluð vinstri Shift, og
svokölluð hægri vakt rekstraraðila.

762
00:36:13,840 --> 00:36:16,620
Við skulum taka a líta á hvernig þeir vinna.

763
00:36:16,620 --> 00:36:20,780
Left Shift rekstraraðila, skrifað
með tveimur horn sviga eins og þessi,

764
00:36:20,780 --> 00:36:22,110
starfar eins og hér segir.

765
00:36:22,110 --> 00:36:27,390
Ef inntak mín, eða operand minn, til vinstri
breyting rekstraraðila er einfaldlega 1.

766
00:36:27,390 --> 00:36:33,750
Og ég segi þá tölva til
vinstri vakt sem 1, segja sjö stöðum,

767
00:36:33,750 --> 00:36:37,150
niðurstaðan er eins og ég
taka þessi 1 og færa það

768
00:36:37,150 --> 00:36:40,160
sjö stöðum á við
vinstri, og við vanræksla,

769
00:36:40,160 --> 00:36:42,270
við erum að fara að gera ráð fyrir að
pláss til hægri

770
00:36:42,270 --> 00:36:44,080
er að fara að vera bólstruð með núllum.

771
00:36:44,080 --> 00:36:50,316
Með öðrum orðum, 1 vinstri vakt 7 er að fara
til að gefa mér að 1, fylgt eftir með 1, 2, 3,

772
00:36:50,316 --> 00:36:54,060
4, 5, 6, 7 núll.

773
00:36:54,060 --> 00:36:57,380
Það á þann hátt, að það gerir þér kleift að
taka fáeinum eins og 1,

774
00:36:57,380 --> 00:37:00,740
og greinilega gera það mikið
miklu, miklu stærri á þennan hátt,

775
00:37:00,740 --> 00:37:06,460
en við erum í raun að fara að sjá
meira snjall aðferðir fyrir það

776
00:37:06,460 --> 00:37:08,080
í staðinn, eins og heilbrigður,

777
00:37:08,080 --> 00:37:08,720
>> Allt í lagi.

778
00:37:08,720 --> 00:37:10,060
Það er það fyrir viku þrjú.

779
00:37:10,060 --> 00:37:11,400
Við munum sjá þig næst.

780
00:37:11,400 --> 00:37:12,770
Þetta var CS50.

781
00:37:12,770 --> 00:37:17,270

782
00:37:17,270 --> 00:37:22,243
>> [TÓNLIST spila]

783
00:37:22,243 --> 00:37:25,766
>> Ræðumaður 1: Hann var á snarl
bar borða heitan Fudge sundae.

784
00:37:25,766 --> 00:37:28,090
Hann hafði það allt yfir andlit hans.

785
00:37:28,090 --> 00:37:30,506
Hann er þreytandi að súkkulaði eins skegg

786
00:37:30,506 --> 00:37:31,756
Ræðumaður 2: Hvað ert þú að gera?

787
00:37:31,756 --> 00:37:32,422
Ræðumaður 3: Hmmm?

788
00:37:32,422 --> 00:37:33,500
Hvað?

789
00:37:33,500 --> 00:37:36,800
>> Ræðumaður 2: Vissir þú réttlátur tvöfaldur dýfa?

790
00:37:36,800 --> 00:37:38,585
Þú dýfði tvöfalt flís.

791
00:37:38,585 --> 00:37:39,460
Ræðumaður 3: Afsakaðu.

792
00:37:39,460 --> 00:37:44,440
Ræðumaður 2: Þú dýfði flís, þú
tók bita, og þú dýfði aftur.

793
00:37:44,440 --> 00:37:44,940
Ræðumaður 3:

794
00:37:44,940 --> 00:37:48,440
Ræðumaður 2: Svo það er eins og að setja
allt munninn rétt dýfa.

795
00:37:48,440 --> 00:37:52,400
Næst þegar þú tekur flís,
bara dýfa einu sinni, og enda það.

796
00:37:52,400 --> 00:37:53,890
>> Ræðumaður 3: Þú veist hvað, Dan?

797
00:37:53,890 --> 00:37:58,006
Þú dýfa leið sem þú vilt að dýfa.

798
00:37:58,006 --> 00:38:01,900
Ég dýfa hvernig sem ég vil að dýfa.

799
00:38:01,900 --> 00:38:03,194