1
00:00:00,000 --> 00:00:11,904
>> [Muzikos grojimo]

2
00:00:11,904 --> 00:00:12,910
>> PROFESORIUS: Visos dešinę.

3
00:00:12,910 --> 00:00:16,730
Tai yra, ir tai yra CS50
savaitę nuo trijų pabaigos.

4
00:00:16,730 --> 00:00:20,230
Taigi mes čia šiandien, o ne Sanders
Teatras, o ne į WEIDNER bibliotekoje.

5
00:00:20,230 --> 00:00:23,170
Kurio viduje yra studija
žinomas kaip Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
arba sakome Studio H, arba
mes say-- Jei jums patiko šį juokelį,

7
00:00:28,310 --> 00:00:30,540
tai tikrai iš
klasiokas, ženklas, internete,

8
00:00:30,540 --> 00:00:32,420
kuris pasiūlė kiek per "Twitter".

9
00:00:32,420 --> 00:00:34,270
Dabar kas kietas apie
kad čia studijoje

10
00:00:34,270 --> 00:00:38,410
yra tai, kad aš apsupta tai žalia
sienos, žalia ekranas arba chromakey,

11
00:00:38,410 --> 00:00:43,290
taip sakant, tai reiškia, kad CS50 s
gamybos komanda, nežinant mane

12
00:00:43,290 --> 00:00:47,380
dabar, gali būti išleisti
man dauguma visame pasaulyje,

13
00:00:47,380 --> 00:00:48,660
geriau ar blogiau.

14
00:00:48,660 --> 00:00:51,800
>> Dabar, kas laukia priekyje, problema nustatyti
du yra jūsų rankose šią savaitę,

15
00:00:51,800 --> 00:00:53,830
bet su problema nustatyti
tris šių metų savaitę

16
00:00:53,830 --> 00:00:56,600
Jums bus užginčyti su
vadinamasis žaidimas 15

17
00:00:56,600 --> 00:00:58,960
senas šalis palankumą, kad
jums gali prisiminti gavimo

18
00:00:58,960 --> 00:01:02,030
kaip vaikas, kad turi visa krūva
skaičių, kad gali skaidrę aukštyn, žemyn,

19
00:01:02,030 --> 00:01:05,790
kairę ir į dešinę, ir ten vienas tarpas
per galvosūkį, į kurį

20
00:01:05,790 --> 00:01:07,840
iš tikrųjų galite skaidrę tuos įspūdį.

21
00:01:07,840 --> 00:01:11,150
Galų gale jūs gaunate tai
dėlionės kai pusiau atsitiktine tvarka,

22
00:01:11,150 --> 00:01:12,940
ir tikslas yra
rūšiuoti, iš viršaus į apačią,

23
00:01:12,940 --> 00:01:16,310
kairės į dešinę, iš vienos
visą kelią iki per 15.

24
00:01:16,310 --> 00:01:19,360
>> Deja, įgyvendinimas
jūs turėsite po ranka

25
00:01:19,360 --> 00:01:21,590
bus programinė įranga
pagrindu, ne fiziškai.

26
00:01:21,590 --> 00:01:25,280
Jūs iš tikrųjų teks rašyti
kodas, su kuriuo studentas arba vartotojas gali

27
00:01:25,280 --> 00:01:26,760
žaisti 15 rungtynes.

28
00:01:26,760 --> 00:01:29,030
Ir iš tikrųjų, hakeris
leidimas žaidimas 15

29
00:01:29,030 --> 00:01:32,155
jums bus iššūkis įgyvendinti,
ne tik Šio seno mokykloje vienodos

30
00:01:32,155 --> 00:01:35,010
žaidimas, bet veikiau sprendimas
jo, įgyvendinant Dievo režimas,

31
00:01:35,010 --> 00:01:38,280
taip sakant, kad iš tikrųjų
išsprendžia galvosūkį už žmogaus,

32
00:01:38,280 --> 00:01:41,080
suteikiant jiems užuomina,
po užuominą, po užuominą.

33
00:01:41,080 --> 00:01:42,280
Taigi daugiau apie tai kitą savaitę.

34
00:01:42,280 --> 00:01:43,720
Bet tai, kas laukia priekyje.

35
00:01:43,720 --> 00:01:47,610
>> Nes dabar priminti, kad anksčiau šią savaitę
mes turėjome šį Įspūdingos filmą, jei norite,

36
00:01:47,610 --> 00:01:52,560
kuriuo geriausia, ką veikėte rūšiavimas
Išminčius buvo viršutinė riba didelis O n

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

38
00:01:53,210 --> 00:01:56,520
Kitaip tariant, burbulas rūšiuoti,
pasirinkimas rūšiuoti, įterpimo rūšiuoti,

39
00:01:56,520 --> 00:01:59,120
visi iš jų, tuo tarpu skirtingi
jų įgyvendinimą,

40
00:01:59,120 --> 00:02:03,480
perduotos į n kvadratu veikia
Laikas labai blogiausiu atveju.

41
00:02:03,480 --> 00:02:06,010
Ir mes paprastai manome, kad
labai blogiausiu atveju rūšiavimo

42
00:02:06,010 --> 00:02:08,814
yra vienas, kad jūsų indėlis
yra visiškai atgal.

43
00:02:08,814 --> 00:02:11,980
Ir iš tiesų, jis paėmė nemažai priemonių,
įgyvendinti kiekviena iš šių algoritmo.

44
00:02:11,980 --> 00:02:15,110
>> Dabar pačioje pabaigoje klasės
Prisiminkite, mes palyginti burbulas rūšiuoti

45
00:02:15,110 --> 00:02:19,390
prieš atrankos rūšiuoti prieš vieną kitą
kad mes vadinami suliejimo rūšiuoti tuo metu,

46
00:02:19,390 --> 00:02:22,120
ir siūlau, kad tai atsižvelgiant
privalumas nuo savaitės pamoką

47
00:02:22,120 --> 00:02:24,060
nulis, skaldyk ir valdyk.

48
00:02:24,060 --> 00:02:28,810
Ir kažkaip pasiekti tam tikrą rūšį
logaritminė bėgančio laiko, galiausiai,

49
00:02:28,810 --> 00:02:31,024
vietoj kažką
tai grynai kvadratinė.

50
00:02:31,024 --> 00:02:33,440
Ir tai ne visai logaritminė,
tai šiek tiek daugiau nei tai.

51
00:02:33,440 --> 00:02:36,520
Bet jei jūs prisimenate iš klasės,
tai buvo daug, daug greičiau.

52
00:02:36,520 --> 00:02:38,210
Leiskite pažvelgti, kur mes baigėte išvaizdą.

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

54
00:02:41,880 --> 00:02:45,370
>> Burbulas rūšiuoti, palyginti atrankos
Rūšiuoti palyginti merge rūšiuoti.

55
00:02:45,370 --> 00:02:47,700
Dabar jie visi veikia, yra
teorija, tuo pačiu metu.

56
00:02:47,700 --> 00:02:50,510
CPU veikia tuo pačiu greičiu.

57
00:02:50,510 --> 00:02:54,990
Bet jūs galite pajusti, kaip nuobodu tai
labai greitai taps,

58
00:02:54,990 --> 00:02:58,790
ir tiesiog, kaip greitai, kai mes švirkšti
visą savaitę Zero algoritmų tiek,

59
00:02:58,790 --> 00:03:00,080
mes galime pagreitinti.

60
00:03:00,080 --> 00:03:01,630
>> Taigi ženklas Rūšiuoti atrodo nuostabi.

61
00:03:01,630 --> 00:03:05,220
Kaip mes galime išnaudoti jį, kad
greičiau rūšiuoti numerius.

62
00:03:05,220 --> 00:03:07,140
Na pagalvokime atgal
komponentui, kad mes

63
00:03:07,140 --> 00:03:10,380
turėjo grįžti į nulinę savaitę, kad
ieškoti ką nors į telefonų knygą,

64
00:03:10,380 --> 00:03:12,380
ir priminti, kad
Pseudocode, kad mes pasiūlėme,

65
00:03:12,380 --> 00:03:14,560
per kurį mes galime rasti
kažkas panašaus Mike Smith,

66
00:03:14,560 --> 00:03:16,310
atrodė šiek tiek kažką panašaus į tai.

67
00:03:16,310 --> 00:03:20,820
>> Dabar imtis ypač išvaizdą
eilutėje 7 ir 8, ir 10 ir 11,

68
00:03:20,820 --> 00:03:25,240
kurios sukelia tą kilpą, kurią mes nuolat
grįžta į liniją 3 vėl, ir vėl,

69
00:03:25,240 --> 00:03:26,520
ir vėl.

70
00:03:26,520 --> 00:03:31,790
Tačiau paaiškėja, kad mes galime pamatyti
Šis algoritmas, čia Pseudocode,

71
00:03:31,790 --> 00:03:33,620
šiek tiek daugiau holistiškai.

72
00:03:33,620 --> 00:03:35,960
Tiesą sakant, tai, ką aš ieškote
bent čia ekrane,

73
00:03:35,960 --> 00:03:41,180
yra paieškai algoritmas
Mike Smith tarp kai kurių puslapių rinkiniu.

74
00:03:41,180 --> 00:03:45,520
Ir iš tiesų, mes galime supaprastinti šį
algoritmas tose 7 ir 8 linijų,

75
00:03:45,520 --> 00:03:49,860
ir 10 ir 11, tiesiog pasakyti, kad tai,
kurios aš čia pateikiama geltonai.

76
00:03:49,860 --> 00:03:52,210
Kitaip tariant, jei Mike
Smith anksčiau knygoje,

77
00:03:52,210 --> 00:03:55,004
mums nereikia nurodyti žingsnis
po žingsnio, dabar, kaip eiti jo rasti.

78
00:03:55,004 --> 00:03:56,920
Neturime nurodyti
grįžti į liniją 3

79
00:03:56,920 --> 00:03:58,960
Kodėl ne mes tiesiog vietoj to,
tarkim, apskritai,

80
00:03:58,960 --> 00:04:01,500
ieškoti Mike į
kairė pusė knygos.

81
00:04:01,500 --> 00:04:03,960
>> Ir atvirkščiai, jei Mike
iš tikrųjų vėliau knygoje,

82
00:04:03,960 --> 00:04:07,540
kodėl ne mes tiesiog pacituoti citatos pabaiga paiešką
Mike dešinėje pusėje knygoje.

83
00:04:07,540 --> 00:04:11,030
Kitaip tariant, tai kodėl gi ne mes tiesiog
rūšiuoti punt sau sakydamas:

84
00:04:11,030 --> 00:04:13,130
ieškoti Mike šiame
poaibis knygos,

85
00:04:13,130 --> 00:04:16,279
ir palikite jį į mūsų esamų
algoritmas pasakykite mums

86
00:04:16,279 --> 00:04:18,750
Kaip ieškoti mike
kad kairė pusė knygos.

87
00:04:18,750 --> 00:04:20,750
Kitaip tariant, mūsų
algoritmas veikia, ar tai

88
00:04:20,750 --> 00:04:24,670
telefono knyga tokio storio, tai
storis, arba bet kokio storio kokia.

89
00:04:24,670 --> 00:04:27,826
Taigi, mes galime rekursyviai
apibrėžti šį algoritmą.

90
00:04:27,826 --> 00:04:29,950
Kitaip tariant, dėl
ekranas čia yra algoritmas

91
00:04:29,950 --> 00:04:33,130
paieškai Mike Smith
tarp telefono knygos puslapiuose.

92
00:04:33,130 --> 00:04:37,410
Taigi 7 ir 10 eilutė, tegul
tiesiog pasakyti būtent tai.

93
00:04:37,410 --> 00:04:40,250
Ir aš naudoju šį terminą akimirkai
Prieš ir iš tiesų, rekursija

94
00:04:40,250 --> 00:04:42,450
yra madingas terminas dabar,
ir tai šis procesas

95
00:04:42,450 --> 00:04:47,210
daro kažką cikliško iki kažkaip
naudojant kodą, kurį jūs jau turite,

96
00:04:47,210 --> 00:04:49,722
ir raginama jį dar kartą,
ir vėl, ir vėl.

97
00:04:49,722 --> 00:04:51,930
Dabar jis ketina būti svarbi
kad mes kažkaip apačioje

98
00:04:51,930 --> 00:04:53,821
užduotis, ir nereikia daryti, kad be galo ilgai.

99
00:04:53,821 --> 00:04:56,070
Priešingu atveju mes ketiname
iš tikrųjų begalinis ciklas.

100
00:04:56,070 --> 00:04:59,810
Bet pažiūrėkime, ar mes galime skolintis šią idėją
iš rekursijos, daro kažką naujo

101
00:04:59,810 --> 00:05:03,600
ir vėl, ir vėl, spręsti
rūšiavimo problema per suliejimo

102
00:05:03,600 --> 00:05:05,900
Rūšiuoti, visi efektyviau.

103
00:05:05,900 --> 00:05:06,970
>> Taigi, aš suteikti jums sujungti rūšiuoti.

104
00:05:06,970 --> 00:05:07,920
Leiskite pažvelgti.

105
00:05:07,920 --> 00:05:10,850
Taigi čia yra Pseudocode, su
kuris galėtume įgyvendinti rūšiavimo,

106
00:05:10,850 --> 00:05:12,640
naudojant šį algoritmą, pavadintą sujungti rūšiuoti.

107
00:05:12,640 --> 00:05:13,880
Ir tai paprasčiausiai tai.

108
00:05:13,880 --> 00:05:15,940
Apie įvesties n elementų,
Kitaip tariant, jei esate

109
00:05:15,940 --> 00:05:18,830
suteikta n elementai ir numeriai bei
laiškus ar kokia įvestis,

110
00:05:18,830 --> 00:05:22,430
jei jums suteikta n elementų, jei
n yra mažiau nei 2, tiesiog grįžti.

111
00:05:22,430 --> 00:05:22,930
Teisė?

112
00:05:22,930 --> 00:05:26,430
Nes jei n yra mažiau nei 2, kad
tai reiškia, kad mano sąrašas elementų

113
00:05:26,430 --> 00:05:30,446
yra arba dydžio 0 arba 1, ir
tiek iš tų nereikšmingų atvejų,

114
00:05:30,446 --> 00:05:31,570
sąrašas jau rūšiuojamos.

115
00:05:31,570 --> 00:05:32,810
Jei nėra sąraše, tai rūšiuojamos.

116
00:05:32,810 --> 00:05:35,185
Ir jei ten ilgio sąrašas
1, tai akivaizdžiai rūšiuojami.

117
00:05:35,185 --> 00:05:38,280
Taigi algoritmas turi tik
tikrai padaryti kažką įdomaus,

118
00:05:38,280 --> 00:05:40,870
jei mes turime du ar daugiau
elementai mums duota.

119
00:05:40,870 --> 00:05:42,440
Taigi pažvelkime į magijos tada.

120
00:05:42,440 --> 00:05:47,500
Kita rūšiuoti kairįjį pusę elementų,
tada rūšiuoti tinkamą pusę elementų,

121
00:05:47,500 --> 00:05:49,640
tada sujungti surūšiuoti puses.

122
00:05:49,640 --> 00:05:52,440
Ir kas rūšies proto lenkimo
čia yra, kad aš tikrai ne

123
00:05:52,440 --> 00:05:56,190
Atrodo, kad jums sakiau,
nieko nėra, tiesa?

124
00:05:56,190 --> 00:05:59,560
Viskas, ką aš sakiau yra, nes iš sąrašo
n elementų, rūšiuoti yra kairėje pusėje,

125
00:05:59,560 --> 00:06:01,800
tada į dešinę pusę, tada
sujungti rūšiuoti puses,

126
00:06:01,800 --> 00:06:03,840
Bet kur yra tikrasis slaptą padažu?

127
00:06:03,840 --> 00:06:05,260
Kur yra algoritmas?

128
00:06:05,260 --> 00:06:09,150
Na paaiškėja, kad šių dviejų linijų
Pirma, tarsi liko pusė elementų,

129
00:06:09,150 --> 00:06:13,970
ir rūšiuoti teisę pusė elementų,
yra pasikartojantys skambučiai, taip sakant.

130
00:06:13,970 --> 00:06:16,120
>> Galų gale, ne tai
momentas, turiu

131
00:06:16,120 --> 00:06:18,950
algoritmas, su kuria
rūšiuoti visa krūva elementų?

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

133
00:06:19,450 --> 00:06:20,620
Tai čia.

134
00:06:20,620 --> 00:06:25,180
Tai čia ekrane ir
todėl galiu naudoti tą patį rinkinį žingsnių

135
00:06:25,180 --> 00:06:28,500
rūšiuoti yra kairėje pusėje,
kaip aš galiu teisė pusę.

136
00:06:28,500 --> 00:06:30,420
Ir iš tiesų, vėl, ir vėl.

137
00:06:30,420 --> 00:06:34,210
Taigi vienaip ar kitaip, ir mes netrukus
pamatyti tai, apie merge rūšiuoti magija

138
00:06:34,210 --> 00:06:37,967
yra įdėta, kad labai galutinis
linija, sujungti surūšiuoti puses.

139
00:06:37,967 --> 00:06:39,300
Ir tai atrodo gana intuityvus.

140
00:06:39,300 --> 00:06:41,050
Jūs imtis dvi dalis, ir jūs,
kažkaip, sujungti juos kartu,

141
00:06:41,050 --> 00:06:43,260
ir mes pamatyti, tai
konkrečiai per akimirką.

142
00:06:43,260 --> 00:06:45,080
>> Tačiau tai yra pilnas algoritmas.

143
00:06:45,080 --> 00:06:46,640
Ir pažiūrėkime tiksliai, kodėl.

144
00:06:46,640 --> 00:06:50,912
Na manau, kad mes Atsižvelgiant į šiuos pats
aštuonios čia elementus ekrane, vienas

145
00:06:50,912 --> 00:06:53,120
per aštuonių, bet jie
iš pažiūros atsitiktine tvarka.

146
00:06:53,120 --> 00:06:55,320
Ir po ranka tikslas
rūšiuoti šiuos elementus.

147
00:06:55,320 --> 00:06:58,280
Na kaip aš galiu eiti apie
daro jį naudoti, vėlgi,

148
00:06:58,280 --> 00:07:00,407
sujungti rūšiuoti, kaip už šio Pseudocode?

149
00:07:00,407 --> 00:07:02,740
Ir vėl, Įsitvirtino tai
jūsų protas, nes tik akimirką.

150
00:07:02,740 --> 00:07:05,270
Pirmasis atvejis yra gana
trivialus, jei ji mažesnė kaip 2,

151
00:07:05,270 --> 00:07:07,060
tiesiog grįžti, nėra nuveikti.

152
00:07:07,060 --> 00:07:09,290
Taigi tikrai ten tik trys
žingsnių, kad tikrai reikia nepamiršti.

153
00:07:09,290 --> 00:07:11,081
Vėlgi, ir vėl, aš
ketinate nori turėti

154
00:07:11,081 --> 00:07:13,980
rūšiuoti yra kairėje pusėje,
rūšiuoti tinkamą pusę,

155
00:07:13,980 --> 00:07:15,890
ir tada, kai jų
dvi puselės yra rūšiuojami,

156
00:07:15,890 --> 00:07:18,710
Noriu sujungti juos kartu
į vieną rūšiuotų sąrašą.

157
00:07:18,710 --> 00:07:19,940
Taigi keep that in mind.

158
00:07:19,940 --> 00:07:21,310
>> Taigi čia originalus sąrašą.

159
00:07:21,310 --> 00:07:23,510
Leiskite gydyti tai kaip
masyvas, kaip mes pradėjome

160
00:07:23,510 --> 00:07:25,800
dviejose savaitę, kuris yra
ribotis blokas atminties.

161
00:07:25,800 --> 00:07:28,480
Šiuo atveju, kurių sudėtyje yra aštuoni
numeriai, atgal atgal į nugarą.

162
00:07:28,480 --> 00:07:30,700
Ir tegul dabar taikomos suliejimo rūšiuoti.

163
00:07:30,700 --> 00:07:33,300
Taigi aš pirmą norite rūšiuoti
kairė pusė šio sąrašo,

164
00:07:33,300 --> 00:07:37,370
Ir tegul, todėl
sutelkti dėmesį į 4, 8, 6 ir 2.

165
00:07:37,370 --> 00:07:41,000
>> Dabar kaip man eiti apie
rūšiavimas nuo dydžio 4 sąrašą?

166
00:07:41,000 --> 00:07:45,990
Na aš turiu dabar mano
rūšiavimas kairiojo pusmetį kairėje.

167
00:07:45,990 --> 00:07:47,720
Vėlgi, galime atsukti tik už akimirką.

168
00:07:47,720 --> 00:07:51,010
Jei Pseudocode tai,
ir aš suteiktas aštuonių elementų,

169
00:07:51,010 --> 00:07:53,230
8 yra akivaizdžiai didesnis
nei arba lygus 2.

170
00:07:53,230 --> 00:07:54,980
Taigi su pirmas atvejis netaikomas.

171
00:07:54,980 --> 00:07:58,120
Taigi rūšiuoti aštuonis elementus, aš pirmą kartą
rūšiuoti kairįjį pusę elementų,

172
00:07:58,120 --> 00:08:01,930
tada aš rūšiuoti tinkamą pusę, tada aš sujungti
du rūšiuotos pusės, kiekvienas iš dydis 4.

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

174
00:08:02,470 --> 00:08:07,480
>> Bet jei jūs tiesiog man pasakė, rūšiuoti
kairėje pusėje,, kuris yra dabar dydžio 4,

175
00:08:07,480 --> 00:08:09,350
Kaip rūšiuoti kairįjį pusę?

176
00:08:09,350 --> 00:08:11,430
Na, jei aš turėti
įėjimas iš keturių elementų,

177
00:08:11,430 --> 00:08:14,590
Aš rikiuoti į kairę
du, tada dešiniuoju du,

178
00:08:14,590 --> 00:08:16,210
ir tada aš juos sujungti kartu.

179
00:08:16,210 --> 00:08:18,700
Taigi dar kartą, ji tampa šiek tiek
iš proto lenkimo žaidimą čia

180
00:08:18,700 --> 00:08:21,450
nes jūs, tipo, turi
prisiminti, kur jūs esate į istoriją,

181
00:08:21,450 --> 00:08:23,620
bet tuo dienos pabaigoje,
suteiktas joks elementų skaičių,

182
00:08:23,620 --> 00:08:25,620
pirmiausia noriu rūšiuoti
kairė pusė, tada į dešinę pusę,

183
00:08:25,620 --> 00:08:26,661
tada sujungti juos kartu.

184
00:08:26,661 --> 00:08:28,630
Pradėkime daryti būtent tai.

185
00:08:28,630 --> 00:08:30,170
Štai aštuoni elementų įvestis.

186
00:08:30,170 --> 00:08:31,910
Dabar mes ieškome kairėje pusėje čia.

187
00:08:31,910 --> 00:08:33,720
Kaip rūšiuoti keturis elementus?

188
00:08:33,720 --> 00:08:35,610
Na aš rikiuoti yra kairėje pusėje.

189
00:08:35,610 --> 00:08:37,720
Dabar kaip man sutvarkyti kairįjį pusę?

190
00:08:37,720 --> 00:08:39,419
Na aš buvo suteikta du elementus.

191
00:08:39,419 --> 00:08:41,240
Taigi leiskite surūšiuoti šių dviejų elementų.

192
00:08:41,240 --> 00:08:44,540
2 yra didesnis arba
lygus 2, žinoma.

193
00:08:44,540 --> 00:08:46,170
Taigi, kad pirmas atvejis netaikomas.

194
00:08:46,170 --> 00:08:49,010
>> Taigi dabar aš turiu rūšiuoti į kairę
pusė šių dviejų elementų.

195
00:08:49,010 --> 00:08:50,870
Kairėje pusė, žinoma, yra tik 4.

196
00:08:50,870 --> 00:08:54,020
Taigi, kaip man sutvarkyti iš vieno elemento sąrašą?

197
00:08:54,020 --> 00:08:57,960
Na, dabar, kad ypatingas bazinį scenarijų
iki viršaus, taip sakant, taikoma.

198
00:08:57,960 --> 00:09:01,470
1 yra mažiau nei 2, ir savo
sąrašas yra iš tiesų dydžio 1 d.

199
00:09:01,470 --> 00:09:02,747
Taigi aš tiesiog grįžti.

200
00:09:02,747 --> 00:09:03,580
Aš nieko negaliu daryti.

201
00:09:03,580 --> 00:09:06,770
Ir iš tiesų, pažvelgti, ką aš
padaryta, 4 jau rūšiuojamos.

202
00:09:06,770 --> 00:09:09,220
Kaip jau esu
dalinai sėkmingas čia.

203
00:09:09,220 --> 00:09:11,750
>> Dabar, atrodo rūšies kvailas
reikalauti, bet tai tiesa.

204
00:09:11,750 --> 00:09:13,700
4 yra 1 dydžio sąrašas.

205
00:09:13,700 --> 00:09:15,090
Tai jau rūšiuojamos.

206
00:09:15,090 --> 00:09:16,270
Štai kairė pusė.

207
00:09:16,270 --> 00:09:18,010
Dabar aš rūšiuoti tinkamą pusę.

208
00:09:18,010 --> 00:09:22,310
Mano indėlis yra vienas elementas, 8
Be to, jau rūšiuojamos.

209
00:09:22,310 --> 00:09:25,170
Kvailas, taip pat, tačiau ir vėl,
Šis pagrindinis principas

210
00:09:25,170 --> 00:09:28,310
ketina leisti mums dabar statyti
ant sėkmingai tai.

211
00:09:28,310 --> 00:09:32,260
4 rūšiuojamos, 8 rūšiuojamos, o dabar
kas buvo, kad paskutinis žingsnis?

212
00:09:32,260 --> 00:09:35,330
Taigi, trečiasis ir paskutinis žingsnis, bet kokia
kartą jūs rūšiavimo sąrašas, prisiminti,

213
00:09:35,330 --> 00:09:38,310
buvo sujungti dvi puses,
kairėje ir dešinėje.

214
00:09:38,310 --> 00:09:39,900
Taigi darykime būtent tai.

215
00:09:39,900 --> 00:09:41,940
Mano kairė pusė, žinoma, 4.

216
00:09:41,940 --> 00:09:43,310
Mano teisė pusė yra 8.

217
00:09:43,310 --> 00:09:44,100
>> Taigi leiskite tai padaryti.

218
00:09:44,100 --> 00:09:46,410
Pirmiausia aš ruošiuosi skirti
Kai kurios papildomos atminties,

219
00:09:46,410 --> 00:09:48,680
kad aš atstovauti čia
kaip tik antrinis masyvas,

220
00:09:48,680 --> 00:09:49,660
tai pakankamai didelis, kad tilptų tai.

221
00:09:49,660 --> 00:09:52,243
Bet jūs galite įsivaizduoti, išplečiant
kad stačiakampis visas ilgis,

222
00:09:52,243 --> 00:09:53,290
jei mums reikia daugiau vėliau.

223
00:09:53,290 --> 00:09:58,440
Kaip man imtis 4 ir 8, ir sujungti
šie du sąrašai dydis 1 kartu?

224
00:09:58,440 --> 00:10:00,270
Čia taip pat gana paprasta.

225
00:10:00,270 --> 00:10:03,300
4 ateina pirmas, tada ateina 8.

226
00:10:03,300 --> 00:10:07,130
Nes jei aš noriu rūšiuoti
kairė pusė, tada į dešinę pusę,

227
00:10:07,130 --> 00:10:09,900
ir tada sujungti šias dvi puses
kartu, išrūšiuotų tam,

228
00:10:09,900 --> 00:10:11,940
4 ateina pirmas, tada ateina 8.

229
00:10:11,940 --> 00:10:15,810
>> Taigi, mes, atrodo, daro pažangą, net
nors aš nepadariau jokio faktinio darbą.

230
00:10:15,810 --> 00:10:17,800
Bet atsiminkite, kur mes esame į istoriją.

231
00:10:17,800 --> 00:10:19,360
Mes iš pradžių priėmė aštuonis elementus.

232
00:10:19,360 --> 00:10:21,480
Mes rūšiuojami kairįjį pusę, kuri yra 4.

233
00:10:21,480 --> 00:10:24,450
Tada mes rūšiuojami kairįjį pusę
kairiojo pusėje, kuri buvo 2.

234
00:10:24,450 --> 00:10:25,270
Ir čia mes einame.

235
00:10:25,270 --> 00:10:26,920
Mes padaryti su tuo žingsnio.

236
00:10:26,920 --> 00:10:29,930
>> Taigi, jei mes surūšiuoti
į kairę pusę 2, dabar mes

237
00:10:29,930 --> 00:10:32,130
turi rūšiuoti tinkamą pusę 2.

238
00:10:32,130 --> 00:10:35,710
Taigi teisė pusė 2
šių dviejų verčių čia, 6 ir 2.

239
00:10:35,710 --> 00:10:40,620
Tad dabar pats imtis iš dydžio indėlį
2, ir rūšiuoti kairįjį pusę, ir tada

240
00:10:40,620 --> 00:10:42,610
teisę pusę, ir tada
sujungti juos kartu.

241
00:10:42,610 --> 00:10:45,722
Na kaip man sutvarkyti iš dydį sąrašą
1, kurių sudėtyje yra tik skaičių 6?

242
00:10:45,722 --> 00:10:46,430
Aš jau padaryta.

243
00:10:46,430 --> 00:10:48,680
Šis dydis 1 sąrašas surūšiuotas.

244
00:10:48,680 --> 00:10:52,140
>> Kaip rūšiuoti kitą sąrašą
dydis 1, vadinamoji teisė pusę.

245
00:10:52,140 --> 00:10:54,690
Na tai irgi jau rūšiuojamos.

246
00:10:54,690 --> 00:10:56,190
Skaičius 2 yra vieni.

247
00:10:56,190 --> 00:11:00,160
Taigi dabar turiu dvi dalis, į kairę ir
Gerai, man reikia jas sujungti kartu.

248
00:11:00,160 --> 00:11:01,800
Leiskite man duoti sau šiek tiek papildomos erdvės.

249
00:11:01,800 --> 00:11:05,580
Ir 2 įdėti ten,
tada 6 ten, taip

250
00:11:05,580 --> 00:11:10,740
rūšiavimas šį sąrašą, į kairę ir į dešinę,
ir sujungiant jį kartu, galiausiai.

251
00:11:10,740 --> 00:11:12,160
Taigi, aš šiek tiek geresnės formos.

252
00:11:12,160 --> 00:11:16,250
Aš ne padaryta, nes aiškiai 4, 8, 2,
6 nėra galutinė užsakymas, kad aš noriu.

253
00:11:16,250 --> 00:11:20,640
Bet dabar aš turiu du sąrašus 2 dydžio, kad
tiek, atitinkamai, rūšiuojami.

254
00:11:20,640 --> 00:11:24,580
Taigi dabar, jei atsukti savo proto
akių, kur gi, kad palieka mus?

255
00:11:24,580 --> 00:11:28,520
Aš pradėjau su aštuonių elementų, tada aš
sutrumpino jį žemyn į kairę pusę 4,

256
00:11:28,520 --> 00:11:31,386
tada kairėje pusėje, 2, ir
tada į dešinę pusę 2,

257
00:11:31,386 --> 00:11:34,510
Aš baigiau todėl, rūšiavimas į kairę
pusė 2, ir teisę pusė 2,

258
00:11:34,510 --> 00:11:37,800
Taigi, kas yra trečiasis ir paskutinis žingsnis čia?

259
00:11:37,800 --> 00:11:41,290
Turiu sujungti kartu
du sąrašus 2 dydžio.

260
00:11:41,290 --> 00:11:42,040
Taigi eikime į priekį.

261
00:11:42,040 --> 00:11:43,940
Ir ekrane čia parašęs
man kai papildoma atmintis,

262
00:11:43,940 --> 00:11:47,170
nors techniškai, pastebėsite, kad aš
turiu visa krūva tuščioje vietoje iki viršaus

263
00:11:47,170 --> 00:11:47,670
ten.

264
00:11:47,670 --> 00:11:50,044
Jei aš noriu būti ypač
efektyvus plotas išmintingi,

265
00:11:50,044 --> 00:11:52,960
Galėčiau tik pradėti judėti elementai
pirmyn ir atgal, viršuje ir apačioje.

266
00:11:52,960 --> 00:11:55,460
Bet tik vizualiai aiškumo,
Aš ruošiuosi įdėti jį žemyn žemiau,

267
00:11:55,460 --> 00:11:56,800
išlaikyti dalykų gražus ir švarus.

268
00:11:56,800 --> 00:11:58,150
>> Taigi aš turiu du sąrašus 2 dydžio.

269
00:11:58,150 --> 00:11:59,770
Pirmasis sąraše yra 4 ir 8.

270
00:11:59,770 --> 00:12:01,500
Antrasis sąraše yra 2 ir 6.

271
00:12:01,500 --> 00:12:03,950
Leiskite sujungti tuos
kartu rūšiuotų tvarka.

272
00:12:03,950 --> 00:12:09,910
2, žinoma, ateina pirma,
tada 4, tada 6, tada 8.

273
00:12:09,910 --> 00:12:12,560
Ir dabar mes, atrodo, vis
kažkur įdomu.

274
00:12:12,560 --> 00:12:15,720
Dabar aš rūšiuojami pusė
sąrašą ir atsitiktinai, tai

275
00:12:15,720 --> 00:12:18,650
visi net numeriai, bet
yra, tiesą sakant, tik sutapimas.

276
00:12:18,650 --> 00:12:22,220
Ir dabar aš turiu rūšiuojami į kairę
pusė, taip, kad ji yra 2, 4, 6, ir 8.

277
00:12:22,220 --> 00:12:23,430
Nieko tai iš eilės.

278
00:12:23,430 --> 00:12:24,620
Tai jaučiasi pažangą.

279
00:12:24,620 --> 00:12:26,650
>> Dabar jis jaučiasi aš
buvo kalbama amžinai dabar

280
00:12:26,650 --> 00:12:29,850
Taigi, kas dar turi būti peržiūrėta, jei tai
algoritmas yra, iš tiesų, efektyviau.

281
00:12:29,850 --> 00:12:31,766
Bet mes išgyvena
super metodiškai.

282
00:12:31,766 --> 00:12:34,060
Kompiuteris, žinoma,
norėčiau tai padaryti, kaip kad.

283
00:12:34,060 --> 00:12:34,840
Taigi, kur mes esame?

284
00:12:34,840 --> 00:12:36,180
Mes pradėjome su aštuonių elementų.

285
00:12:36,180 --> 00:12:37,840
Aš rūšiuojami kairėje pusėje, 4.

286
00:12:37,840 --> 00:12:39,290
Man atrodo, kad reikia padaryti, kad.

287
00:12:39,290 --> 00:12:42,535
Taigi, dabar kitas žingsnis yra
rūšiuoti tinkamą pusę 4.

288
00:12:42,535 --> 00:12:44,410
Ir ši dalis mes galime eiti
per šiek tiek daugiau

289
00:12:44,410 --> 00:12:47,140
greitai, nors esate
Sveiki atsukti arba sustabdyti, tiesiog

290
00:12:47,140 --> 00:12:49,910
manau, per jį
savo tempu, bet ką

291
00:12:49,910 --> 00:12:53,290
mes turime dabar yra galimybė
padaryti tą patį algoritmą keturiais

292
00:12:53,290 --> 00:12:54,380
su skirtingais numeriais.

293
00:12:54,380 --> 00:12:57,740
>> Taigi eikime į priekį, ir sutelkti dėmesį į
teisė pusė, kurią mes čia.

294
00:12:57,740 --> 00:13:01,260
Kairėje pusėje, kad
teisė pusę, o dabar

295
00:13:01,260 --> 00:13:04,560
kairėje pusėje, kairėje
pusė šios teisės pusę,

296
00:13:04,560 --> 00:13:08,030
ir kaip man sutvarkyti iš dydį sąrašą
1, kuriame yra tik 1 numeriu?

297
00:13:08,030 --> 00:13:09,030
Tai jau padaryta.

298
00:13:09,030 --> 00:13:11,830
Kaip aš galiu padaryti dėl sąrašo pats
dydžio 1, kuriame yra tik 7?

299
00:13:11,830 --> 00:13:12,840
Tai jau padaryta.

300
00:13:12,840 --> 00:13:16,790
Trečias žingsnis šiam pusę tada
yra sujungti šiuos du elementus

301
00:13:16,790 --> 00:13:20,889
į naują sąrašo 2 dydžio, 1 ir 7.

302
00:13:20,889 --> 00:13:23,180
Ar neatrodo, kad padarėme viską
kad daug įdomus darbas.

303
00:13:23,180 --> 00:13:24,346
Pažiūrėkime, kas vyksta šalia.

304
00:13:24,346 --> 00:13:29,210
Aš tik sutvarkyti kairįjį pusę
teisė pusė mano originalus indėlis.

305
00:13:29,210 --> 00:13:32,360
Dabar galime rūšiuoti teisę
pusė, kuri yra 5 ir 3.

306
00:13:32,360 --> 00:13:35,740
Leiskite dar kartą pažvelgti į kairę
pusę, rūšiuojami, teisė pusę, rūšiuojami,

307
00:13:35,740 --> 00:13:39,120
ir sujungti tuos du kartu,
į tam tikrą papildomą erdvę,

308
00:13:39,120 --> 00:13:41,670
3 ateina pirmas, tada ateina 5.

309
00:13:41,670 --> 00:13:46,190
Ir todėl dabar, mes surūšiuoti
kairėje pusėje, dešinės pusėje

310
00:13:46,190 --> 00:13:49,420
pirminio problemą, ir
teisę pusė dešinės pusėje

311
00:13:49,420 --> 00:13:50,800
pirminio problemą.

312
00:13:50,800 --> 00:13:52,480
Kas trečias ir paskutinis žingsnis?

313
00:13:52,480 --> 00:13:54,854
Na sujungti šias dvi puses kartu.

314
00:13:54,854 --> 00:13:57,020
Taigi leiskite man gauti sau kai
papildomos vietos, bet, vėlgi, aš

315
00:13:57,020 --> 00:13:58,699
gali būti naudoti, kad atsarginį kosmoso iki viršaus.

316
00:13:58,699 --> 00:14:00,490
Tačiau mes ketiname išlaikyti
paprasta vizualiai.

317
00:14:00,490 --> 00:14:07,070
Leiskite sujungti dabar 1 ir
tada 3, ir tada 5, ir tada 7.

318
00:14:07,070 --> 00:14:10,740
Paliekant man dabar su
teisė pusė originalo problemos

319
00:14:10,740 --> 00:14:12,840
kad manimi puikiai rūšiuojami.

320
00:14:12,840 --> 00:14:13,662
>> Taigi, kas lieka?

321
00:14:13,662 --> 00:14:16,120
Aš jaučiuosi kaip aš nuolat sakydamas, kad
tie patys dalykai vėl, ir vėl,

322
00:14:16,120 --> 00:14:18,700
bet tai neparodo
Faktas, kad mes naudojame rekursija.

323
00:14:18,700 --> 00:14:21,050
Iš naudojate procesas
algoritmas vėl, ir vėl,

324
00:14:21,050 --> 00:14:23,940
mažesnių pogrupių
originalus problema.

325
00:14:23,940 --> 00:14:27,580
Taigi dabar aš turiu iš kairės rūšiuojami
pusė pradinio problemą.

326
00:14:27,580 --> 00:14:30,847
Turiu teisę rūšiuotą pusę
pirminio problemą.

327
00:14:30,847 --> 00:14:32,180
Kas trečias ir paskutinis žingsnis?

328
00:14:32,180 --> 00:14:33,590
Oi, tai sujungti.

329
00:14:33,590 --> 00:14:34,480
Taigi leiskite tai padaryti.

330
00:14:34,480 --> 00:14:36,420
Leiskite skirti kai papildoma
atminties, bet mano Dieve, mes

331
00:14:36,420 --> 00:14:37,503
gali jį visur dabar.

332
00:14:37,503 --> 00:14:40,356
Mes turime tiek daug laisvos vietos
pas mus, bet mes keep it simple.

333
00:14:40,356 --> 00:14:42,730
Vietoj grįžta ir
atgal su mūsų originalios atminties,

334
00:14:42,730 --> 00:14:44,480
tegul tiesiog padaryk tai
vizualiai žemyn čia žemiau,

335
00:14:44,480 --> 00:14:47,240
baigti iki apjungiant
kairė pusė ir teisė pusę.

336
00:14:47,240 --> 00:14:49,279
>> Taigi sujungus, ką man reikia daryti?

337
00:14:49,279 --> 00:14:50,820
Noriu imtis elementus tvarka.

338
00:14:50,820 --> 00:14:53,230
Taigi žiūri kairėje pusėje,
Matau pirmas skaičius yra 2.

339
00:14:53,230 --> 00:14:55,230
Žiūriu dešinėje pusėje,
I žr pirmąjį skaičių

340
00:14:55,230 --> 00:14:58,290
yra 1, taigi akivaizdu, kad, kuri
Taškų aš noriu išplėšti,

341
00:14:58,290 --> 00:15:00,430
ir įdėti pirmasis mano galutinį sąrašą?

342
00:15:00,430 --> 00:15:01,449
Žinoma, 1.

343
00:15:01,449 --> 00:15:02,990
Dabar aš noriu paprašyti, kad tą patį klausimą.

344
00:15:02,990 --> 00:15:05,040
Kairėje pusėje, aš
vis dar turiu 2 numeriu.

345
00:15:05,040 --> 00:15:07,490
Dešinėje pusėje,
Aš turiu 3 numeriu.

346
00:15:07,490 --> 00:15:08,930
Kuris aš noriu pasirinkti?

347
00:15:08,930 --> 00:15:11,760
Žinoma, numeris 2
dabar pastebėti kandidatus

348
00:15:11,760 --> 00:15:13,620
yra 4 kairėje, 3 dešinėje.

349
00:15:13,620 --> 00:15:15,020
Leiskite, žinoma, pasirinkti 3.

350
00:15:15,020 --> 00:15:18,020
Dabar kandidatai yra 4 dėl
kairysis, 5 dešinėje.

351
00:15:18,020 --> 00:15:19,460
Mes, žinoma, pasirinkti 4.

352
00:15:19,460 --> 00:15:21,240
6 kairėje, 5 dešinėje.

353
00:15:21,240 --> 00:15:22,730
Mes, žinoma, pasirinkti 5.

354
00:15:22,730 --> 00:15:25,020
6 kairėje, 7 dešinėje.

355
00:15:25,020 --> 00:15:29,320
Renkamės 6, ir tada mes
pasirinkti 7, ir tada mes renkamės 8.

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

357
00:15:30,100 --> 00:15:34,370
>> Taigi didžiulis skaičius tariant vėliau, mes
surūšiuoti šį aštuonių elementų sąrašą

358
00:15:34,370 --> 00:15:38,450
į vieną sąrašą per aštuonių,
kad manimi didėja su kiekvienu žingsniu,

359
00:15:38,450 --> 00:15:40,850
bet kiek laiko darė
tai užtruks mums tai padaryti.

360
00:15:40,850 --> 00:15:43,190
Na aš sąmoningai
laid dalykų iš pavaizduotomis piktogramo-

361
00:15:43,190 --> 00:15:46,330
čia, kad galėtume rūšies
matyti ar vertiname padalinį

362
00:15:46,330 --> 00:15:49,060
užkariauti kad buvo vyksta.

363
00:15:49,060 --> 00:15:52,830
>> Iš tiesų, jei jūs atsigręžti į tinklą,
Aš paliktas visų šių punktyrinėmis linijomis

364
00:15:52,830 --> 00:15:55,660
įdiegtos turėtojų, galite,
rūšies, žr atvirkštine tvarka,

365
00:15:55,660 --> 00:15:58,800
jei rūšies atsigręžti į
istorija, dabar, mano originalus sąrašas

366
00:15:58,800 --> 00:16:00,250
yra, žinoma, dydžio 8 d.

367
00:16:00,250 --> 00:16:03,480
Ir tada anksčiau buvau
susiduriame su dviem sąrašus dydis 4,

368
00:16:03,480 --> 00:16:08,400
ir tada keturi sąrašai dydis 2,
ir tada aštuoni sąrašai dydis 1 d.

369
00:16:08,400 --> 00:16:10,151
>> Taigi, kas tai daro,
rūšies, priminti jums?

370
00:16:10,151 --> 00:16:11,858
Na, iš tiesų, bet
algoritmai mes

371
00:16:11,858 --> 00:16:14,430
pažvelgė šiol, kur mes
skaldyk ir skaldyk ir atskirties,

372
00:16:14,430 --> 00:16:19,500
susilaukia dalykų ir vėl
vėl atsiranda šiame bendrą idėją.

373
00:16:19,500 --> 00:16:23,100
Ir taip yra kažkas
logaritminė vyksta čia.

374
00:16:23,100 --> 00:16:26,790
Ir tai ne visai žurnalas n, bet
ten logaritminis komponentas

375
00:16:26,790 --> 00:16:28,280
kas mes ką tik padaryti.

376
00:16:28,280 --> 00:16:31,570
>> Dabar aptarkime, kaip kad iš tikrųjų yra.

377
00:16:31,570 --> 00:16:34,481
Taigi prisijunkite n, vėl buvo
puikus veikimo laikas,

378
00:16:34,481 --> 00:16:36,980
kai mes padarėme kažką panašaus
dvejetainis paieškos, kaip mes dabar vadiname,

379
00:16:36,980 --> 00:16:40,090
skaldyk ir valdyk strategija
per kurį mes nustatėme, Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Dabar techniškai.

381
00:16:41,020 --> 00:16:43,640
Štai žurnalas bazė 2 n, net
nors daugeliu matematikos klases,

382
00:16:43,640 --> 00:16:45,770
10 dažniausiai bazinė kad jūs prisiimate.

383
00:16:45,770 --> 00:16:48,940
Bet kompiuterių mokslininkai beveik visada
galvoti ir kalbėti Kalbant apie pagrindą 2,

384
00:16:48,940 --> 00:16:52,569
todėl mes paprastai tiesiog pasakyti žurnalą
n, o ne log bazės 2 n,

385
00:16:52,569 --> 00:16:55,110
bet jie tiksliai vieną ir tą
pats į kompiuterį pasaulyje

386
00:16:55,110 --> 00:16:57,234
Mokslas ir kaip panaikinti,
ten pastovus veiksnys

387
00:16:57,234 --> 00:17:01,070
skirtumas tarp šių dviejų, todėl
inscenizacijos vistiek, daugiau formalių priežasčių.

388
00:17:01,070 --> 00:17:04,520
>> Bet dabar, kas mums rūpi
apie tai pavyzdys.

389
00:17:04,520 --> 00:17:08,520
Taigi tegul ne įrodyti, pavyzdžiui, bet ne
mažiau naudoti iš numerių pavyzdį

390
00:17:08,520 --> 00:17:10,730
po ranka kaip normalumas patikrinti, jei bus.

391
00:17:10,730 --> 00:17:14,510
Taigi anksčiau formulė buvo Prisijungti bazė
2 n, bet tai, kas yra n ir šiuo atveju.

392
00:17:14,510 --> 00:17:18,526
Aš turėjau n originalius numerius arba 8
originalaus skaičius specialiai.

393
00:17:18,526 --> 00:17:20,359
Dabar ji buvo šiek tiek
o, bet aš esu gana

394
00:17:20,359 --> 00:17:25,300
Įsitikinkite, kad žurnalas bazė 2
iš vertės 8 yra 3,

395
00:17:25,300 --> 00:17:29,630
Ir iš tiesų, kas malonu apie tai
kad 3 yra tiksliai kartų

396
00:17:29,630 --> 00:17:33,320
kad jūs galite padalinti sąrašą
Ilgio 8 vėl, ir vėl,

397
00:17:33,320 --> 00:17:36,160
ir vėl, kol jūs liekate
sąrašus tik 1 dydžio.

398
00:17:36,160 --> 00:17:36,660
Teisė?

399
00:17:36,660 --> 00:17:40,790
8 eina iki 4, eina iki 2,
eina iki 1, ir kad tai

400
00:17:40,790 --> 00:17:43,470
atspindi būtent tai
nuotrauka mes turėjome vos prieš akimirką.

401
00:17:43,470 --> 00:17:47,160
Taigi šiek tiek normalumas patikrinti, kur
logaritmas yra faktiškai dalyvauja.

402
00:17:47,160 --> 00:17:50,180
>> Taigi, dabar, ką dar dalyvauja čia? n.

403
00:17:50,180 --> 00:17:53,440
Taigi pastebėti, kad kiekvienas
kartą aš padalinti sąrašą

404
00:17:53,440 --> 00:17:58,260
nors atvirkštine tvarka istorijos
čia, aš vis dar daro n dalykų.

405
00:17:58,260 --> 00:18:02,320
Tai sujungimo žingsnis reikalaujama, kad
Liečiu kiekvieną numerių vieną,

406
00:18:02,320 --> 00:18:05,060
tam, kad jį į skaidrių
prireikus jo vieta.

407
00:18:05,060 --> 00:18:10,760
Taigi, nors šis aukštis
schema yra matmenų dalelių log n n arba 3,

408
00:18:10,760 --> 00:18:13,860
Konkrečiau, kitaip tariant,
Aš tris padalinius čia.

409
00:18:13,860 --> 00:18:18,800
Kiek darbo aš padaryti horizontaliai
kartu šios diagramos kiekvieną kartą?

410
00:18:18,800 --> 00:18:21,110
>> Na, aš n žingsnių
dirbti, nes jei aš

411
00:18:21,110 --> 00:18:24,080
gavo keturis elementus ir keturis elementus,
ir man reikia jas sujungti kartu.

412
00:18:24,080 --> 00:18:26,040
Man reikia eiti per
Šie keturi ir jie keturi,

413
00:18:26,040 --> 00:18:28,123
galiausiai sujungti jas
Atgal į aštuonias elementais.

414
00:18:28,123 --> 00:18:32,182
Jei atvirkščiai, aš turiu aštuonis pirštus
Čionai, kurį aš ne, ir aštuonios

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- Jei aš
gavo keturis pirštus per čia

416
00:18:34,390 --> 00:18:37,380
kuri man daryti, keturi pirštai
Čionai, kuris man daryti,

417
00:18:37,380 --> 00:18:40,590
tada, kad tas pats
pavyzdys, kaip ir anksčiau, jei aš

418
00:18:40,590 --> 00:18:44,010
turi aštuonis pirštus nors
iš viso, kurį galiu, rūšies, daryti.

419
00:18:44,010 --> 00:18:47,950
Galiu tiksliai padaryti čia
tada aš tikrai gali

420
00:18:47,950 --> 00:18:50,370
sujungti visus šiuos sąrašus
dydžio 1 kartu.

421
00:18:50,370 --> 00:18:54,050
Bet aš tikrai turime ieškoti
kiekvieno elemento tik vieną kartą.

422
00:18:54,050 --> 00:18:59,640
Taigi, šio proceso aukštis yra log n,
Šio proceso plotis, taip sakant,

423
00:18:59,640 --> 00:19:02,490
yra n, tai, ką mes, atrodo,
turėti, galiausiai, yra

424
00:19:02,490 --> 00:19:06,470
bėgimo laikas dydžio n kartų log n.

425
00:19:06,470 --> 00:19:08,977
>> Kitaip tariant, mes padalintas
sąrašas, žurnalas n kartų,

426
00:19:08,977 --> 00:19:11,810
bet kiekvieną kartą mes padarėme, kad mes turėjome
paliesti kiekvieną iš elementų vieną

427
00:19:11,810 --> 00:19:13,560
siekiant sujungti juos
visi kartu, kuris

428
00:19:13,560 --> 00:19:18,120
buvo n žingsnis, todėl mes turime n kartų log n,
arba kaip kompiuteris mokslininkas pasakytų,

429
00:19:18,120 --> 00:19:20,380
asimptotiškai, kuris
Būtų didelis žodis

430
00:19:20,380 --> 00:19:22,810
apibūdinti viršutinė
laikytis ant važiavimo laikas,

431
00:19:22,810 --> 00:19:28,010
mes veikia dideliame o
Rąstų n metu, taip sakant.

432
00:19:28,010 --> 00:19:31,510
>> Dabar tai yra reikšminga, nes
prisiminti ką veikia laikai buvo

433
00:19:31,510 --> 00:19:34,120
su burbulas rūšiuoti, ir atrankos
Rūšiuoti ir įterpimo rūšiuoti,

434
00:19:34,120 --> 00:19:38,200
ir net keli kiti, kurie egzistuoja,
n kvadratu buvo, kai mes buvome.

435
00:19:38,200 --> 00:19:39,990
Ir jūs galite, rūšies, pamatyti tai čia.

436
00:19:39,990 --> 00:19:45,720
Jei n kvadratu yra akivaizdžiai n kartų
N, bet čia mes turime n kartų log n,

437
00:19:45,720 --> 00:19:48,770
ir mes jau žinome iš savaitę
nuliui, kad žurnalas N, logaritminis,

438
00:19:48,770 --> 00:19:50,550
yra geriau nei kažkas tiesinis.

439
00:19:50,550 --> 00:19:52,930
Galų gale, prisiminti paveikslėlį
su raudona ir geltona

440
00:19:52,930 --> 00:19:56,500
ir žalios linijos, kad mes atskleidžianti, tuo
žalia logaritminė linija buvo daug mažesnis.

441
00:19:56,500 --> 00:20:00,920
Ir todėl, daug geriau ir greičiau
nei tiesios geltonos ir raudonos linijos,

442
00:20:00,920 --> 00:20:05,900
n kartų log n yra, tiesą sakant, geriau
nei n kartų, n, arba n kvadrato.

443
00:20:05,900 --> 00:20:09,110
>> Taigi, mes, atrodo,
nustatė algoritmą suliejimą

444
00:20:09,110 --> 00:20:11,870
Rūšiuoti kuri veikia daug
greičiau laikas, ir iš tiesų,

445
00:20:11,870 --> 00:20:16,560
Štai kodėl, anksčiau šią savaitę, kai
Mes matėme, kad tarp burbulas konkursas

446
00:20:16,560 --> 00:20:20,750
Rūšiuoti atranka rūšiuoti, ir sujungti
Rūšiuoti, sujungti rūšiuoti tikrai, tikrai laimėjo.

447
00:20:20,750 --> 00:20:23,660
Ir iš tiesų, mes net ne laukti
Kramtomoji rūšiuoti ir atrankos rūšiuoti

448
00:20:23,660 --> 00:20:24,790
pabaigti.

449
00:20:24,790 --> 00:20:27,410
>> Dabar galime imtis vieną kitą perdavimo
į tai, iš šiek tiek daugiau

450
00:20:27,410 --> 00:20:31,030
formalus požiūris, tik
atveju, tai rezonuoja geriau

451
00:20:31,030 --> 00:20:33,380
negu aukštesnio lygio diskusija.

452
00:20:33,380 --> 00:20:34,880
Taigi čia algoritmas dar kartą.

453
00:20:34,880 --> 00:20:36,770
Paklauskime savęs,
ką veikia laikas

454
00:20:36,770 --> 00:20:39,287
yra tai algoritmai įvairius veiksmus?

455
00:20:39,287 --> 00:20:41,620
Leiskite padalinti jį į pirmą
atveju ir antras atvejis.

456
00:20:41,620 --> 00:20:46,280
IF ir kitur IF atveju,
N yra mažiau nei 2, tiesiog grįžti.

457
00:20:46,280 --> 00:20:47,580
Jaučia pastovaus laiko.

458
00:20:47,580 --> 00:20:50,970
Tai, tipo, kaip ir dviejų pakopų,
N yra mažiau nei 2, tada grįžti.

459
00:20:50,970 --> 00:20:54,580
Bet kaip mes sakėme, pirmadienį,
pastovus laikas, arba didelis O 1,

460
00:20:54,580 --> 00:20:57,130
gali būti du žingsniai, trys
žingsniai, net 1000 žingsnių.

461
00:20:57,130 --> 00:20:59,870
Svarbu yra tai, kad
pastovus skaičius žingsnius.

462
00:20:59,870 --> 00:21:03,240
Taigi geltona pabrėžė Pseudocode
čia veikia, mes jį vadiname,

463
00:21:03,240 --> 00:21:04,490
pastovus laikas.

464
00:21:04,490 --> 00:21:06,780
Taigi daugiau formaliai, ir
mes ketiname to-- tai

465
00:21:06,780 --> 00:21:09,910
bus kiek mes
formalizuoti šią teisę now-- T n,

466
00:21:09,910 --> 00:21:15,030
važiavimo laikas problema
kad mano n septyniasdešimties kaip įvestį,

467
00:21:15,030 --> 00:21:19,150
lygus didelis O vienas,
N yra mažiau nei 2.

468
00:21:19,150 --> 00:21:20,640
Taigi, tai sąlyga, kad.

469
00:21:20,640 --> 00:21:24,150
Taigi, norint būti aišku, n yra mažiau nei
2, mes turime labai trumpą sąrašą, tada

470
00:21:24,150 --> 00:21:29,151
filmo laikas, "T" n, kur n yra
1 arba 0, tai labai konkrečiu atveju,

471
00:21:29,151 --> 00:21:30,650
tai tiesiog bus pastovus laikas.

472
00:21:30,650 --> 00:21:32,691
Ji ketina imtis vieną
dėti du žingsnius, nesvarbu.

473
00:21:32,691 --> 00:21:33,950
Tai fiksuotas skaičius žingsnius.

474
00:21:33,950 --> 00:21:38,840
>> Taigi sultinga dalis turi tikrai būti
kitas atvejis Pseudocode.

475
00:21:38,840 --> 00:21:40,220
Else atveju.

476
00:21:40,220 --> 00:21:44,870
Rūšiuoti kairė pusė elementų, rūšiuoti teisė
pusė elementų, sujungti surūšiuotas puses.

477
00:21:44,870 --> 00:21:46,800
Kiek kiekviena iš šių žingsnių imtis?

478
00:21:46,800 --> 00:21:49,780
Na, jei veikia
laikas rūšiuoti n elementų

479
00:21:49,780 --> 00:21:53,010
yra, tegul jį vadina labai
bendrine, T n,

480
00:21:53,010 --> 00:21:55,500
tada rūšiavimas į kairę
pusė iš elementų,

481
00:21:55,500 --> 00:21:59,720
yra, tipo, tarsi sakydamas,
T n skirstomos 2,

482
00:21:59,720 --> 00:22:03,000
ir panašiai rūšiavimo tinkamą pusę
elementų yra, tipo, tarsi sakydamas,

483
00:22:03,000 --> 00:22:06,974
T n padalintas 2, ir tada
Sujungiant surūšiuotus puses.

484
00:22:06,974 --> 00:22:08,890
Na, jei aš turiu kai
skaičius elementų čia

485
00:22:08,890 --> 00:22:11,230
kaip keturi, ir šiek tiek skaičių
elementų čia, kaip ir keturių,

486
00:22:11,230 --> 00:22:14,650
ir aš turiu sujungti kiekvieną iš šių keturių
į, ir kiekvienas iš jų keturi, vieną

487
00:22:14,650 --> 00:22:17,160
po kito, taip, kad
galiausiai turiu aštuonis elementus.

488
00:22:17,160 --> 00:22:20,230
Atrodo, kad tai didelis O n žingsnių?

489
00:22:20,230 --> 00:22:23,500
Jei aš turiu n pirštus ir kiekviena iš
jiems turi būti sujungtos į vietą,

490
00:22:23,500 --> 00:22:25,270
tai kaip dar n žingsnių.

491
00:22:25,270 --> 00:22:27,360
>> Taigi iš tiesų formulaically,
galime išreikšti tai,

492
00:22:27,360 --> 00:22:29,960
nors truputį scarily per pirmąjį
žvilgsnis, bet tai yra kažkas,

493
00:22:29,960 --> 00:22:31,600
kuri fiksuoja tiksliai tą logiką.

494
00:22:31,600 --> 00:22:35,710
Judamasis laikas, T n JEI N
yra didesnis arba lygus 2.

495
00:22:35,710 --> 00:22:42,500
Šiuo atveju, kad ELSE atveju, yra T n
padalintas iš 2, plius t n padalytą iš 2,

496
00:22:42,500 --> 00:22:45,320
plius Didelės O n, kai
linijinis pakopų skaičius,

497
00:22:45,320 --> 00:22:51,630
gal lygiai n, gal 2 kartus
N, bet tai maždaug, kad n.

498
00:22:51,630 --> 00:22:54,060
Taigi, kad per daug, tai, kaip mes galime
išreikšti tai formulaically.

499
00:22:54,060 --> 00:22:56,809
Dabar jūs nežinote, nebent
Jūs įrašyti jį į savo protą,

500
00:22:56,809 --> 00:22:58,710
ar ieškoti jį į
atgal vadovėlis, kad

501
00:22:58,710 --> 00:23:00,501
gali turėti šiek tiek
Cheat sheet pabaigoje

502
00:23:00,501 --> 00:23:03,940
bet tai, žinoma, ketina
Duok mums O n log n didelis,

503
00:23:03,940 --> 00:23:06,620
nes pasikartojimo, kad
jūs matote čia ekrane,

504
00:23:06,620 --> 00:23:09,550
jei iš tikrųjų jį, su
begalinis skaičius pavyzdžių,

505
00:23:09,550 --> 00:23:13,000
ar tu ją formulaically, darytumėte
matyti, kad tai, nes šią formulę

506
00:23:13,000 --> 00:23:17,100
savaime yra grįžtamojo su t
n per kažką dešinėje,

507
00:23:17,100 --> 00:23:21,680
ir t n kairės, tai gali
iš tikrųjų būti išreikštas, galiausiai,

508
00:23:21,680 --> 00:23:24,339
tokie dideli Go n log n.

509
00:23:24,339 --> 00:23:26,130
Jei nėra įsitikinęs, kad tai
gerai dabar, tik

510
00:23:26,130 --> 00:23:28,960
imtis tikėjimo, kad tai, tiesą sakant,
ką, kad pasikartos, veda į,

511
00:23:28,960 --> 00:23:31,780
tačiau tai yra tik šiek tiek daugiau
matematinis metodas ieškote

512
00:23:31,780 --> 00:23:36,520
tuo veikimo laikas merge rūšiuoti
remiantis jos Pseudocode vieni.

513
00:23:36,520 --> 00:23:39,030
>> Dabar galime imtis šiek tiek
gurkšnis iš visų, kad

514
00:23:39,030 --> 00:23:41,710
ir pažvelgti į išvaizdą
tikras buvęs senatorius, kuris

515
00:23:41,710 --> 00:23:44,260
gali atrodyti šiek tiek pažįstamas,
kuris atsisėdo su "Google" Eric

516
00:23:44,260 --> 00:23:48,410
Schmidt prieš kurį laiką, interviu
scenoje, priešais visa krūva

517
00:23:48,410 --> 00:23:53,710
žmonių, kalbėti apie galiausiai
tema, tai gana dabar pažįstamas.

518
00:23:53,710 --> 00:23:54,575
Leiskite pažvelgti.

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

520
00:24:01,020 --> 00:24:03,890
>> Ericas Schmidtas: Dabar senatorius,
esate čia Google,

521
00:24:03,890 --> 00:24:09,490
ir man patinka galvoti apie
Pirmininkaujanti kaip darbo interviu.

522
00:24:09,490 --> 00:24:11,712
Dabar sunku gauti darbą, kaip prezidentas.

523
00:24:11,712 --> 00:24:12,670
Prezidentas B. Obama: Dešiniuoju.

524
00:24:12,670 --> 00:24:13,940
Ericas Schmidtas: Ir jūs
ketina daryti [nesigirdi] dabar.

525
00:24:13,940 --> 00:24:15,523
Taip pat sunku gauti darbą "Google".

526
00:24:15,523 --> 00:24:17,700
Prezidentas B. Obama: Dešiniuoju.

527
00:24:17,700 --> 00:24:21,330
>> Ericas Schmidtas: "Mes turime klausimų,
ir mes prašome mūsų kandidatų klausimus,

528
00:24:21,330 --> 00:24:24,310
ir tai vienas iš Larry Schwimmer.

529
00:24:24,310 --> 00:24:25,890
>> Prezidentas B. Obama: "Gerai".

530
00:24:25,890 --> 00:24:27,005
>> Ericas Schmidtas: Kas?

531
00:24:27,005 --> 00:24:28,130
Jūs manote, aš nejuokauju?

532
00:24:28,130 --> 00:24:30,590
Tai čia.

533
00:24:30,590 --> 00:24:33,490
Kas yra efektyviausias būdas
rūšiuoti milijoną 32 bitų sveikųjų skaičių?

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

535
00:24:37,560 --> 00:24:38,979
>> Prezidentas B. Obama: Well--

536
00:24:38,979 --> 00:24:41,020
Ericas Schmidtas: Kartais
gal aš atsiprašau, maybe--

537
00:24:41,020 --> 00:24:42,750
Prezidentas B. Obama: Ne, ne,
ne, ne, ne, aš think--

538
00:24:42,750 --> 00:24:43,240
Ericas Schmidtas: Tai ne it--

539
00:24:43,240 --> 00:24:45,430
Prezidentas B. Obama: "Aš
manau, manau burbulas

540
00:24:45,430 --> 00:24:46,875
Rūšiuoti būtų neteisingas būdas eiti.

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

542
00:24:49,619 --> 00:24:50,535
Ericas Schmidtas: Nagi.

543
00:24:50,535 --> 00:24:52,200
Kas jam šį pasakė?

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

545
00:24:54,020 --> 00:24:55,590
Aš ne informatikos on--

546
00:24:55,590 --> 00:24:58,986
>> Prezidentas B. Obama: mes
gavo mūsų šnipai ten.

547
00:24:58,986 --> 00:24:59,860
PROFESORIUS: Visos dešinę.

548
00:24:59,860 --> 00:25:03,370
Palikime už mus dabar
Teorinis pasaulis algoritmai

549
00:25:03,370 --> 00:25:06,520
į asimptotinėje analizės
dalį, ir grįžti į kai kurias temas

550
00:25:06,520 --> 00:25:09,940
nuo nulio ir vieną savaitę, ir pradžios
pašalinti keletą mokymo ratus,

551
00:25:09,940 --> 00:25:10,450
jei bus.

552
00:25:10,450 --> 00:25:13,241
Taigi, kad jūs tikrai suprasti,
galiausiai iš žemės, kas

553
00:25:13,241 --> 00:25:16,805
vyksta po kapotu, kai jūs
rašyti, kaupti, ir vykdyti programas.

554
00:25:16,805 --> 00:25:19,680
Prisiminkite, ypač, kad tai buvo
pirmasis C programa, mes pažvelgė,

555
00:25:19,680 --> 00:25:22,840
kanoniniu, paprasta programa
nekaip, santykinai kalbant,

556
00:25:22,840 --> 00:25:24,620
kurioje jis spausdina, Hello World ".

557
00:25:24,620 --> 00:25:27,610
Ir prisiminti, kad pasakiau, kad procesas
kad kodo eina per

558
00:25:27,610 --> 00:25:28,430
yra būtent tai.

559
00:25:28,430 --> 00:25:31,180
Jūs imtis savo kodą, perduoti
tai per sudarytojas, kaip klingsėti,

560
00:25:31,180 --> 00:25:34,650
ir iš ateina objekto kodą, kad
gali atrodyti taip, nulių ir

561
00:25:34,650 --> 00:25:37,880
kad kompiuterio procesoriaus, centrinis
apdorojimo blokas arba smegenų,

562
00:25:37,880 --> 00:25:39,760
galiausiai supranta.

563
00:25:39,760 --> 00:25:42,460
>> Pasirodo, kad tai yra
tiek kaip supaprastinimas,

564
00:25:42,460 --> 00:25:44,480
kad mes dabar yra
pozicija erzinti išskyrus

565
00:25:44,480 --> 00:25:46,720
suprasti, kas iš tikrųjų buvo
vyksta po kapotu

566
00:25:46,720 --> 00:25:48,600
kiekvieną kartą paleidus
Klingsėti, arba apskritai,

567
00:25:48,600 --> 00:25:53,040
kiekvieną kartą jums padaryti programą,
naudojant Padaryti CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
Visų pirma, stuff like
tai visų pirma būtų sukuriami,

569
00:25:56,760 --> 00:25:58,684
kai pirmą kartą sudaryti savo programą.

570
00:25:58,684 --> 00:26:00,600
Kitaip tariant, kai jūs
imtis savo kodą

571
00:26:00,600 --> 00:26:04,390
ir kaupia jį, o kas pirmas
yra išvedamas pagal klingsėti

572
00:26:04,390 --> 00:26:06,370
yra kažkas žinomas kaip surinkimo kodą.

573
00:26:06,370 --> 00:26:08,990
Ir iš tiesų, atrodo lygiai taip pat kaip tai.

574
00:26:08,990 --> 00:26:11,170
>> Išbėgau komandą ne
komandinės eilutės anksčiau.

575
00:26:11,170 --> 00:26:16,260
Klingsėti Dash sostinės s hello.c,
ir tai sukūrė failą

576
00:26:16,260 --> 00:26:19,490
man vadinamų hello.s,
kurio viduje buvo lygiai

577
00:26:19,490 --> 00:26:22,290
Šie turinį ir šiek tiek daugiau
aukščiau, ir šiek tiek daugiau žemiau,

578
00:26:22,290 --> 00:26:25,080
bet aš įdėti Juiciest
informacijos rasite čia ekrane.

579
00:26:25,080 --> 00:26:29,190
Ir jei atidžiai, pamatysite
bent keli pažįstami raktažodžius.

580
00:26:29,190 --> 00:26:31,330
Mes turime Pagrindinis viršuje.

581
00:26:31,330 --> 00:26:35,140
Mes printf žemyn viduryje.

582
00:26:35,140 --> 00:26:38,670
Ir mes taip pat turime hello world
Backslash n citatos apačioje.

583
00:26:38,670 --> 00:26:42,450
>> Ir visa kita čia
yra labai žemo lygio instrukcijos

584
00:26:42,450 --> 00:26:45,500
kad kompiuterio procesorius supranta.

585
00:26:45,500 --> 00:26:50,090
CPU instrukcijos, kad juda atminties
aplink, kad apkrovos įsipareigojimų iš atminties,

586
00:26:50,090 --> 00:26:52,750
ir galiausiai, spausdinti
dalykų ekrane.

587
00:26:52,750 --> 00:26:56,780
Dabar, kas atsitinka, nors po
ši asamblėja kodas generuojamas?

588
00:26:56,780 --> 00:26:59,964
Galų gale, jūs, žinoma,
vis dar generuoja objekto kodą.

589
00:26:59,964 --> 00:27:02,630
Bet žingsniai, kurie turi tikrai
vyksta po kapotu

590
00:27:02,630 --> 00:27:04,180
atrodo šiek tiek daugiau, kaip šis.

591
00:27:04,180 --> 00:27:08,390
Šaltinis kodas tampa surinkimo kodas,
kuris tada tampa objekto kodas,

592
00:27:08,390 --> 00:27:11,930
ir rezoliucinė žodžiai čia yra, kad
kai jūs surinkti savo kodą,

593
00:27:11,930 --> 00:27:16,300
iš ateina surinkimo kodą ir
kai jūs surinkti savo surinkimo kodą

594
00:27:16,300 --> 00:27:17,800
iš ateina objekto kodą.

595
00:27:17,800 --> 00:27:20,360
>> Dabar klingsėti yra super sudėtingas,
tarsi sudarytojų daug,

596
00:27:20,360 --> 00:27:23,151
ir ji visus šiuos veiksmus
kartu, ir tai nereiškia, kad

597
00:27:23,151 --> 00:27:25,360
išvesties bet koks tarpinis
failai, jūs netgi galite pamatyti.

598
00:27:25,360 --> 00:27:28,400
Jis tiesiog kaupia daiktus,
kuris yra bendras terminas, kad

599
00:27:28,400 --> 00:27:30,000
apibūdina visą šį procesą.

600
00:27:30,000 --> 00:27:32,000
Bet jei jūs tikrai norite
būti ypač ten

601
00:27:32,000 --> 00:27:34,330
daug ten vyksta taip pat.

602
00:27:34,330 --> 00:27:38,860
>> Bet tegul taip pat mano, kad dabar, net
kad super paprasta programa, hello.c,

603
00:27:38,860 --> 00:27:40,540
vadinama funkcija.

604
00:27:40,540 --> 00:27:41,870
Ji paragino printf.

605
00:27:41,870 --> 00:27:46,900
Bet aš ne rašyti printf, tiesą sakant,
kuris ateina su C, taip sakant.

606
00:27:46,900 --> 00:27:51,139
Tai funkcija Prisiminkite, kad tai
paskelbta standartinio io.h, kuris

607
00:27:51,139 --> 00:27:53,180
yra antraštės failas, kuris
yra tema mes iš tikrųjų

608
00:27:53,180 --> 00:27:55,780
pasinerti į daugiau gylio prieš ilgas.

609
00:27:55,780 --> 00:27:58,000
Bet antraštės failas yra
paprastai lydi

610
00:27:58,000 --> 00:28:02,920
pagal kodą failą, kodo failą,
panašiai kaip egzistuoja standartinės io.h.

611
00:28:02,920 --> 00:28:05,930
>> Kažkada seniai, kažkas,
ar kažkam, taip pat rašė

612
00:28:05,930 --> 00:28:11,040
failas vadinamas standartiniu io.c, į
kurių faktinė apibrėžimai,

613
00:28:11,040 --> 00:28:15,220
arba realizacijos printf,
ir kekių kitų funkcijų,

614
00:28:15,220 --> 00:28:16,870
iš tikrųjų yra parašyta.

615
00:28:16,870 --> 00:28:22,140
Taigi atsižvelgiant į tai, jei mes manome, turintys
čia kairėje, hello.c, kad kai

616
00:28:22,140 --> 00:28:26,250
parengta, suteikia mums hello.s, net jei
Klingsėti nesivargina taupymo vietoje

617
00:28:26,250 --> 00:28:31,360
galime matyti, ir kad surinkimo kodas
gauna surinkti į hello.o, kuris

618
00:28:31,360 --> 00:28:34,630
yra, iš tiesų, numatytasis pavadinimas
teikiama, kai jūs surinkti šaltinį

619
00:28:34,630 --> 00:28:39,350
kodą į objektiniu kodu, bet nėra
visai pasirengę jį vykdyti dar,

620
00:28:39,350 --> 00:28:41,460
nes dar vienas žingsnis
turi atsitikti, ir turi

621
00:28:41,460 --> 00:28:44,440
buvo daroma per pastaruosius keletą
savaites, galbūt nežinant jums.

622
00:28:44,440 --> 00:28:47,290
>> Tiksliau kažkur
į CS50 IDE, ir tai,

623
00:28:47,290 --> 00:28:49,870
taip pat, bus kraštui tiek
supaprastinimas akimirką,

624
00:28:49,870 --> 00:28:54,670
yra arba buvo ant metu,
failas vadinamas standartiniu io.c,

625
00:28:54,670 --> 00:28:58,440
kad kažkas surinkti į
standartiniai io.s arba lygiaverčiai,

626
00:28:58,440 --> 00:29:02,010
kad kažkas tada surinkti
į standartinį io.o,

627
00:29:02,010 --> 00:29:04,600
arba paaiškėja iš jo
šiek tiek skiriasi failą

628
00:29:04,600 --> 00:29:07,220
formatas, kuris gali turėti skirtingas
Rinkmenos plėtinys apskritai,

629
00:29:07,220 --> 00:29:11,720
bet teoriškai ir konceptualiai, tiksliai
tie žingsniai turėjo įvykti tam tikra forma.

630
00:29:11,720 --> 00:29:14,060
Kuris yra pasakyti, kad dabar
kai aš rašau programą,

631
00:29:14,060 --> 00:29:17,870
hello.c, kad tiesiog sako, hello world,
ir aš naudoju kažkieno kodą

632
00:29:17,870 --> 00:29:22,480
kaip printf, kuris buvo kadaise
laikas, faile vadinamas standartinis io.c,

633
00:29:22,480 --> 00:29:26,390
tada kažkaip turiu imtis savo
objekto kodas, mano nulių ir,

634
00:29:26,390 --> 00:29:29,260
ir kad asmens objektas
kodą arba nulių ir,

635
00:29:29,260 --> 00:29:34,970
ir kažkaip susieti juos kartu į
Vienas galutinis failas, vadinamas labas, kad

636
00:29:34,970 --> 00:29:38,070
turi visas nulio ir
tie iš mano pagrindinės funkcijos,

637
00:29:38,070 --> 00:29:40,830
ir visi nulio
ir tie, printf.

638
00:29:40,830 --> 00:29:44,900
>> Ir iš tiesų, tai paskutinis procesas
vadinamas, susiejimas savo objektą kodą.

639
00:29:44,900 --> 00:29:47,490
Įtaisas, kurio išėjimas
yra vykdomąjį failą.

640
00:29:47,490 --> 00:29:49,780
Taigi sąžiningumo, ne
pabaigoje dieną, nieko

641
00:29:49,780 --> 00:29:52,660
pasikeitė nuo savaitės viena, kai mes
pirmą kartą pradėjo sudarant programas.

642
00:29:52,660 --> 00:29:55,200
Iš tiesų, visa tai buvo
vyksta po gaubtu,

643
00:29:55,200 --> 00:29:57,241
bet dabar mes tokioje padėtyje,
kur mes galime iš tikrųjų

644
00:29:57,241 --> 00:29:58,794
erzinti, išskyrus šiuos įvairius veiksmus.

645
00:29:58,794 --> 00:30:00,710
Ir iš tikrųjų, pabaigoje
dienos, mes vis dar

646
00:30:00,710 --> 00:30:04,480
liko nulių ir, kurie
yra tikrai puikus Segue dabar

647
00:30:04,480 --> 00:30:08,620
į kitą C galimybes, kad
mes neturėjome sverto greičiausiai

648
00:30:08,620 --> 00:30:11,250
iki šiol žinoma kaip Bitinis operatorių.

649
00:30:11,250 --> 00:30:15,220
Kitaip tariant, iki šiol, bet kuriuo metu, mes
nagrinėjami duomenų C arba kintamųjų C,

650
00:30:15,220 --> 00:30:17,660
mes jau tokius dalykus kaip
simbolių ir plūdės ir moduliai

651
00:30:17,660 --> 00:30:21,990
ir ilgisi ir dviviečiai ir pan, bet
visi iš jų yra bent aštuonis bitai.

652
00:30:21,990 --> 00:30:25,550
Mes niekada dar galėjo
manipuliuoti atskirus bitus,

653
00:30:25,550 --> 00:30:28,970
nors individualaus tiek, mes
žinau, gali atstovauti 0 ir 1.

654
00:30:28,970 --> 00:30:32,640
Dabar paaiškėja, kad C, jums
galite gauti prieigą prie atskirų bitų,

655
00:30:32,640 --> 00:30:35,530
jei žinote, sintaksę,
su kuria gauti į juos.

656
00:30:35,530 --> 00:30:38,010
>> Taigi leiskite pažvelgti
ne Bitinis operatorių.

657
00:30:38,010 --> 00:30:41,700
Taigi nuotraukoje čia yra keletas simboliai
mes, tipo, rūšiuoti, matęs.

658
00:30:41,700 --> 00:30:45,580
Matau ampersendo, vertikalus
Baras, ir kai kurie kiti, taip pat,

659
00:30:45,580 --> 00:30:49,430
ir prisiminti, kad Ampersand ampersendo
yra kažkas, ką mes matėme anksčiau.

660
00:30:49,430 --> 00:30:54,060
Logiška operatorius AND, kur jūs turite
du iš jų kartu, arba loginis ARBA

661
00:30:54,060 --> 00:30:56,300
operatorius, kur jūs
turi dvi vertikalias juostas.

662
00:30:56,300 --> 00:31:00,550
Bitinis operatorių, kuris mes
matyti veikti bitai individualiai,

663
00:31:00,550 --> 00:31:03,810
tiesiog naudoti vieną ampersendo A
vieno vertikali juosta, Žymeklis simbolis

664
00:31:03,810 --> 00:31:06,620
ateina kitas, mažai
Tilde, tada į kairę

665
00:31:06,620 --> 00:31:08,990
laikiklis paliko laikiklį arba
teisė laikiklis teisę laikiklis.

666
00:31:08,990 --> 00:31:10,770
Kiekvienas iš jų turi skirtingas reikšmes.

667
00:31:10,770 --> 00:31:11,950
>> Iš tiesų, tegul pažvelgti.

668
00:31:11,950 --> 00:31:16,560
Vykime senosios mokyklos šiandien ir naudojimas
jutiklinis ekranas iš praeities,

669
00:31:16,560 --> 00:31:18,002
žinomas kaip baltos lentos.

670
00:31:18,002 --> 00:31:19,710
Ir tai balta lenta
ketina leisti mums

671
00:31:19,710 --> 00:31:27,360
išreikšti keletą gana paprastų simbolius,
ar veikiau kai gana paprastas formules,

672
00:31:27,360 --> 00:31:29,560
, kad mes galime tada galiausiai
svertas, kad būtų

673
00:31:29,560 --> 00:31:33,230
prieiti prie atskirų
bitai per C programa.

674
00:31:33,230 --> 00:31:34,480
Kitaip tariant, galime tai padaryti.

675
00:31:34,480 --> 00:31:37,080
Tegul pirmasis aptarimas dėl
momentas apie ženklui,

676
00:31:37,080 --> 00:31:39,560
kuri yra Bitinis operatorius AND.

677
00:31:39,560 --> 00:31:42,130
Kitaip tariant, tai yra
operatorius, kuris leidžia

678
00:31:42,130 --> 00:31:45,930
man turėti kairinis kintamasis
Paprastai ir dešinė kintamasis,

679
00:31:45,930 --> 00:31:50,640
arba individualus vertė, tai jei mes IR
juos kartu, suteikia man galutinį rezultatą.

680
00:31:50,640 --> 00:31:51,560
Taigi, ką aš turiu galvoje?

681
00:31:51,560 --> 00:31:54,840
Jei programoje, turite kintamąjį
kuris saugo vieną iš šių reikšmių,

682
00:31:54,840 --> 00:31:58,000
arba tegul keep it simple, ir tik
rašyti nulių ir individualiai,

683
00:31:58,000 --> 00:32:00,940
Štai kaip Ampersand operatorius veikia.

684
00:32:00,940 --> 00:32:06,400
0 Ampersand 0 ketina lygus 0.

685
00:32:06,400 --> 00:32:07,210
Dabar, kodėl taip yra?

686
00:32:07,210 --> 00:32:09,291
>> Tai labai panašus į
Būlio išraiškos,

687
00:32:09,291 --> 00:32:10,540
kad mes aptarė iki šiol.

688
00:32:10,540 --> 00:32:15,800
Jei manote, galų gale, yra 0
klaidinga, 0 yra klaidinga, klaidinga ir neteisinga

689
00:32:15,800 --> 00:32:18,720
yra, kaip mes aptarti
Logiškai mąstant, taip pat klaidinga.

690
00:32:18,720 --> 00:32:20,270
Taigi mes gauname 0 čia taip pat.

691
00:32:20,270 --> 00:32:24,390
Pavartojus 0 ampersendo
1, gerai, kad, taip pat,

692
00:32:24,390 --> 00:32:29,890
bus 0, nes tai
kairine išraiška, kad būtų tiesa arba 1,

693
00:32:29,890 --> 00:32:32,360
ji turi būti teisinga ir tikra.

694
00:32:32,360 --> 00:32:36,320
Bet čia mes turime klaidinga
ir tiesa, arba 0 ir 1.

695
00:32:36,320 --> 00:32:42,000
Dabar vėl, jei mes turime 1 ampersendo
0, tai taip pat bus 0,

696
00:32:42,000 --> 00:32:47,240
ir jei mes turime 1 ampersendo 1,
pagaliau mes turime 1 bitas.

697
00:32:47,240 --> 00:32:50,340
Taigi, kitaip tariant, mes ne daro
nieko įdomiau su šiuo operatoriumi

698
00:32:50,340 --> 00:32:51,850
tik dar, tai Ampersand operatorius.

699
00:32:51,850 --> 00:32:53,780
Tai Bitinis operatorius AND.

700
00:32:53,780 --> 00:32:57,290
Tačiau tai yra ingredientai
per kurį mes galime padaryti

701
00:32:57,290 --> 00:32:59,240
įdomių dalykų, kaip mes netrukus pamatysite.

702
00:32:59,240 --> 00:33:02,790
>> Dabar pažvelkime tik vieną
vertikali juosta Čionai dešinėje.

703
00:33:02,790 --> 00:33:06,710
Jei turiu 0 truputį ir aš
Arba tai su ja Bitinis

704
00:33:06,710 --> 00:33:11,030
Arba operatorius, kitas 0 truputį,
kad ketina suteikti man 0.

705
00:33:11,030 --> 00:33:17,540
Jei aš imtis 0 truputį ir ar IT su
A 1 tiek, tada aš ruošiuosi gauti 1.

706
00:33:17,540 --> 00:33:19,830
Ir iš tikrųjų, tik
aiškumas, leiskite man grįžti,

707
00:33:19,830 --> 00:33:23,380
kad mano vertikalios juostos
nėra klaidingai palaikyta 1 s.

708
00:33:23,380 --> 00:33:26,560
Leiskite man perrašyti visus
mano 1 yra šiek tiek daugiau

709
00:33:26,560 --> 00:33:32,700
aiškiai, taip, kad mes kitą žr, jei aš
turėti 1 arba 0, kad ketina būti 1,

710
00:33:32,700 --> 00:33:39,060
o jei turiu 1 arba 1, kad,
taip pat ketina būti 1.

711
00:33:39,060 --> 00:33:42,900
Taigi jūs galite pamatyti logiškai, kad AR
operatorius elgiasi labai skirtingai.

712
00:33:42,900 --> 00:33:48,070
Tai suteikia man 0 arba 0 man duoda 0, tačiau
kiekvienas kitas derinys suteikia man 1.

713
00:33:48,070 --> 00:33:52,480
Kol turiu vieną 1 dalyje,
formulė, rezultatas bus 1 d.

714
00:33:52,480 --> 00:33:55,580
>> Skirtingai nei paties ir
operatorius, Ampersand,

715
00:33:55,580 --> 00:34:00,940
tik tada, jei turiu du 1, The
lygtis, aš iš tikrųjų gauti 1 iš.

716
00:34:00,940 --> 00:34:02,850
Dabar yra keletas kitų
operatoriai, taip pat.

717
00:34:02,850 --> 00:34:04,810
Vienas iš jų yra šiek tiek daugiau įsitraukti.

718
00:34:04,810 --> 00:34:07,980
Taigi leiskite man eiti į priekį ir ištrinti
tai atlaisvinti šiek tiek vietos.

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

720
00:34:13,020 --> 00:34:16,460
Ir tegul ne išvaizdą
Žymeklis simboliu, tik akimirkai.

721
00:34:16,460 --> 00:34:18,210
Tai yra paprastai
charakteris galite įvesti

722
00:34:18,210 --> 00:34:21,420
Jūsų klaviatūra laikymu Shift ir
tada vienas ant savo JAV skaičiais

723
00:34:21,420 --> 00:34:22,250
klaviatūra.

724
00:34:22,250 --> 00:34:26,190
>> Taigi tai yra išskirtinis
Arba operatorius, arba išimtines.

725
00:34:26,190 --> 00:34:27,790
Taigi mes tiesiog pamačiau arba operatorius.

726
00:34:27,790 --> 00:34:29,348
Tai yra išimtinė arba operatorius.

727
00:34:29,348 --> 00:34:30,639
Kas iš tikrųjų skirtumas?

728
00:34:30,639 --> 00:34:34,570
Na tegul tiesiog pažvelgti į formulę,
ir tai naudoti kaip ingredientus galiausiai.

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

730
00:34:37,690 --> 00:34:39,650
Aš ruošiuosi pasakyti visada 0.

731
00:34:39,650 --> 00:34:41,400
Štai iš XOR apibrėžimas.

732
00:34:41,400 --> 00:34:47,104
0 XOR 1 bus 1 d.

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 bus 1,
ir 1 XOR 1 bus?

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

735
00:34:59,890 --> 00:35:00,520
Arba tiesa?

736
00:35:00,520 --> 00:35:01,860
Nežinau.

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

738
00:35:02,810 --> 00:35:04,700
Dabar tai, kas vyksta čia?

739
00:35:04,700 --> 00:35:06,630
Na manau, kad apie
Pavadinimas šio operatoriaus.

740
00:35:06,630 --> 00:35:09,980
Išskirtinis ARBA, taip, kaip
pavadinimas, rūšis ir, rodo,

741
00:35:09,980 --> 00:35:13,940
atsakymas tik bus
A 1, jei indėlis yra išskirtinis,

742
00:35:13,940 --> 00:35:15,560
tik skirtingi.

743
00:35:15,560 --> 00:35:18,170
Taigi čia įėjimai yra
pat, todėl išėjimas yra 0.

744
00:35:18,170 --> 00:35:20,700
Čia įėjimai yra
pat, todėl išėjimas yra 0.

745
00:35:20,700 --> 00:35:25,640
Čia yra išėjimai yra skirtingi, todėl jie
yra išimtinės, todėl produkcija yra 1.

746
00:35:25,640 --> 00:35:28,190
Taigi, tai labai panašus į
IR, tai labai panašūs,

747
00:35:28,190 --> 00:35:32,760
ar veikiau tai labai panašus į
ARBA, bet tik išskirtiniu būdu.

748
00:35:32,760 --> 00:35:36,210
Tai vienas yra nebėra 1,
nes mes turime dvi 1-ųjų,

749
00:35:36,210 --> 00:35:38,621
ir ne išimtinai, tik vienas iš jų.

750
00:35:38,621 --> 00:35:39,120
Gerai.

751
00:35:39,120 --> 00:35:40,080
Ką apie kitus?

752
00:35:40,080 --> 00:35:44,220
Na tildės, tuo tarpu, yra
iš tikrųjų gražus ir paprastas, laimei.

753
00:35:44,220 --> 00:35:46,410
Ir tai unarinį
operatoriaus, kuris reiškia,

754
00:35:46,410 --> 00:35:50,400
jis taikomas tik vieną įvesties,
vienas operandas, taip sakant.

755
00:35:50,400 --> 00:35:51,800
Ne iš kairės ir dešinę.

756
00:35:51,800 --> 00:35:56,050
Kitaip tariant, jei vartojate tildės iš
0, atsakymas bus priešingas.

757
00:35:56,050 --> 00:35:59,710
Ir jei jūs imtis Tilde 1, The
Atsakymas bus priešingas.

758
00:35:59,710 --> 00:36:02,570
Taigi tildės operatorius
iš paneigiant truputį būdas,

759
00:36:02,570 --> 00:36:06,000
arba prakeiktas nuo tiek
0-1, arba nuo 1 iki 0.

760
00:36:06,000 --> 00:36:09,820
>> Ir tai palieka mus pagaliau
tik su dviem galutiniais operatorių,

761
00:36:09,820 --> 00:36:13,840
vadinamasis kairysis SHIFT ir
Vadinamasis teisę perėjimas operatorius.

762
00:36:13,840 --> 00:36:16,620
Paimkime, kaip tas darbas atrodo.

763
00:36:16,620 --> 00:36:20,780
Ataka perėjimas operatorius, parašyta
su dviem laužtiniuose skliaustuose, pavyzdžiui, kad

764
00:36:20,780 --> 00:36:22,110
veikia taip.

765
00:36:22,110 --> 00:36:27,390
Jei mano indėlis, ar mano operandas, į kairę
perėjimas operatorius paprasčiausiai yra 1.

766
00:36:27,390 --> 00:36:33,750
Ir aš tada pasakysiu kompiuterį
į kairę, kad 1, pasakyti septyni vietos,

767
00:36:33,750 --> 00:36:37,150
rezultatas yra tarsi būčiau
imtis, kad 1, ir perkelti jį

768
00:36:37,150 --> 00:36:40,160
septynios vietos perkelti į
kairysis, ir pagal nutylėjimą,

769
00:36:40,160 --> 00:36:42,270
mes ketiname daryti prielaidą, kad
erdvė į dešinę

770
00:36:42,270 --> 00:36:44,080
ketina būti su paminkštinimu nuliai.

771
00:36:44,080 --> 00:36:50,316
Kitaip tariant, 1 paliktas poslinkio 7 vyksta
duoti me, kad 1, po 1, 2, 3,

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

773
00:36:54,060 --> 00:36:57,380
Taigi tokiu būdu, jis leidžia jums
imtis nedidelį skaičių kaip 1,

774
00:36:57,380 --> 00:37:00,740
ir aiškiai padaryti jį daug
daug, daug didesnis šiuo būdu,

775
00:37:00,740 --> 00:37:06,460
bet mes iš tikrųjų ketiname pamatyti
daugiau protingas požiūriai jį

776
00:37:06,460 --> 00:37:08,080
vietoj to, taip pat,

777
00:37:08,080 --> 00:37:08,720
>> Gerai.

778
00:37:08,720 --> 00:37:10,060
Štai jį savaitę trys.

779
00:37:10,060 --> 00:37:11,400
Pamatysime, jums kitą kartą.

780
00:37:11,400 --> 00:37:12,770
Tai buvo CS50.

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

782
00:37:17,270 --> 00:37:22,243
>> [Muzikos grojimo]

783
00:37:22,243 --> 00:37:25,766
>> GARSIAKALBIS 1: Jis buvo tuo užkandis
bar valgyti karštą fudge ledai.

784
00:37:25,766 --> 00:37:28,090
Jis turėjo viską per veidą.

785
00:37:28,090 --> 00:37:30,506
Jis dėvi, kad kaip ir barzda šokoladą

786
00:37:30,506 --> 00:37:31,756
SPEAKER 2: Ką tu darai?

787
00:37:31,756 --> 00:37:32,422
GARSIAKALBIS 3: Hmmm?

788
00:37:32,422 --> 00:37:33,500
Ką?

789
00:37:33,500 --> 00:37:36,800
>> SPEAKER 2: Ar jums tiesiog dukart DIP?

790
00:37:36,800 --> 00:37:38,585
Jūs dvigubai artimųjų lustas.

791
00:37:38,585 --> 00:37:39,460
GARSIAKALBIS 3: Atleiskit.

792
00:37:39,460 --> 00:37:44,440
SPEAKER 2: Jūs artimųjų lustas, jums
paėmė įkandimo, ir jūs artimųjų vėl.

793
00:37:44,440 --> 00:37:44,940
GARSIAKALBIS 3:

794
00:37:44,940 --> 00:37:48,440
SPEAKER 2: Štai kaip pradėti
Visa jūsų burna tiesiai į kritimo.

795
00:37:48,440 --> 00:37:52,400
Kitą kartą išgėrėte lustą,
tik panirti jį vieną kartą, ir ją baigti.

796
00:37:52,400 --> 00:37:53,890
>> GARSIAKALBIS 3: jūs žinote, ką Dan?

797
00:37:53,890 --> 00:37:58,006
Jūs panirti kelią, kurį norite panirti.

798
00:37:58,006 --> 00:38:01,900
Aš panirti kelią, kad aš noriu panirti.

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