1
00:00:00,000 --> 00:00:11,270

2
00:00:11,270 --> 00:00:14,910
>> SPEAKER: Kull dritt, dan huwa CS50.

3
00:00:14,910 --> 00:00:19,020
Dan huwa l-aħħar ta 'tliet ġimgħat, u jekk
ma tkunx ħadt vantaġġ li jkun diġà,

4
00:00:19,020 --> 00:00:21,790
jafu li se jkun hemm ikla
din il-ġimgħa bħas-soltu, fejn

5
00:00:21,790 --> 00:00:25,430
inti tista 'tgawdi konversazzjoni tajba
u l-ikel fil-nar u Silġ

6
00:00:25,430 --> 00:00:27,980
ma 'wħud mill l CS50
persunal u klassi.

7
00:00:27,980 --> 00:00:30,170
Head sa dan il-URL hawn.

8
00:00:30,170 --> 00:00:33,420
>> Issa inti tista 'recall, jew inti
dalwaqt jista ikunu familjari ma ',

9
00:00:33,420 --> 00:00:35,970
dawn l-affarijiet hawn, li
huma mogħtija fl-aħħar

10
00:00:35,970 --> 00:00:37,850
tas-semestru għal ħafna klassijiet.

11
00:00:37,850 --> 00:00:40,870
Kotba blu hekk imsejħa eżami, f'liema
tikteb tweġibiet tiegħek għall-eżamijiet.

12
00:00:40,870 --> 00:00:44,240
Issa għandi hawn 26 bħal
kotba blu, fuq kull wieħed minnhom

13
00:00:44,240 --> 00:00:47,580
huwa miktub l-isem, A permezz Z. And
tabilħaqq l-ismijiet huma li sempliċi, A

14
00:00:47,580 --> 00:00:50,490
permezz Z. U wieħed ta '
l-għanijiet fil-idejn llum

15
00:00:50,490 --> 00:00:53,910
se tkun li tkompli liema
bdejna nhar it-Tnejn, li mhuwiex

16
00:00:53,910 --> 00:00:57,830
tant tħares lejn kodiċi, imma verament
tħares lejn ideat u sabiex jissolvew problemi.

17
00:00:57,830 --> 00:01:00,170
Wieħed mill-għanijiet u
wegħdiet ta 'dan il-kors

18
00:01:00,170 --> 00:01:02,985
huwa li jgħallmu inti biex jaħsbu b'mod aktar
b'attenzjoni, aktar metodiku,

19
00:01:02,985 --> 00:01:05,400
u sabiex isolvu problemi b'mod aktar effiċjenti.

20
00:01:05,400 --> 00:01:09,526
U fil-fatt, nistgħu nagħmlu li verament
anki mingħajr jmissu linja ta 'kodiċi.

21
00:01:09,526 --> 00:01:12,150
So I jkollhom koppja ta 'ljunfanti
up hawn illum, oranġjo u blu,

22
00:01:12,150 --> 00:01:15,780
jekk nistgħu jiksbu voluntier wieħed,
forsi minn farther lura mis-soltu.

23
00:01:15,780 --> 00:01:18,070
Kif dwar id-dritt hemmhekk, jaqgħu fuq l isfel.

24
00:01:18,070 --> 00:01:24,180
L-għan ta 'liema se jkun li
jgħinu plus jamministra dan il-eżami hawn.

25
00:01:24,180 --> 00:01:24,935
X'hemm isem tiegħek?

26
00:01:24,935 --> 00:01:25,768
>> UDJENZA: Mary Beth.

27
00:01:25,768 --> 00:01:27,560
SPEAKER: Mary Beth, come fuq up.

28
00:01:27,560 --> 00:01:29,560
Let me nikseb il-mikrofonu hawn għalik.

29
00:01:29,560 --> 00:01:32,172

30
00:01:32,172 --> 00:01:32,880
Nizza li jissodisfaw inti.

31
00:01:32,880 --> 00:01:34,005
>> UDJENZA: Nizza li jissodisfaw inti.

32
00:01:34,005 --> 00:01:36,790
SPEAKER: Kull dritt, so I jkollhom
hawn blu kotba A permezz Z,

33
00:01:36,790 --> 00:01:41,680
u jien ser nippretendu li
I jkollhom waħda mill-istudenti,

34
00:01:41,680 --> 00:01:45,770
u dawn qed ġejjin fil kemmxejn saltwarjament
fl-aħħar tal-blokka tal-eżami ta 'tliet sigħat,

35
00:01:45,770 --> 00:01:49,400
hekk dawn qed jispiċċaw f'xi
Sabiex semi-każwali bħal dan.

36
00:01:49,400 --> 00:01:54,510
Issa xogħol tiegħek fi ftit mument huwa għaddej
biex be-- dan huwa attwalment kif huma jiksbu

37
00:01:54,510 --> 00:01:56,820
kellu fl-aħħar ta '
il-klassi, l-aktar probabbli.

38
00:01:56,820 --> 00:02:01,120
Impjieg tiegħek issa se tkun, pjuttost
sempliċiment, biex issolvi dawn il-kotba blu għalina

39
00:02:01,120 --> 00:02:05,220
minn A sa Z.

40
00:02:05,220 --> 00:02:08,400
>> UDJENZA: Oh, dan huwa
ser jieħdu dejjem.

41
00:02:08,400 --> 00:02:13,747
>> SPEAKER: U aħna ser tara
kif inti tagħmel dan, l-ebda pressjoni.

42
00:02:13,747 --> 00:02:15,330
UDJENZA: No, no pressjoni jew xejn.

43
00:02:15,330 --> 00:02:19,230

44
00:02:19,230 --> 00:02:23,570
>> SPEAKER: U għall-gost,
ejja imqiegħed tajmer.

45
00:02:23,570 --> 00:02:26,680

46
00:02:26,680 --> 00:02:28,700
>> UDJENZA: gost Tant hu, tant gost.

47
00:02:28,700 --> 00:02:36,741

48
00:02:36,741 --> 00:02:38,574
>> SPEAKER: I tista 'żżomm l-mic għalik.

49
00:02:38,574 --> 00:02:40,240
Kull dritt, konna biss irdoppja veloċità tagħna.

50
00:02:40,240 --> 00:02:44,190

51
00:02:44,190 --> 00:02:49,060
Allura fil-frattemp, let me joħolqu x'hemm
se tkun il-kwistjoni għall Mary Beth

52
00:02:49,060 --> 00:02:51,540
huwa dak li qed tagħmel hi, kif huwa
hi għaddej dwar isolvi dan?

53
00:02:51,540 --> 00:02:54,040
U fil-fatt, inti jista 'ma jkollhomx
qatt ħsibt dwar xi ħaġa

54
00:02:54,040 --> 00:02:57,440
tant sempliċi bħal meta inti pick
up 26 kotba bħal dan,

55
00:02:57,440 --> 00:02:59,350
li ma jkollhom naturali
tordna lilhom.

56
00:02:59,350 --> 00:03:01,335
X'inhu l-proċess
li inti attwalment jużaw?

57
00:03:01,335 --> 00:03:03,770
Huwa pjuttost każwali biss
picking-ewwel waħda tara

58
00:03:03,770 --> 00:03:05,250
u t-tqegħid fil-post tagħha?

59
00:03:05,250 --> 00:03:09,680
Do inti l-ewwel timxi idejk madwar
Looking for a imbagħad tfittex B?

60
00:03:09,680 --> 00:03:11,722
Do inti tagħti ħarsa lejn
par minnhom ġenb ma 'ġenb

61
00:03:11,722 --> 00:03:14,680
u biss jgħidu, stenna minuta, dan
mhuwiex dritt, u mbagħad tpartit l-ordni?

62
00:03:14,680 --> 00:03:16,960
Rajna diġà nhar it-Tnejn
li hemm numru ta 'modi

63
00:03:16,960 --> 00:03:22,140
li nistgħu nagħmlu dan, u
tabilħaqq kif aħna qrib it-tmiem hawn,

64
00:03:22,140 --> 00:03:26,360
Nixtieq jieħdu nota forsi
ta 'dak Mary Beth qed tagħmel.

65
00:03:26,360 --> 00:03:30,040
Għandna piles ftit jidher, a
akbar wieħed, tliet dawk iżgħar.

66
00:03:30,040 --> 00:03:33,790

67
00:03:33,790 --> 00:03:36,415
>> UDJENZA: Jien tordna minnhom
meta I ssib żewġ ittri

68
00:03:36,415 --> 00:03:39,540
li naf huma flimkien f'sekwenza,
I jpoġġuhom flimkien b'tali mod li jien ma

69
00:03:39,540 --> 00:03:42,915
jkollhom għalfejn tinkwieta dwar iż-żamma
track ta 'ringiela sħiħa ta' kotba.

70
00:03:42,915 --> 00:03:45,706
Huwa biss, oh, A huwa l-ewwel,
Stajt sibt dan munzell hawn.

71
00:03:45,706 --> 00:03:47,580
SPEAKER: Allura, kważi simili
biċċiet puzzle li

72
00:03:47,580 --> 00:03:49,860
għandhom il-forma dritt li
jaqblu ma 'xulxin.

73
00:03:49,860 --> 00:03:51,026
UDJENZA: Pretty ħafna, yeah.

74
00:03:51,026 --> 00:03:55,320
SPEAKER: OK, eċċellenti.

75
00:03:55,320 --> 00:03:59,850
U issa kull wieħed minn dawn
piles huwa preżumibbilment magħżula?

76
00:03:59,850 --> 00:04:00,990
>> UDJENZA: Yeah.

77
00:04:00,990 --> 00:04:09,900
>> SPEAKER: Kull dritt, A permezz Z. All
dritt, congratulations, inti ma kien.

78
00:04:09,900 --> 00:04:11,461
Inti għandek l-għażla tiegħek.

79
00:04:11,461 --> 00:04:11,960
Blue?

80
00:04:11,960 --> 00:04:13,530
Kull dritt, nirringrazzjak għal dak.

81
00:04:13,530 --> 00:04:16,679
Allura Mary Beth ma tipproponi
dak l-approċċ tagħha kien,

82
00:04:16,679 --> 00:04:19,720
imma dak li hu approċċ ieħor kif inti
jista 'jmur dwar issortjar dawn l-affarijiet?

83
00:04:19,720 --> 00:04:21,130
What would you għamlu?

84
00:04:21,130 --> 00:04:24,060
Ir-rekord li tħabbat kien ikun
minuta u 50 sekonda jew hekk,

85
00:04:24,060 --> 00:04:26,039
plus dawk I nesa biex jingħaddu.

86
00:04:26,039 --> 00:04:27,080
What would you għamlu?

87
00:04:27,080 --> 00:04:27,579
Yeah?

88
00:04:27,579 --> 00:04:28,735
UDJENZA: Ħu l-munzell.

89
00:04:28,735 --> 00:04:29,776
Ibda mill-bidu.

90
00:04:29,776 --> 00:04:32,284
Iċċekkja karti tiegħek.

91
00:04:32,284 --> 00:04:36,586
U jekk il-wieħed quċċata hija ogħla
minn, forsi, huma,

92
00:04:36,586 --> 00:04:38,980
l-waħda qiegħ hija
ogħla, imbagħad ixgħel minnhom.

93
00:04:38,980 --> 00:04:41,300
>> SPEAKER: OK, hekk jibdew
fil-quċċata u l-qiegħ,

94
00:04:41,300 --> 00:04:43,716
u mbagħad jaħdmu tiegħek mod
ġewwa bħal dik, jagħmlu skambju ta minnhom?

95
00:04:43,716 --> 00:04:46,580
OK, hekk ftit simili
fl-ispirtu li sort bużżieqa,

96
00:04:46,580 --> 00:04:49,160
iżda jagħżlu l-estremi
mhux il-pari li jmissu magħhom.

97
00:04:49,160 --> 00:04:52,080
Iżda l-qasira ta 'dan hija li hemm
żgur mazz ta 'modi differenti

98
00:04:52,080 --> 00:04:54,210
stajna nagħmlu dan, u
franchement, I think inti tip ta '

99
00:04:54,210 --> 00:04:55,700
adottat approċċi koppja, id-dritt?

100
00:04:55,700 --> 00:05:00,567
Inti għamilt tip ta 'erba' puntali magħżula, u
imbagħad effettivament magħquda flimkien.

101
00:05:00,567 --> 00:05:02,650
U li, daresay, ieħor
teknika għal kollox.

102
00:05:02,650 --> 00:05:06,950
Inti ma titratta dan bħala pile waħda kbira,
inti maqsuma l-problema f'erba quads,

103
00:05:06,950 --> 00:05:09,820
jekk inti se, u mbagħad b'xi mod
ingħaqdu minnhom fl-aħħar.

104
00:05:09,820 --> 00:05:13,410
>> Mela ejja jikkunsidraw, finalment,
kif inkella nistgħu nagħmlu dan.

105
00:05:13,410 --> 00:05:15,860
Aħna formalizzata l-kunċett
ta bubble sort aħħar darba,

106
00:05:15,860 --> 00:05:18,780
u recall sort bużżieqa kien
algoritmu li aħna viżwalizzata

107
00:05:18,780 --> 00:05:22,640
bl tmienja mill-klassi tiegħek up here,
apparentement saltwarjament magħżula fl-ewwel.

108
00:05:22,640 --> 00:05:26,110
U aħna mbagħad iddeċidew pairwise, jekk
żewġ elementi huma out of order,

109
00:05:26,110 --> 00:05:26,950
sempliċiment swap lilhom.

110
00:05:26,950 --> 00:05:28,930
Allura erba 'u tnejn huma
ovvjament out of order,

111
00:05:28,930 --> 00:05:31,080
hekk dawn iż-żewġ klassi
pożizzjonijiet qalbu.

112
00:05:31,080 --> 00:05:35,390
U allura aħna ripetut erba 'u sitt,
imbagħad sitta u tmienja, fuq kull iterazzjoni,

113
00:05:35,390 --> 00:05:36,980
jiċċaqalqu lejn il-lemin.

114
00:05:36,980 --> 00:05:42,590
>> Allura mogħtija tmien persuni, pairwise kemm
paraguni ma nagħmel waqt mixi minn

115
00:05:42,590 --> 00:05:45,220
xellug għall-lemin iterazzjoni waħda tali?

116
00:05:45,220 --> 00:05:48,410
Kif paraguni ħafna?

117
00:05:48,410 --> 00:05:49,197
Seba, id-dritt?

118
00:05:49,197 --> 00:05:51,405
Għaliex jekk hemm tmienja
nies iżda inti għandek il-par

119
00:05:51,405 --> 00:05:53,880
lilhom u inti żżomm jiċċaqalqu
wieħed ħops għad-dritt,

120
00:05:53,880 --> 00:05:56,060
int mhux se jkollhom tmien
paraguni għaliex inti ma tistax tqabbel

121
00:05:56,060 --> 00:05:59,226
element kontra innifsu, jew kieku
biss tkun inutli, hekk ikollok seba.

122
00:05:59,226 --> 00:06:01,290
Jew b'mod iktar ġenerali, jekk
għandna n-nies, aħna

123
00:06:01,290 --> 00:06:04,300
do n minus 1 paraguni
ma sort bużżieqa.

124
00:06:04,300 --> 00:06:08,150
>> Mela ejja jikkunsidraw issa kif tajba jew
bubble bad sort attwalment kien, u jippruvaw

125
00:06:08,150 --> 00:06:13,570
biex jagħtu lilna nfusna vokabularju ma
li biex algoritmi critique bħal dan,

126
00:06:13,570 --> 00:06:14,430
u dalwaqt tagħna stess.

127
00:06:14,430 --> 00:06:16,970
Allura l-ewwel pass permezz
sort bużżieqa, l-ewwel darba

128
00:06:16,970 --> 00:06:20,909
I mixi minn fuq ix-xellug għal-lemin madwar il-
istadju, ħa me n minus 1 paraguni.

129
00:06:20,909 --> 00:06:22,950
U li għaddej biex tkun tiegħi
unità tal-kejl, id-dritt?

130
00:06:22,950 --> 00:06:26,170
I kien tip ta 'titkellem u strolling,
kemmxejn mgħaġġel, kemmxejn kajman,

131
00:06:26,170 --> 00:06:29,300
hekk għadd tiegħi numru ta 'sekonda
mhuwiex partikolarment javżak,

132
00:06:29,300 --> 00:06:32,260
iżda għadd tan-numru ta '
operazzjonijiet li għamilt nhar it-Tnejn,

133
00:06:32,260 --> 00:06:35,900
jitqabblu żewġ persuni, li jħoss
bħal unità sympathique ta 'miżura.

134
00:06:35,900 --> 00:06:40,980
>> Allura n minus 1 passi l-ewwel darba,
iżda mbagħad dak li ġara wara li?

135
00:06:40,980 --> 00:06:46,610
X'hemm-rasu waħda pass wieħed
permezz ta 'lista inkella mhux magħżul?

136
00:06:46,610 --> 00:06:49,840
X'tista 'tgħidli dwar l-element
li kien il-triq kollha hemmhekk?

137
00:06:49,840 --> 00:06:51,300
Yeah?

138
00:06:51,300 --> 00:06:52,870
Dan kien l-element akbar, id-dritt?

139
00:06:52,870 --> 00:06:55,710
Numru tmienja, anki jekk hija
beda hawn, kull darba I

140
00:06:55,710 --> 00:06:57,860
imqabbla tagħha kontra
ġar, hi miżmuma

141
00:06:57,860 --> 00:07:00,480
tbaqbieq up lejn il-lemin
naħa tal-lista.

142
00:07:00,480 --> 00:07:02,710
U fil-fatt, li fejn
l-algoritmu gets isimha.

143
00:07:02,710 --> 00:07:07,630
>> Issa billi li l-loġika, kif ħafna paraguni
bżonn I jagħmlu fuq il-tieni darba

144
00:07:07,630 --> 00:07:09,800
I jagħmlu li jgħaddu mix-xellug għal-lemin?

145
00:07:09,800 --> 00:07:10,730
n minus 2, id-dritt?

146
00:07:10,730 --> 00:07:14,297
Ikun biss tkun ħela ta 'ħin tiegħi jekk I
iżommu jqabbel tmienja kontra xi ħadd

147
00:07:14,297 --> 00:07:16,630
inkella għaliex aħna diġà jafu
kienet fil-post dritt.

148
00:07:16,630 --> 00:07:19,760
Allura dak daqsxejn ta '
ottimizzazzjoni, sabiex il-pass li jmiss

149
00:07:19,760 --> 00:07:23,899
se tkun plus n minus żewġ passi,
fejn n huwa n-numru ta 'nies.

150
00:07:23,899 --> 00:07:26,940
Issa inti tista 'tip ta' estrapolati, anke
jekk int ma xjenzat kompjuter,

151
00:07:26,940 --> 00:07:27,680
kif dan truf.

152
00:07:27,680 --> 00:07:31,259
Fl-aħħar ta 'dan algoritmu, preżumibbilment
inti ħadthom ltqajna waħda biss paragun xellug.

153
00:07:31,259 --> 00:07:33,800
Int għandek tip ta 'tiffissa l-
bidu tal-lista fil-każ f'żewġ

154
00:07:33,800 --> 00:07:36,540
u wieħed huma out of order
u għandu jkun wieħed u tnejn,

155
00:07:36,540 --> 00:07:40,330
għalhekk dan Qigħan fil
plus 1 finali paragun.

156
00:07:40,330 --> 00:07:44,500
>> Issa l-dot, dot, dot tip ta 'mewġ huwa
idejn fil wħud mid-dettalji juicier,

157
00:07:44,500 --> 00:07:46,452
imma ejja biss jimxi 'l quddiem u jissimplifika.

158
00:07:46,452 --> 00:07:48,660
Jekk inti recall minn għoli
iskola, franchement, ħafna minnkom

159
00:07:48,660 --> 00:07:50,340
kellhom kotba matematika li kellhom
iqarrqu folja ftit

160
00:07:50,340 --> 00:07:52,550
fuq il-qoxra ta 'quddiem jew il-
qoxra ta 'wara li wera inti

161
00:07:52,550 --> 00:07:56,400
ammonti totali liema serje bħall
dan finalment miżjud sa.

162
00:07:56,400 --> 00:07:59,600
Fil-każ ġenerali, jekk għandek
varjabbli bħall n, u tabilħaqq dan wieħed,

163
00:07:59,600 --> 00:08:01,634
jekk inti ħares lejn tiegħek
ktieb matematika iskola antika,

164
00:08:01,634 --> 00:08:04,050
inti tara li dan fil-fatt
żżid sa din is-somma hawn,

165
00:08:04,050 --> 00:08:07,970
n ħinijiet n minus 1 kollha diviż bi 2.

166
00:08:07,970 --> 00:08:11,172
Allura għal issa let me biss jistipulaw
dan huwa minnu, hekk fuq qabża ta 'fidi,

167
00:08:11,172 --> 00:08:12,880
dan huwa dak li din somom
sa, u nistgħu

168
00:08:12,880 --> 00:08:14,341
jipprova li f'każ aktar ġenerali.

169
00:08:14,341 --> 00:08:15,590
Imma issa ejja jespandu dan out.

170
00:08:15,590 --> 00:08:19,920
Mela ejja jimmultiplikaw dan out, b'tali mod li
n kwadrat, minus n, kollha diviż bl 2.

171
00:08:19,920 --> 00:08:23,200
Li tassew n kwadrat,
diviż bi 2, minus n aktar minn 2,

172
00:08:23,200 --> 00:08:25,010
hekk li kollox sbieħ u interessanti.

173
00:08:25,010 --> 00:08:27,060
Imma x'jiġri jekk aħna
issa plug-in valur?

174
00:08:27,060 --> 00:08:29,724
Ejja ngħidu I ma kellhomx tmien
nies, iżda jgħidu miljun.

175
00:08:29,724 --> 00:08:31,890
U miljun biss minħabba
huwa numru pretty big,

176
00:08:31,890 --> 00:08:34,039
ejja plagg li fi u tara x'jiġri.

177
00:08:34,039 --> 00:08:39,039
Mela jekk jien plug miljun fis dik il-formula
Jien ser tikseb miljun kwadrat,

178
00:08:39,039 --> 00:08:42,868
diviż bi 2, nieqes
miljun, diviż bl 2.

179
00:08:42,868 --> 00:08:44,159
Issa x'hemm dik għaddej biex ugwali?

180
00:08:44,159 --> 00:08:47,354
Allura 500,000,000,000, minus 500,000.

181
00:08:47,354 --> 00:08:49,270
U jekk I attwalment do
li matematika barra, li l-mezzi

182
00:08:49,270 --> 00:08:53,920
li issortjar miljun
nies bil-tip bużżieqa

183
00:08:53,920 --> 00:09:01,800
tista 'tieħu me 499,999,500,000
passi jew paraguni fl-aħħar,

184
00:09:01,800 --> 00:09:02,900
aħna qed biss estrapolazzjoni.

185
00:09:02,900 --> 00:09:06,860
>> Li iħoss pretty bil-mod, iżda franchement
kejl input wieħed partikolari

186
00:09:06,860 --> 00:09:09,160
bħal dan, mhux kollha li javżak.

187
00:09:09,160 --> 00:09:14,050
Iżda tabilħaqq dan ma jissuġġerixxu li bħala n
gets akbar u akbar, dan algoritmu

188
00:09:14,050 --> 00:09:16,280
tip ta 'tħossha agħar u
agħar, jew inti verament

189
00:09:16,280 --> 00:09:20,450
tibda tħossok l-uġigħ ta 'dik
exponentiation, li n kwadrat,

190
00:09:20,450 --> 00:09:21,770
li żżid up pretty fast.

191
00:09:21,770 --> 00:09:25,340
U dan id-dettall mhuwiex
mitlufa fuq in-nies, fil-fatt

192
00:09:25,340 --> 00:09:29,640
xi snin ilu senatur ċerta li kien
kampanji, sib l isfel għal intervista

193
00:09:29,640 --> 00:09:32,180
ma Eric Google
Schmidt, CEO fil-ħin,

194
00:09:32,180 --> 00:09:36,380
u ġie kkontestat bil-kwistjoni
ferm simili aħna qed jesploraw llum.

195
00:09:36,380 --> 00:09:38,468
Ejja tagħti ħarsa.

196
00:09:38,468 --> 00:09:45,280
>> [Daqq ta 'video]

197
00:09:45,280 --> 00:09:48,560
>> -Senator, Int hawn
fuq Google, u I simili

198
00:09:48,560 --> 00:09:53,382
biex jaħsbu tal-presidenza
bħala intervista tax-xogħol.

199
00:09:53,382 --> 00:09:56,434
Issa, huwa diffiċli biex jiksbu
xogħol bħala president,

200
00:09:56,434 --> 00:09:58,100
u int għaddejjin mill-ħruxija issa.

201
00:09:58,100 --> 00:10:01,860
Huwa wkoll diffiċli li jsibu xogħol fil-Google.

202
00:10:01,860 --> 00:10:05,490
Għandna mistoqsijiet, u aħna
jistaqsu mistoqsijiet kandidati tagħna,

203
00:10:05,490 --> 00:10:09,770
u dan huwa wieħed mill Larry Schwimmer.

204
00:10:09,770 --> 00:10:14,760
What-- inti guys think jien
kidding, huwa dritt hawn.

205
00:10:14,760 --> 00:10:17,930
X'inhu l-aktar mod effiċjenti biex
sort miljun interi 32-bit?

206
00:10:17,930 --> 00:10:21,800

207
00:10:21,800 --> 00:10:24,350
>> -Well--

208
00:10:24,350 --> 00:10:25,200
>> -I'm Sorry, maybe--

209
00:10:25,200 --> 00:10:27,400
>> -Nru, No, no.

210
00:10:27,400 --> 00:10:30,700
Naħseb li l-sort bużżieqa
tkun l-mod żbaljat biex imorru.

211
00:10:30,700 --> 00:10:34,165

212
00:10:34,165 --> 00:10:38,180
>> -Come Fuq, li qallu dan?

213
00:10:38,180 --> 00:10:40,590
I ma tara kompjuter
xjenza fl-isfond tiegħek.

214
00:10:40,590 --> 00:10:42,130
>> -We've Ltqajna Spies tagħna fil hemm.

215
00:10:42,130 --> 00:10:44,930

216
00:10:44,930 --> 00:10:48,444
>> OK, ejja jistaqsu differenti
mistoqsija intervista.

217
00:10:48,444 --> 00:10:49,300
>> [END daqq ta 'video]

218
00:10:49,300 --> 00:10:52,290
>> SPEAKER: Allura jitkellem dwar
numri speċifiċi għalkemm,

219
00:10:52,290 --> 00:10:53,890
mhux se jkun dak kollu li utli.

220
00:10:53,890 --> 00:10:56,810
Mhuwiex lezzjoni ħajja li bużżieqa
sort, minħabba miljun inputs,

221
00:10:56,810 --> 00:10:58,590
jista 'jieħu daqs 500,000,000,000 passi.

222
00:10:58,590 --> 00:11:01,120
Inti ma tistax verament jiġġeneralizza
wisq effettivament minn dak

223
00:11:01,120 --> 00:11:03,560
u jagħmlu deċiżjonijiet tad-disinn tajba
meta tikteb programmi.

224
00:11:03,560 --> 00:11:07,070
Mela ejja tiffoka għalkemm fuq kif
nistgħu jissimplifika dan ir-riżultat.

225
00:11:07,070 --> 00:11:11,780
>> So I ve enfasizzat bl-isfar hawn
ir-riżultat ta 'n kwadrat diviż bi 2,

226
00:11:11,780 --> 00:11:14,330
so a miljun kwadrat
diviż bi 2, u mbagħad

227
00:11:14,330 --> 00:11:16,710
Stajt enfasizzat dak
ir-risposta aħħari kien

228
00:11:16,710 --> 00:11:20,180
ladarba aħna mnaqqas off n diviż bi 2.

229
00:11:20,180 --> 00:11:24,850
U l-pretensjoni jien ser tagħmel issa huwa,
li l-Heck jimpurtah jekk inti naqqas off

230
00:11:24,850 --> 00:11:30,060
a n qodma ftit aktar minn 2 meta l-ewwel
parti ta 'din il-formula hija tant ħafna akbar?

231
00:11:30,060 --> 00:11:33,910
Hija jiddomina l-oħra
tul, n kwadrat diviż bl 2

232
00:11:33,910 --> 00:11:37,510
hija tant ikbar, b'mod ċar, bħala
n gets kbar bħal miljun,

233
00:11:37,510 --> 00:11:41,450
li hemm verament differenza kbira fil
l-aħħar tal-ġurnata bejn 500,000,000,000

234
00:11:41,450 --> 00:11:45,730
u 499,999,500,000?

235
00:11:45,730 --> 00:11:46,349
Mhux tassew.

236
00:11:46,349 --> 00:11:48,640
U hekk dak li aħna qed tmur biex
tagħmel kif xjenzjati tal-kompjuter hija

237
00:11:48,640 --> 00:11:53,270
jinjora dawn it-termini ordni aktar baxxa u
tieħu xi ħaġa bħal din u verament

238
00:11:53,270 --> 00:11:56,050
biss jissimplifika lill-
terminu li għaddej biex jimpurtax.

239
00:11:56,050 --> 00:12:00,315
L-ikbar settijiet ta 'data tagħna jiksbu, l-akbar
databases tagħna jiksbu, il-paġni web aktar

240
00:12:00,315 --> 00:12:02,690
irridu tfittxija, l-aktar
ħbieb għandek fuq Facebook.

241
00:12:02,690 --> 00:12:07,340
>> Bħala n gets akbar, aħna qed verament
jmorru għall-kura dwar l-akbar

242
00:12:07,340 --> 00:12:11,560
tul f'xi analiżi bħal din ta '
algoritmi prestazzjoni tagħna.

243
00:12:11,560 --> 00:12:16,230
U jien se ngħid, inti taf liema,
sort bużżieqa huwa fuq l-ordni ta 'O big,

244
00:12:16,230 --> 00:12:18,060
fuq l-ordni ta 'n kwadrat.

245
00:12:18,060 --> 00:12:20,090
Mhuwiex eżattament n
kwadrat kif aħna stajt tidher,

246
00:12:20,090 --> 00:12:22,060
imma li verament jimpurtah
dwar dawk it-termini iżgħar,

247
00:12:22,060 --> 00:12:24,390
u franchement, li verament
cares jekk irridu iddividi 2?

248
00:12:24,390 --> 00:12:25,870
Li jinsab biss fattur kostanti.

249
00:12:25,870 --> 00:12:29,480
U huwa 500,000,000,000 versus 250
biljun verament li kbar ta 'ftehim?

250
00:12:29,480 --> 00:12:32,190
I jistgħu biss stenna sena,
let laptop tiegħi litteralment

251
00:12:32,190 --> 00:12:34,810
nikseb darbtejn aktar malajr fil-hardware,
u dik it-tip ta 'differenza

252
00:12:34,810 --> 00:12:36,650
biss tmur bogħod naturalment maż-żmien.

253
00:12:36,650 --> 00:12:39,300
>> What we care about hija
l-espressjoni, il-parti

254
00:12:39,300 --> 00:12:42,489
tal-espressjoni li għaddej biex jvarja
bħala input tagħna gets akbar u akbar.

255
00:12:42,489 --> 00:12:45,280
U fil-fatt, fid-dinja reali,
dan huwa dak li qed jiġri dejjem aktar

256
00:12:45,280 --> 00:12:48,330
huwa l-inputs għall-problemi tagħna u
algoritmi huma jkollna akbar.

257
00:12:48,330 --> 00:12:53,470
Allura O big se tkun in-notazzjoni,
in-notazzjoni asintotiku, li aħna biss

258
00:12:53,470 --> 00:12:57,160
użu bħala xjenzjati tal-kompjuter biex jiddeskrivu
il-prestazzjoni, jew il-ħin running,

259
00:12:57,160 --> 00:12:58,130
ta 'algoriżmu.

260
00:12:58,130 --> 00:13:00,800
Allura li nistgħu jqabblu algoritmi
fuq kompjuters differenti miktuba

261
00:13:00,800 --> 00:13:04,170
minn persuni differenti, bl-użu
xi metrika fundamentalment simili

262
00:13:04,170 --> 00:13:07,557
bħall-numru ta 'tqabbil int
tagħmel, jew forsi in-numru ta 'swaps

263
00:13:07,557 --> 00:13:08,140
int tagħmel.

264
00:13:08,140 --> 00:13:11,910
>> Dak li aħna ma tkunx qed tmur biex
għadd huwa l-ammont ta 'ħin

265
00:13:11,910 --> 00:13:13,981
li jgħaddi fuq l-arloġġ
fuq il-ħajt tipikament.

266
00:13:13,981 --> 00:13:16,230
Dak li aħna ma tkunx qed tmur biex ninkwetaw
dwar huwa memorja kemm

267
00:13:16,230 --> 00:13:17,820
inti qed tuża llum fuq
inqas, għalkemm dan huwa

268
00:13:17,820 --> 00:13:19,370
riżors ieħor nistgħu ikejlu.

269
00:13:19,370 --> 00:13:23,610
Aħna ser jippruvaw tibbaża l-analiżi tagħna
biss fuq l-operazzjonijiet bażiċi, dawk,

270
00:13:23,610 --> 00:13:25,930
franchement, li tista 'tara l-aktar viżwalment.

271
00:13:25,930 --> 00:13:30,700
Allura ma xi ħaġa simili O kbira ta 'n
kwadrat, I jsostnu li O ta 'n kwadrat

272
00:13:30,700 --> 00:13:35,820
hija 'fuq marbut fuq l-hekk imsejħa
żmien ta 'tip bużżieqa running.

273
00:13:35,820 --> 00:13:38,820
Fi kliem ieħor, jekk inti
riedu jsostnu li hemm

274
00:13:38,820 --> 00:13:41,370
dan il-limitu massimu fuq kemm
passi 'algoriżmu jista' jieħu,

275
00:13:41,370 --> 00:13:46,240
li għaddej biex tkun fil-O kbir ta 'n
kwadrat f'dan il-każ, l-rbit superjuri.

276
00:13:46,240 --> 00:13:49,710
>> X'jiġri jekk I minflok jibdlu l-
istorja li jkun mhux dwar sort bużżieqa,

277
00:13:49,710 --> 00:13:50,910
iżda dwar dan fuq marbuta.

278
00:13:50,910 --> 00:13:54,030
Tista 'taħseb ta' algoriżmu
li konna ħares lejn diġà

279
00:13:54,030 --> 00:13:59,530
ta 'fuq bound, massima tagħhom
ikejlu ta 'żmien jew l-operazzjonijiet,

280
00:13:59,530 --> 00:14:04,300
tkun jingħad li tmiss
billi n, funzjoni lineari,

281
00:14:04,300 --> 00:14:07,260
mhux waħda kwadratiċi li l mgħawġa?

282
00:14:07,260 --> 00:14:10,780
X'hemm algoritmu li
dejjem tieħu aktar

283
00:14:10,780 --> 00:14:12,860
minn bħall passi n, jew
Passi 2n, jew passi 3N?

284
00:14:12,860 --> 00:14:13,360
Yeah?

285
00:14:13,360 --> 00:14:15,030
>> UDJENZA: Sib l-
akbar numru f'lista?

286
00:14:15,030 --> 00:14:16,930
>> SPEAKER: Perfect, il-konstatazzjoni
l-akbar numru f'lista.

287
00:14:16,930 --> 00:14:18,940
Jekk jien tingħata lista ta '
nies per eżempju,

288
00:14:18,940 --> 00:14:21,440
kull wieħed li qiegħda żżomm numru,
x'inhu n-numru massimu

289
00:14:21,440 --> 00:14:23,770
tal-passi li għandha tieħu me,
persuna raġonevolment intelliġenti,

290
00:14:23,770 --> 00:14:27,530
biex isibu l-persuna akbar f'dik il-lista?

291
00:14:27,530 --> 00:14:28,100
n, id-dritt?

292
00:14:28,100 --> 00:14:31,320
Minħabba li fl-agħar każ, fejn
tista l-akbar valur tkun?

293
00:14:31,320 --> 00:14:32,700
Dritt, it-triq kollha fl-aħħar.

294
00:14:32,700 --> 00:14:34,575
Allura fl-agħar każ
ta 'fuq marbut, I jista

295
00:14:34,575 --> 00:14:36,450
ikollhom imorru-triq kollha
minn hawn u jkunu simili,

296
00:14:36,450 --> 00:14:39,170
oh, hawnhekk numru tmienja,
jew kwalunkwe dak il-valur huwa.

297
00:14:39,170 --> 00:14:41,330
Issa se jkun biss stupid
jekk I jinżammu għaddejjin, right?

298
00:14:41,330 --> 00:14:43,840
Looking for aktar u aktar elementi
jekk l-aħħar minnhom huwa hemmhekk?

299
00:14:43,840 --> 00:14:45,340
Allura żgur, n hija marbuta fuq.

300
00:14:45,340 --> 00:14:47,420
I m'għandhomx bżonn li jieħdu
aktar passi minn dak.

301
00:14:47,420 --> 00:14:51,580
>> Allura dak jekk minflok I propost li
hemm algoritmi f'din id-dinja li

302
00:14:51,580 --> 00:14:57,750
jkollhom żmien running thats
li tmiss mill O kbir ta 'log n, log n?

303
00:14:57,750 --> 00:15:00,390
Fejn ma rajna dan qabel?

304
00:15:00,390 --> 00:15:00,890
Yeah?

305
00:15:00,890 --> 00:15:03,309
>> UDJENZA: Fil-problema ktieb tat-telefon?

306
00:15:03,309 --> 00:15:04,850
SPEAKER: Bħall-problema ktieb tat-telefon.

307
00:15:04,850 --> 00:15:07,754
Liema kienet l-miżura ta 'kemm
ħafna ħin jew kif ħafna tiċrit IT

308
00:15:07,754 --> 00:15:10,170
Domt biex isibu xi ħadd bħal
Mike Smith fil-ktieb tat-telefon?

309
00:15:10,170 --> 00:15:13,212
Aħna sostniet li kien log n, u
anki jekk familjari jew huwa

310
00:15:13,212 --> 00:15:15,170
a imċajpra ftit dak
logarithm jew esponent kien,

311
00:15:15,170 --> 00:15:17,650
biss ftakar li log n
ġeneralment tirreferi għall-proċess,

312
00:15:17,650 --> 00:15:20,790
f'dan il-każ, ta 'diviżjoni
xi ħaġa fil nofs mill-ġdid, u għal darb'oħra,

313
00:15:20,790 --> 00:15:25,790
u għal darb'oħra, u għal darb'oħra, tali li
gets dejjem aktar żgħar kif inti tagħmel dan.

314
00:15:25,790 --> 00:15:28,470
>> Allura log ta n jirreferi, żgur,
għall-eżempju ktieb tat-telefon,

315
00:15:28,470 --> 00:15:32,662
li tfittxija binarju fit-teorija, meta aħna
kellha l-bibien virtwali fuq il-bord,

316
00:15:32,662 --> 00:15:34,370
jew meta Sean kien
tiftix għal xi ħaġa.

317
00:15:34,370 --> 00:15:37,374
Jekk huwa kien użat tfittxija binarja, log n
tkun l fuq marbuta fuq kemm

318
00:15:37,374 --> 00:15:38,040
ħin li jieħu.

319
00:15:38,040 --> 00:15:44,027
Iżda dawk algoritmi li dam fil
log n assunt dak dettall ċavetta?

320
00:15:44,027 --> 00:15:45,360
Li l-lista ġiet magħżula, id-dritt?

321
00:15:45,360 --> 00:15:47,789
Algoritmu tiegħek huwa ħażin jekk
input tiegħek mhix magħżula,

322
00:15:47,789 --> 00:15:49,830
u għadhom inti qed tuża
xi ħaġa bħal tfittxija binarja

323
00:15:49,830 --> 00:15:51,704
għax jista 'jkollok jaqbżu
dritt fuq l-element

324
00:15:51,704 --> 00:15:53,600
mingħajr ma jirrealizza huwa tabilħaqq hemmhekk.

325
00:15:53,600 --> 00:15:55,600
>> Issa dak li jista 'jfisser dan, O kbir ta' waħda?

326
00:15:55,600 --> 00:15:59,117
Dan ma jfissirx li algorithm tiegħek
tieħu waħda u biss pass wieħed,

327
00:15:59,117 --> 00:16:01,200
dan ifisser biss li tieħu
numru kostanti ta 'passi.

328
00:16:01,200 --> 00:16:04,060
Forsi huwa 1, forsi huwa
10, forsi huwa 1,000,

329
00:16:04,060 --> 00:16:07,750
imma hija indipendenti ta '
id-daqs tal-problema.

330
00:16:07,750 --> 00:16:10,850
Ma jimpurtax kemm hu kbir huwa n,
algoritmu ta 'żmien kostanti

331
00:16:10,850 --> 00:16:12,747
dejjem jieħu l-istess numru ta 'passi.

332
00:16:12,747 --> 00:16:15,080
Allura dak li jista 'jkun algoritmu
konna tkellimna dwar jew biss

333
00:16:15,080 --> 00:16:20,418
intuwittivament li jiġi lilek li
dejjem runs fl-hekk imsejħa time kostanti?

334
00:16:20,418 --> 00:16:20,918
Yeah?

335
00:16:20,918 --> 00:16:22,001
>> UDJENZA: Żid żewġ numri.

336
00:16:22,001 --> 00:16:25,320
SPEAKER: Żid żewġ numri,
2 plus 2 ugwali 4, isir.

337
00:16:25,320 --> 00:16:27,227
Allura li jista 'jaħdem, x'iktar?

338
00:16:27,227 --> 00:16:28,560
Kif dwar id-dinja aktar reali, yeah?

339
00:16:28,560 --> 00:16:30,686
>> UDJENZA: Sib l-
ewwel ħaġa f'lista.

340
00:16:30,686 --> 00:16:32,810
SPEAKER: Sib l-ewwel
element f'lista, żgur.

341
00:16:32,810 --> 00:16:34,540
Imxejna ġew effettivament jitkellem
dwar arrays diġà,

342
00:16:34,540 --> 00:16:36,540
kif do ikollok fil-
ewwel element fil-firxa,

343
00:16:36,540 --> 00:16:40,465
ebda kwistjoni kemm żmien il-
array huwa kodiċi C?

344
00:16:40,465 --> 00:16:43,090
Inti biss jużaw bħall-bracket
notazzjoni żero, bam, int hemm.

345
00:16:43,090 --> 00:16:46,120
U fil-fatt arrays, bħala twarrib,
appoġġ ħaġa ġeneralment magħrufa

346
00:16:46,120 --> 00:16:49,240
aċċess bl-addoċċ, aċċess bl-addoċċ
memorja, għaliex inti tista litteralment

347
00:16:49,240 --> 00:16:50,284
jaqbżu għal kull post wieħed.

348
00:16:50,284 --> 00:16:52,700
Nistgħu nagħmlu dan saħansitra aktar sempliċi
nistgħu kontrina għal żero ġimgħa

349
00:16:52,700 --> 00:16:53,900
meta għamilna Scratch.

350
00:16:53,900 --> 00:16:59,707
Kif ħafna ħin ma ħadet għall-
jgħidu blokk fil Scratch biex tesegwixxi?

351
00:16:59,707 --> 00:17:00,790
Just ħin kostanti, id-dritt?

352
00:17:00,790 --> 00:17:03,960
Say xi ħaġa, jgħidu
xi ħaġa, ma jimpurtax

353
00:17:03,960 --> 00:17:07,359
kif Grif kbar dinja hija, huwa dejjem
ser tieħu l-istess ammont ta 'ħin

354
00:17:07,359 --> 00:17:08,490
li sempliċiment ngħid xi ħaġa.

355
00:17:08,490 --> 00:17:11,089
>> Allura dak iż-żmien kostanti,
imma dak in-naħa flip?

356
00:17:11,089 --> 00:17:13,030
Jekk dan kien ta 'fuq
limiti, dak li jekk irridu

357
00:17:13,030 --> 00:17:17,089
biex jiddeskrivu l-limiti aktar baxxi
ta 'algoritmi tagħna running time?

358
00:17:17,089 --> 00:17:19,852
Kważi aħjar każ
potenzjalment, jekk inti se,

359
00:17:19,852 --> 00:17:23,060
għalkemm dawn it-termini jista 'japplika għall-aħjar
każijiet, agħar każijiet, każijiet medja aktar

360
00:17:23,060 --> 00:17:26,359
ġeneralment, imma ejja biss jiffoka
fuq limiti aktar baxxi b'mod aktar ġenerali.

361
00:17:26,359 --> 00:17:31,920
X'hemm algoritmu li għandu
baxxa tal-passi n,

362
00:17:31,920 --> 00:17:33,350
jew passi 2n, jew passi 3N?

363
00:17:33,350 --> 00:17:36,241
Xi fattur ta 'passi n,
thats aktar baxx tagħha marbuta.

364
00:17:36,241 --> 00:17:36,740
Yeah?

365
00:17:36,740 --> 00:17:37,910
>> UDJENZA: sort Bubble?

366
00:17:37,910 --> 00:17:41,610
>> SPEAKER: sort Bubble jieħu
inti passi n minimament, għaliex?

367
00:17:41,610 --> 00:17:42,279
Għaliex huwa li?

368
00:17:42,279 --> 00:17:45,320
Għaliex għandhom li jibdew li jiġu għandek
intuwittivament, anki jekk ma biss

369
00:17:45,320 --> 00:17:46,530
għadhom?

370
00:17:46,530 --> 00:17:47,030
Yeah?

371
00:17:47,030 --> 00:17:47,990
>> UDJENZA: [inaudible].

372
00:17:47,990 --> 00:17:51,652

373
00:17:51,652 --> 00:17:52,360
SPEAKER: Eżattament.

374
00:17:52,360 --> 00:17:55,810
Fl-aħjar xenarju possibbli ta '
sort bużżieqa, u ħafna ta 'algoritmi,

375
00:17:55,810 --> 00:17:58,769
jekk I inti idejn tmien persuni
li huma diġà magħżula,

376
00:17:58,769 --> 00:18:00,560
ikun foolish
għalik, l-algoritmu,

377
00:18:00,560 --> 00:18:02,202
li jmorru quddiem u lura
aktar minn darba, id-dritt?

378
00:18:02,202 --> 00:18:04,285
Minħabba hekk kif inti
walk permezz tal-lista darba,

379
00:18:04,285 --> 00:18:08,090
inti għandek tirrealizza, oh, I magħmula l-ebda
Swaps, din il-lista huwa magħżul, il-ħruġ.

380
00:18:08,090 --> 00:18:09,700
Iżda li għaddej biex tieħu inti n passi.

381
00:18:09,700 --> 00:18:12,033
>> U bil-maqlub, x'hemm ieħor
mod ta 'ħsieb dwar dan?

382
00:18:12,033 --> 00:18:15,240
Sort Bubble huwa omega,
biex ngħidu hekk, ta 'n,

383
00:18:15,240 --> 00:18:19,050
għaliex jekk inti tħares lejn
inqas minn n elementi, liema

384
00:18:19,050 --> 00:18:23,009
hija l-kwistjoni fundamentali hemmhekk?

385
00:18:23,009 --> 00:18:24,550
Inti ma nafx jekk huwa magħżula, id-dritt.

386
00:18:24,550 --> 00:18:26,800
Aħna bnedmin Jista t'għajn lejn tmien
nies u jkunu simili, oh, huwa magħżula,

387
00:18:26,800 --> 00:18:28,430
li ma ħaditx me n passi, iżda għamlet.

388
00:18:28,430 --> 00:18:30,810
Għajnejn tiegħek, anki jekk inti xorta
ta jkollhom kamp kbir ta 'viżjoni,

389
00:18:30,810 --> 00:18:33,184
inti ħares lejn tmien elementi,
inti ħares lejn tmien persuni,

390
00:18:33,184 --> 00:18:34,610
thats tmien passi b'mod effettiv.

391
00:18:34,610 --> 00:18:38,612
U biss jekk I walk permezz tal-kollu
lista do I realizzata, iva, magħżula.

392
00:18:38,612 --> 00:18:41,320
Jekk I stop f'nofsu ħsieb, kollha
dritt, huwa pretty magħżula s'issa,

393
00:18:41,320 --> 00:18:42,520
liema huma l-odds mhuwiex magħżula?

394
00:18:42,520 --> 00:18:44,186
Li algoritmi mhux ser tkun korretta.

395
00:18:44,186 --> 00:18:46,250
Jista 'jkun malajr, iżda mhux korretta.

396
00:18:46,250 --> 00:18:48,500
>> Allura issa għandna mod ta '
jiddeskrivi limiti aktar baxxi,

397
00:18:48,500 --> 00:18:49,710
u dak dwar ħin kostanti?

398
00:18:49,710 --> 00:18:54,565
X'hemm algoritmu li għandha aktar baxxa
marbuta fil-ħin għat-tmexxija tagħha ta 'waħda?

399
00:18:54,565 --> 00:18:58,350
1 pass, 2 passi, 10 passi, iżda
kostanti, indipendenti mill n,

400
00:18:58,350 --> 00:18:59,310
id-daqs tal-input?

401
00:18:59,310 --> 00:19:03,930

402
00:19:03,930 --> 00:19:04,600
Yeah, fid-dahar.

403
00:19:04,600 --> 00:19:05,309
>> UDJENZA: printf?

404
00:19:05,309 --> 00:19:06,183
SPEAKER: X'hemm li?

405
00:19:06,183 --> 00:19:07,184
UDJENZA: printf?

406
00:19:07,184 --> 00:19:07,850
SPEAKER: printf.

407
00:19:07,850 --> 00:19:08,400
OK, żgur.

408
00:19:08,400 --> 00:19:10,720
Allura hija tieħu numru fiss ta 'passi.

409
00:19:10,720 --> 00:19:13,170
And I għandhom now-- issa li
aħna qed jitkellem dwar kodiċi C

410
00:19:13,170 --> 00:19:16,040
u mhux Scratch, xi ħaġa
bħal ngħidu aħna, ma printf,

411
00:19:16,040 --> 00:19:17,710
għandna tibda tikseb attenta.

412
00:19:17,710 --> 00:19:21,090
Minħabba printf ma tieħu
input, huwa string,

413
00:19:21,090 --> 00:19:23,220
u kordi do teknikament jkollhom tul.

414
00:19:23,220 --> 00:19:25,530
Allura jekk aħna issa tixtieq li pick
fuqek, jekk inti ma mind,

415
00:19:25,530 --> 00:19:29,430
teknikament nistgħu jargumentaw li printf
ma tieħu input tul varjabbli,

416
00:19:29,430 --> 00:19:32,270
u żgur jista 'jieħu aktar
żmien biex jistampaw string dan twil,

417
00:19:32,270 --> 00:19:33,560
minn dan twil.

418
00:19:33,560 --> 00:19:36,570
>> Allura dak li jekk nikkunsidraw biss il-
issortjar u tiftix eżempji?

419
00:19:36,570 --> 00:19:40,450
What about Mike Smith fil-telefon
ktieb, jew tfittxija binarja aktar ġenerali?

420
00:19:40,450 --> 00:19:42,220
Fl-aħjar każ, x'jista 'jiġri?

421
00:19:42,220 --> 00:19:45,577
I tiftaħ il-ktieb tat-telefon u, BAM,
hemm numru Mike Smith.

422
00:19:45,577 --> 00:19:46,660
I jistgħu jsejjaħħlu dritt bogħod.

423
00:19:46,660 --> 00:19:49,390
>> Ħadet pass wieħed, forsi żewġ passi,
iżda numru kostanti ta 'passi

424
00:19:49,390 --> 00:19:50,230
jekk sibt xxurtjati.

425
00:19:50,230 --> 00:19:52,570
U franchement, rajna fuq
It-tnejn classmate tiegħek

426
00:19:52,570 --> 00:19:54,710
jiksbu pjuttost xxurtjati darbtejn in fila.

427
00:19:54,710 --> 00:19:57,050
U li kienet tabilħaqq kostanti
darba fi limiti aktar baxxi

428
00:19:57,050 --> 00:20:01,280
fuq l-algoritmu fil-kwistjoni għall-konstatazzjoni
in-numru 50 wara dawk magħluqa

429
00:20:01,280 --> 00:20:01,830
bibien.

430
00:20:01,830 --> 00:20:06,400
>> Issa, bħala twarrib, jekk inti tiskopri
li kemm O big, l illegat fuq,

431
00:20:06,400 --> 00:20:09,310
u omega, l-aktar baxx marbut,
huma wieħed fl-istess, li

432
00:20:09,310 --> 00:20:11,830
huwa l-istess formula fl
parentesi, inti tista 'wkoll

433
00:20:11,830 --> 00:20:15,170
jgħidu, biss biex tkun fancy,
li xi ħaġa hija fil theta

434
00:20:15,170 --> 00:20:18,270
ta n jew theta ta 'xi valur ieħor.

435
00:20:18,270 --> 00:20:20,661
Dan ifisser biss meta big
O u omega huma l-istess.

436
00:20:20,661 --> 00:20:21,910
Issa dak dwar sort għażla?

437
00:20:21,910 --> 00:20:23,400
Ejja jużaw dan vokabolarju ġdid.

438
00:20:23,400 --> 00:20:27,407
Fil sort għażla, liema kienu aħna
tagħmel għal darb'oħra, u għal darb'oħra, u għal darb'oħra?

439
00:20:27,407 --> 00:20:29,990
I kien għaddej quddiem u lura permezz
il-lista, tfittex għal min?

440
00:20:29,990 --> 00:20:33,260

441
00:20:33,260 --> 00:20:34,730
L-iżgħar numru.

442
00:20:34,730 --> 00:20:37,560
>> Allura kif ħafna passi, kif
ħafna paraguni ma I

443
00:20:37,560 --> 00:20:43,250
ikollhom jagħmlu sabiex insemmu li
l-element iżgħar fil-lista kien?

444
00:20:43,250 --> 00:20:44,437
n minus 1, id-dritt?

445
00:20:44,437 --> 00:20:47,770
Għaliex jekk I biss tibda bil-wieħed jien
mogħtija u I tibda jqabbel lilu jew lilha,

446
00:20:47,770 --> 00:20:49,519
imbagħad lilu jew lilha, lilu
jew tagħha, lilu jew lilha, I

447
00:20:49,519 --> 00:20:52,010
tista 'biss par elementi
flimkien n minus 1 darbiet.

448
00:20:52,010 --> 00:20:55,630
Allura għażla sort simili tieħu
n minus 1 passi l-ewwel darba.

449
00:20:55,630 --> 00:20:59,540
>> Kemm passi ma jieħdu me biex
isibu l-tieni l-iżgħar element?

450
00:20:59,540 --> 00:21:02,920
n minus 2, għaliex jien qed mutu
jekk I iżommu tħares lejn l-istess nies

451
00:21:02,920 --> 00:21:06,280
ġdid jekk stajt diġà magħżula lilu
jew tagħha u tpoġġihom fil-post tagħhom.

452
00:21:06,280 --> 00:21:09,270
U t-tielet pass, n
minus 3, allura n nieqes 4.

453
00:21:09,270 --> 00:21:11,020
Rajna dan il-mudell
qabel, u tabilħaqq

454
00:21:11,020 --> 00:21:13,460
għażla sort simili
għandha fuq bound

455
00:21:13,460 --> 00:21:16,210
ta n kwadrat jekk nagħmlu up li għadd totali.

456
00:21:16,210 --> 00:21:19,790
X'inhu inferjuri, sort għażla tagħha?

457
00:21:19,790 --> 00:21:25,350
Minimament, kemm għandu għażla ħin
sort tieħu, kif aħna ddefinietu nhar it-Tnejn?

458
00:21:25,350 --> 00:21:29,370

459
00:21:29,370 --> 00:21:30,490
Tipproponi żewġ għażliet.

460
00:21:30,490 --> 00:21:32,360
Forsi huwa n, bħal qabel.

461
00:21:32,360 --> 00:21:35,040
Forsi huwa n kwadrat, kif
issa huwa kif l-marbuta fuq.

462
00:21:35,040 --> 00:21:35,874
>> UDJENZA: n kwadrat.

463
00:21:35,874 --> 00:21:36,664
SPEAKER: n kwadrat.

464
00:21:36,664 --> 00:21:37,368
Għaliex?

465
00:21:37,368 --> 00:21:40,060
>> UDJENZA: Minħabba li għandek
sabiex tiddefinixxi [inaudible].

466
00:21:40,060 --> 00:21:41,510
>> SPEAKER: Eżattament.

467
00:21:41,510 --> 00:21:45,077
Mill-inqas I kif definit sort għażla
kien pjuttost naive, iżommu għaddejjin,

468
00:21:45,077 --> 00:21:46,160
isibu l-element iżgħar.

469
00:21:46,160 --> 00:21:47,770
Mur darb'oħra, isibu l-element iżgħar.

470
00:21:47,770 --> 00:21:49,490
Mur darb'oħra, isibu l-element iżgħar.

471
00:21:49,490 --> 00:21:51,700
M'hemm l-ebda tip ta '
ottimizzazzjoni fil hemm li

472
00:21:51,700 --> 00:21:54,350
tista let me abort wara
biss n jew hekk passi.

473
00:21:54,350 --> 00:21:57,080
Allura fil-fatt, l-għażla
sort, omega ta n kwadrat.

474
00:21:57,080 --> 00:22:00,667
>> What about sort inserzjoni, fejn I ħa
li I kien mogħti, u mbagħad I plopped lilu

475
00:22:00,667 --> 00:22:01,750
jew tagħha fil-post dritt?

476
00:22:01,750 --> 00:22:04,958
Imbagħad I ipproċediet għat-tieni persuna,
plopped lilu jew lilha fil-post dritt.

477
00:22:04,958 --> 00:22:07,910
Imbagħad il-persuna li jmiss, plopped
lilu jew lilha fil-post dritt.

478
00:22:07,910 --> 00:22:10,537
Avviż li dan huwa ferm
lineari, biex ngħidu hekk.

479
00:22:10,537 --> 00:22:12,620
Jien linja dritta, jien
mhux se quddiem u lura,

480
00:22:12,620 --> 00:22:16,080
Stajt qatt tħares lura verament, imma
dak li qed jiġri meta I daħħal lilu

481
00:22:16,080 --> 00:22:20,302
jew tagħha fil-bidu ta '
il-lista kif għamilna nhar it-Tnejn?

482
00:22:20,302 --> 00:22:21,010
Dak li qed jiġri?

483
00:22:21,010 --> 00:22:21,510
Yeah?

484
00:22:21,510 --> 00:22:23,122
UDJENZA: [inaudible].

485
00:22:23,122 --> 00:22:24,830
SPEAKER: Yeah, li
kien il-qabda, id-dritt?

486
00:22:24,830 --> 00:22:26,746
Inti tista recall minn
klassi tiegħek, jekk huma

487
00:22:26,746 --> 00:22:29,670
kienu qed jagħmlu kull moviment ma
saqajn tagħhom, li kien operazzjoni.

488
00:22:29,670 --> 00:22:33,610
Mela jekk kien hemm tliet persuni hawn u
il-persuna ġdida kienet ikkontrollata mod hemmhekk,

489
00:22:33,610 --> 00:22:37,360
fuq stadju twil bħal dan, żgur, huwa
jew hi tista 'biss tmur għall-aħħar ħafna.

490
00:22:37,360 --> 00:22:40,074
Imma jekk aħna qed jaħsbu dwar
kompjuter u l-firxa ta 'memorja,

491
00:22:40,074 --> 00:22:41,990
dawn in-nies huma għaddejjin
li jkollhom biex shuffle fuq

492
00:22:41,990 --> 00:22:43,260
biex tagħmel spazju għal dik il-persuna.

493
00:22:43,260 --> 00:22:46,930
U hekk li n minus 1 shufflings,
n minus 2 shufflings, n

494
00:22:46,930 --> 00:22:50,660
minus 3 shufflings huwa biss tip ta '
jiġri lura lili, mhux quddiem lili

495
00:22:50,660 --> 00:22:52,710
bħal qabel, f'xi sens.

499
00:22:52,557 --> 00:22:54,640
Issa bħala twarrib, u bħala
inti tista raw online

500
00:22:54,640 --> 00:22:57,699
jekk tibda poking madwar dwar
xorta, hemm dawk li tant differenti

501
00:22:57,699 --> 00:22:59,490
hemmhekk, xi wħud minnhom
aħjar minn oħrajn.

502
00:22:59,490 --> 00:23:02,200
Tabilħaqq, bogosort hija waħda
li l-xorta ta 'gost tfittex up.

503
00:23:02,200 --> 00:23:06,650
Bogosort jieħu sett ta '
numri jew jgħidu gverta ta 'karti,

504
00:23:06,650 --> 00:23:09,870
saltwarjament shuffles minnhom, u
kontrolli jekk dawn qed magħżula.

505
00:23:09,870 --> 00:23:12,130
U jekk le, ma darb'oħra.

506
00:23:12,130 --> 00:23:14,140
U jekk le, ma darb'oħra.

507
00:23:14,140 --> 00:23:15,440
Jekk le, ma darb'oħra.

508
00:23:15,440 --> 00:23:17,060
Oerhört stupid.

509
00:23:17,060 --> 00:23:19,520
>> U fil-fatt, jekk inti taqra
bħall-artikolu Wikipedia,

510
00:23:19,520 --> 00:23:21,200
laqam tiegħu huwa tip stupid.

511
00:23:21,200 --> 00:23:25,180
Hija eventwalment se taħdem,
nisperaw, jingħataw żmien biżżejjed,

512
00:23:25,180 --> 00:23:28,240
iżda dak l-ammont ta 'ħin
jista 'jieħu żmien pjuttost twil.

513
00:23:28,240 --> 00:23:31,650
Mela jekk I jistgħu, ejja affarijiet veloċità
up mill-eżempju Mary Beth qabel,

514
00:23:31,650 --> 00:23:35,150
billi ftit elementi aktar,
iżda żewġ proċessuri aktar.

515
00:23:35,150 --> 00:23:37,100
Żewġ persuni, jekk inti
ma mind tgħaqqad lili.

516
00:23:37,100 --> 00:23:40,972
Kif madwar 1 hawn fuq, u
ejja go-- ebda waħda hemmhekk?

517
00:23:40,972 --> 00:23:41,722
Ħadd hemmhekk?

518
00:23:41,722 --> 00:23:42,221
OK.

519
00:23:42,221 --> 00:23:44,190
Inti ma l-iswed
shirt, iva, come fuq l isfel.

520
00:23:44,190 --> 00:23:45,000
Kull dritt, x'hemm isem tiegħek?

521
00:23:45,000 --> 00:23:45,720
>> UDJENZA: Peter.

522
00:23:45,720 --> 00:23:46,100
>> SPEAKER: X'hemm li?

523
00:23:46,100 --> 00:23:46,766
>> UDJENZA: Peter.

524
00:23:46,766 --> 00:23:49,450
SPEAKER: Peter, David, sbieħ li jissodisfaw inti.

525
00:23:49,450 --> 00:23:53,670
Kull dritt, għandna Peter hawn, jekk inti
tixtieq li ġejjin fuq il-mejda hawn fuq.

526
00:23:53,670 --> 00:23:54,550
U x'hemm isem tiegħek?

527
00:23:54,550 --> 00:23:55,216
>> UDJENZA: Elena.

528
00:23:55,216 --> 00:23:55,970
SPEAKER: Elena.

529
00:23:55,970 --> 00:23:57,030
OK, sbieħ li jissodisfaw inti.

530
00:23:57,030 --> 00:23:58,060
Elena jilħqu Peter.

531
00:23:58,060 --> 00:23:59,170
Pietru, Elena.

532
00:23:59,170 --> 00:24:02,290
U aħna bzonn Andrew
up hawnhekk ukoll, jekk jogħġbok.

533
00:24:02,290 --> 00:24:06,107
U l-isfida tiegħek huwa għaddej
li jkun biex issolvi gverta ta 'karti.

534
00:24:06,107 --> 00:24:08,190
U jekk familjari, gverta
ta 'karti għandhom finalment

535
00:24:08,190 --> 00:24:11,064
jiġu magħżula ftit xi ħaġa bħal
dan fejn aħna ser nagħmlu l-klabbs, imbagħad

536
00:24:11,064 --> 00:24:13,660
l spades, allura l-qlub u
djamanti, minn ass bħala waħda,

537
00:24:13,660 --> 00:24:15,570
it-triq kollha sa king.

538
00:24:15,570 --> 00:24:20,890
>> Il-kards Jien ser jagħtuk
ser ikunu 52 fil-kwantità.

539
00:24:20,890 --> 00:24:23,160
Aħna ser simili
ħin li inti, fi ftit mument.

540
00:24:23,160 --> 00:24:26,410
Aħna ser tarmi Andrew
up fuq l-iskrin hawn,

541
00:24:26,410 --> 00:24:28,170
sabiex jaraw kif inti tagħmel dan.

542
00:24:28,170 --> 00:24:31,070
U hekk li dan kollu
huwa l-aktar viżibbli,

543
00:24:31,070 --> 00:24:33,490
dawn huma l-cards sibt fuq Amazon.

544
00:24:33,490 --> 00:24:42,861
Allura huma diġà saltwarjament
magħżula, u aħna qed tmur biex darba inti.

545
00:24:42,861 --> 00:24:44,610
U aħna qed tmur biex
jżommha reali dan iż-żmien,

546
00:24:44,610 --> 00:24:47,820
hekk aħna qed tmur biex tipprova pressjoni inti
għax inkella dan se tikseb tedious

547
00:24:47,820 --> 00:24:48,460
malajr.

548
00:24:48,460 --> 00:24:53,860
Jekk inti tista 'tipproċedi biex issolvi 52
elementi flimkien permezz ta 'xi mezzi, issa.

549
00:24:53,860 --> 00:25:04,710

550
00:25:04,710 --> 00:25:07,180
>> U għal darb'oħra, kif aħna watch dawn
guys jagħmlu dak, fl-aħħar

551
00:25:07,180 --> 00:25:10,200
se jipproduċi ovvju
riżultat, jaħsbu dwar verament

552
00:25:10,200 --> 00:25:12,962
kif dawn qed kull nagħmilx hekk,
kif inti tista tiddeskrivi lilha.

553
00:25:12,962 --> 00:25:15,045
Minħabba darb'oħra, dawn huma
kollha proċessi, algoritmi

554
00:25:15,045 --> 00:25:17,090
li nieħdu għall mogħtija bħala bniedem.

555
00:25:17,090 --> 00:25:22,349
Imma inti probabilment ħadthom twil kellhom
intwizzjoni, twil qabel inti anki

556
00:25:22,349 --> 00:25:24,390
ħsibt dwar teħid ta '
klassi xjenza tal-kompjuter li inti

557
00:25:24,390 --> 00:25:27,223
seta 'kellhom l-intuwizzjoni ma
li sabiex isolvu problemi bħal dan.

558
00:25:27,223 --> 00:25:29,560
Imma ladarba inti tirrikonoxxi
il-mudelli u tibda

559
00:25:29,560 --> 00:25:32,407
biex jifformalizzaw il-passi li bihom
int jissolvew dawn il-problemi,

560
00:25:32,407 --> 00:25:35,490
inti ser issib li inti tista 'ssolvi ħafna
aktar interessanti u ferm aktar kumplessa

561
00:25:35,490 --> 00:25:39,190
problemi malajr.

562
00:25:39,190 --> 00:25:42,351
Allura xi ħadd mill-udjenza, dak li huwa
inqas element wieħed ta 'l-algoritmu

563
00:25:42,351 --> 00:25:43,350
li dawn qed jużaw hawn?

564
00:25:43,350 --> 00:25:44,275
>> UDJENZA: [inaudible]

565
00:25:44,275 --> 00:25:45,150
SPEAKER: X'hemm li?

566
00:25:45,150 --> 00:25:47,062
UDJENZA: Billi suit.

567
00:25:47,062 --> 00:25:47,770
SPEAKER: Billi suit.

568
00:25:47,770 --> 00:25:50,630
Allura l-ewwel huma jaqgħu kollha
kollha tal-djamanti flimkien

569
00:25:50,630 --> 00:25:52,560
jidher, kollha tal-
qlub flimkien jidher,

570
00:25:52,560 --> 00:25:56,520
u oħrajn, mingħajr rispett
għall-numri fuq il-karti.

571
00:25:56,520 --> 00:26:00,900
U issa jidhru, per eżempju,
li jiġu issortjar lilhom mill-għadd.

572
00:26:00,900 --> 00:26:06,870

573
00:26:06,870 --> 00:26:08,910
Tajjeb ħafna.

574
00:26:08,910 --> 00:26:12,370
>> Kull dritt, hekk dak li għaddej biex
tkun il-pass finali allura hawnhekk?

575
00:26:12,370 --> 00:26:16,950
Ladarba għandna erba suits magħżula, liema
do we bżonn tagħmel biex l-erba 'munzelli

576
00:26:16,950 --> 00:26:20,059
sabiex jinkiseb wieħed
gverta magħżula, pjuttost sempliċi?

577
00:26:20,059 --> 00:26:21,350
Għalhekk għandna bżonn li jingħaqdu mill-ġdid.

578
00:26:21,350 --> 00:26:25,160
>> Allura hemm idea interessanti li
darb'oħra, daresay, huwa ħafna intuwittivi saħansitra

579
00:26:25,160 --> 00:26:28,140
jekk int qatt ma seta 'slapped
dak it-tip ta 'tikketta fuqha.

580
00:26:28,140 --> 00:26:31,900
Dan il-kunċett fundamentali ta 'diviżjoni
il-problema ma fil nofs il-ħin,

581
00:26:31,900 --> 00:26:33,410
iżda mill-inqas f'erba 'biċċiet.

582
00:26:33,410 --> 00:26:36,810
Solving pretty ħafna
problemi fundamentalment identiċi

583
00:26:36,810 --> 00:26:40,480
fil-iżolament ta 'xulxin,
u mbagħad jingħaqdu r-riżultati.

584
00:26:40,480 --> 00:26:46,940

585
00:26:46,940 --> 00:26:50,140
U, eċċellenti, isir.

586
00:26:50,140 --> 00:26:52,140
Kull dritt, tond big
ta applause, jekk nistgħu.

587
00:26:52,140 --> 00:26:56,480
>> [Applause]

588
00:26:56,480 --> 00:26:59,740
>> SPEAKER: Għandi l-ebda idea dak li inti ser
do ma 'dawn, iżda hawnhekk tmur.

589
00:26:59,740 --> 00:27:01,690
Grazzi tant.

590
00:27:01,690 --> 00:27:04,660
Mela ejja ara, żewġ minuti
u tmien sekondi,

591
00:27:04,660 --> 00:27:07,490
jekk inti tixtieq li jikkontesta ħbieb tiegħek.

592
00:27:07,490 --> 00:27:12,160
X'inhu allura huwa ser
tkun tieħu l bogħod minn din

593
00:27:12,160 --> 00:27:13,830
li nistgħu lieva aktar ġenerali?

594
00:27:13,830 --> 00:27:16,080
Ukoll, think lura għal
dan firxa ta 'numri,

595
00:27:16,080 --> 00:27:19,060
u think lura issa għal xi wħud mill-
pseudocode konna bil-miktub fil-passat,

596
00:27:19,060 --> 00:27:22,080
u dan kien il-pseudocode għall
tissolva l-problema ktieb tat-telefon.

597
00:27:22,080 --> 00:27:25,150
Biha fil pseudocode I
enumerati b'mod aktar metodiku

598
00:27:25,150 --> 00:27:28,400
ta jiddeskrivi kif I għamlet intuwittivi ħafna
algoritmu tal-bniedem tal tiddividi l-phone

599
00:27:28,400 --> 00:27:31,650
ktieb fil nofs, irrepeti, irrepeti, irrepeti,
sal I issib xi ħadd bħal Mike Smith,

600
00:27:31,650 --> 00:27:33,790
jekk huwa tabilħaqq fil-ktieb tat-telefon.

601
00:27:33,790 --> 00:27:37,610
>> Imma I tip ta użati dak I ser sejħa
approċċ iterattiv ħafna hawn,

602
00:27:37,610 --> 00:27:42,160
b'mod partikolari avviż linja 8 u l-linja 11.

603
00:27:42,160 --> 00:27:46,750
Dawk huma evidenza ta 'iterattiv
approċċ, approċċ looping,

604
00:27:46,750 --> 00:27:49,040
għaliex dan huwa eżattament
l-imġieba li jinduċu.

605
00:27:49,040 --> 00:27:52,910
Dawk il-linji kemm jgħidu mur
linja tlieta, u inti tista 'tip ta'

606
00:27:52,910 --> 00:27:55,140
jaħsbu ta 'dak fil tiegħek
għajnejn moħħ bħala loop.

607
00:27:55,140 --> 00:27:59,080
Huwa tghidlek biex tmur lura up pass
tlieta u rrepeti, għal darb'oħra, u għal darb'oħra,

608
00:27:59,080 --> 00:28:00,010
u għal darb'oħra.

609
00:28:00,010 --> 00:28:04,410
>> Imma dak jekk aħna lieva idea ewlenija
hawnhekk li aħna ma l-aħħar darba,

610
00:28:04,410 --> 00:28:10,280
u jissimplifikaw linja 8 u
linja 11 u l-ġirien tagħhom

611
00:28:10,280 --> 00:28:12,840
bħala biss dan, bl-isfar.

612
00:28:12,840 --> 00:28:16,480
Mhuwiex fundamentalment tqassir
l pseudocode ħafna,

613
00:28:16,480 --> 00:28:20,530
imma hija bidla fundamentali tal
in-natura ta algoritmu tiegħi.

614
00:28:20,530 --> 00:28:24,220
Dak li jien issa tgħid
fil-pass 7, fil-pass 10,

615
00:28:24,220 --> 00:28:29,140
huwa ta 'tiftix għal Mike
bl-istess mod eżatt,

616
00:28:29,140 --> 00:28:31,580
iżda biss fil-xellug
nofs jew il-nofs tal-lemin.

617
00:28:31,580 --> 00:28:33,420
>> Allura fi kliem ieħor, jekk
I tibda minn pass wieħed,

618
00:28:33,420 --> 00:28:36,150
pick up ktieb tat-telefon, miftuħa għall middle
tal-ktieb tat-telefon, tħares lejn l-ismijiet,

619
00:28:36,150 --> 00:28:39,010
jekk Smith hija fost
isem, is-sejħa Mike, inkella

620
00:28:39,010 --> 00:28:44,340
jekk Smith tkun qabel fil-ktieb, pass seba
tfittxija għal Mike fil nofs tax-xellug tal-ktieb.

621
00:28:44,340 --> 00:28:47,130
Iżda dan it-tip ta jħoss simili
huwa li jħallu me jiddendlu, right?

622
00:28:47,130 --> 00:28:49,240
Fil isfar, huwa
istruzzjoni, imma kif do I

623
00:28:49,240 --> 00:28:51,870
tfittxija għall Mike fil-xellug
nofs il-ktieb tat-telefon?

624
00:28:51,870 --> 00:28:54,210
Fejn nista 'jkollhom
algoritmu li magħhom I

625
00:28:54,210 --> 00:28:57,100
tista 'tfittex għal xi ħadd bħal Mike Smith?

626
00:28:57,100 --> 00:28:58,980
Ukoll, huwa tluq magħna fil-wiċċ.

627
00:28:58,980 --> 00:29:03,090
I jistgħu litteralment jużaw l-istess eżatt
programm effettivament tmur sal-quċċata

628
00:29:03,090 --> 00:29:06,490
darb'oħra u ri-running
l-istess linji ta 'kodiċi.

629
00:29:06,490 --> 00:29:10,610
>> Allura anke jekk dan għandu jħossu
bħal daqsxejn ta 'definizzjoni ċiklika

630
00:29:10,610 --> 00:29:13,480
fejn int twieġeb xi ħadd huwa
mistoqsija bi ftit tip ta 'tistaqsi

631
00:29:13,480 --> 00:29:15,990
l-istess kwistjoni mill-ġdid,
bħal għaliex, għaliex, għaliex?

632
00:29:15,990 --> 00:29:21,580
Ir-realtà hija għaliex aħna ħadthom hard kodifikati
koppja ta 'linji speċjali, pass 4,

633
00:29:21,580 --> 00:29:25,320
li hija jekk, u 12 pass, li
huwa effettivament fergħa ieħor,

634
00:29:25,320 --> 00:29:30,120
għaliex għandna dawk il-miżuri stopgap,
dan algoritmu se jintemm jekk irridu

635
00:29:30,120 --> 00:29:32,050
isibu Mike, jew jekk aħna ma.

636
00:29:32,050 --> 00:29:36,810
Iżda fil-pass 7 u 10 issa, għandna
dak li aħna ser sejħa algoritmu rikursivi.

637
00:29:36,810 --> 00:29:40,420
U recursion huwa tabilħaqq idea qawwija
thats mind ftit liwi fl-ewwel,

638
00:29:40,420 --> 00:29:42,500
li aħna issa jista 'japplika kif ġej.

639
00:29:42,500 --> 00:29:46,600
>> Jingħaqdu sort se jkun l-aħħar tip li
nħarsu lejn, għall-inqas fil-klassi formalment.

640
00:29:46,600 --> 00:29:50,040
U huwa fundamentalment differenti
minn dawk it-tliet aħħar, u ċertament

641
00:29:50,040 --> 00:29:52,140
aħħar erbgħa jekk aħna jinkludu bogosort.

642
00:29:52,140 --> 00:29:54,810
Hawn il-pseudocode għall tip jingħaqdu.

643
00:29:54,810 --> 00:30:00,170
Meta fuq input ta 'elementi n, hekk mogħtija
firxa ta 'daqs n, jekk n hija inqas minn 2,

644
00:30:00,170 --> 00:30:01,040
ritorn.

645
00:30:01,040 --> 00:30:03,610
Allura għaliex għandi li
sanità tiċċekkja l-ewwel?

646
00:30:03,610 --> 00:30:09,477
X'hemm-implikazzjoni jekk I inti idejn
firxa li t-tul n huwa inqas minn 2?

647
00:30:09,477 --> 00:30:11,060
Huwa diġà magħżula, ovvjament, id-dritt?

648
00:30:11,060 --> 00:30:13,640
Minħabba li l-lista jew għandha
element wieħed, li huwa trivially

649
00:30:13,640 --> 00:30:15,180
magħżula għaliex dan huwa
l-unika ħaġa hemmhekk.

650
00:30:15,180 --> 00:30:18,138
Or, huwa ta 'daqs żero li jfisser
hemm xejn biex issolvi, hekk min-natura

651
00:30:18,138 --> 00:30:18,720
dan huwa magħżul.

652
00:30:18,720 --> 00:30:20,410
Hemm biss xejn ħażin hemmhekk.

653
00:30:20,410 --> 00:30:22,310
Allura dak hekk imsejjaħ każ bażi tagħna.

654
00:30:22,310 --> 00:30:24,440
>> Dan huwa simili fl-ispirtu
għal dak li għamilna ma 'Mike.

655
00:30:24,440 --> 00:30:26,023
Jekk l Mike fil-ktieb tat-telefon, jsejjaħħlu.

656
00:30:26,023 --> 00:30:27,740
Jekk hu ma jkunx hemm, tagħti up.

657
00:30:27,740 --> 00:30:31,240
Huwa hekk imsejħa każ bażi, sabiex tagħmel żgur li
dan algoritmu fl-aħħar tal-ġurnata

658
00:30:31,240 --> 00:30:33,540
se tieqaf f'ċerti ċirkostanzi.

659
00:30:33,540 --> 00:30:37,890
>> Iżda hawn l-qabża ta 'fidi issa, inkella,
sort in-nofs xellugi tal-elementi,

660
00:30:37,890 --> 00:30:39,740
imbagħad sort-dritt
nofs l-elementi,

661
00:30:39,740 --> 00:30:41,189
u mbagħad jingħaqdu in-nofsijiet magħżula.

662
00:30:41,189 --> 00:30:43,230
U hawn fejn iħoss
simili aħna qed Copping out.

663
00:30:43,230 --> 00:30:46,900
Stajt talab li inti sort
n elementi, u jien

664
00:30:46,900 --> 00:30:50,712
qal, OK, tagħmel dan billi issortjar
ix-xellug u l-għażla dritt.

665
00:30:50,712 --> 00:30:52,420
Imma I am qal wieħed
Ħaġa oħra, u dan

666
00:30:52,420 --> 00:30:55,530
hija t-tema ewlenija jidher
fil-intwizzjoni s'issa,

667
00:30:55,530 --> 00:30:57,380
hemm dan it-tielet pass ta 'għaqda.

668
00:30:57,380 --> 00:31:00,430
Liema anki jekk
jidher hekk dumb fl-ispirtu,

669
00:31:00,430 --> 00:31:02,320
bħal biss jingħaqdu affarijiet
flimkien, jidher

670
00:31:02,320 --> 00:31:05,380
li jkun pass ewlieni lejn il-
mill-ġdid ta 'żewġ problemi li

671
00:31:05,380 --> 00:31:07,330
kienu maqsuma finalment nofs.

672
00:31:07,330 --> 00:31:12,090
>> Allura jingħaqdu sort, ejja tagħmel dan, jekk inti taf
Humer lili, ma 'wieħed turija aktar,

673
00:31:12,090 --> 00:31:14,730
biss hekk li aħna għandna xi
numri li jaħdmu magħhom.

674
00:31:14,730 --> 00:31:19,470
Nista jiskambjaw tmien stress
blalen għal tmien persuni?

675
00:31:19,470 --> 00:31:29,320
Kull dritt, kif dwarek tlieta, int erbgħa
f'din it-taqsima, ħamsa, sitta, u ejja

676
00:31:29,320 --> 00:31:30,720
do 7, 8, come fuq up.

677
00:31:30,720 --> 00:31:35,120

678
00:31:35,120 --> 00:31:36,520
OK, yeah OK.

679
00:31:36,520 --> 00:31:38,640
Minus 8, hemm immorru, flimkien ma '1.

680
00:31:38,640 --> 00:31:39,150
Eċċellenti.

681
00:31:39,150 --> 00:31:42,000
Kull dritt come fuq up, ejja
malajr jagħtik numri.

682
00:31:42,000 --> 00:31:50,800
Numru tnejn, numru tlieta, numru erbgħa,
numru b'ħames, sitta, seba ', u tmienja.

683
00:31:50,800 --> 00:31:52,140
Jien għamilt tmien korrett dan iż-żmien.

684
00:31:52,140 --> 00:31:56,390
>> OK, sabiex jimxi 'l quddiem jekk inti tista', u
ejja sort fl-ordni oriġinali

685
00:31:56,390 --> 00:31:59,810
li kellna bieraħ li ħares
bħal dan, jekk inti ma mind.

686
00:31:59,810 --> 00:32:03,620
U ejja tagħmel dan quddiem il-mejda.

687
00:32:03,620 --> 00:32:06,510
Kull dritt, hekk jingħaqdu sort.

688
00:32:06,510 --> 00:32:08,820
Dan huwa fejn huwa għaddej
biex tikseb it-tip ta 'interessanti,

689
00:32:08,820 --> 00:32:12,800
minħabba I jidhru li tkun tagħti myself
tant inqas informazzjoni tal-lum.

690
00:32:12,800 --> 00:32:15,149
>> Allura jingħaqdu sort l-ewwel nett
fuq l-input ta 'elementi n,

691
00:32:15,149 --> 00:32:18,440
u hija ovvjament mhux inqas minn tnejn, huwa
tmienja, so I jkollhom xi xogħol aktar x'isir.

692
00:32:18,440 --> 00:32:21,140
Allura issa mentalment aħna bħala klassi
huma issa fil-fergħa inkella,

693
00:32:21,140 --> 00:32:22,540
li jfisser tliet passi.

694
00:32:22,540 --> 00:32:25,017
L-ewwel, I jkollhom biex issolvi l-
nofs tax-xellug ta 'l-elementi.

695
00:32:25,017 --> 00:32:26,350
Allura kif nista tmur dwar kif isir dan?

696
00:32:26,350 --> 00:32:28,950
Well, jien ser tip ta '
mentalment jaqsam il-lista hawn,

697
00:32:28,950 --> 00:32:30,700
inti ma għandekx
fiżikament jimxu, u jien

698
00:32:30,700 --> 00:32:33,180
ser tiffoka biss fuq il-
nofs tax-xellug ta 'l-elementi hawn.

699
00:32:33,180 --> 00:32:36,770
Allura kif nista tmur dwar issortjar
lista issa ta 'daqs erba?

700
00:32:36,770 --> 00:32:38,730
X'hemm algoritmu tiegħi?

701
00:32:38,730 --> 00:32:42,580
Ewwel I jivverifika hu n inqas minn tnejn, l-ebda,
so I jipproċedu għall-blokk ieħor ġdid.

702
00:32:42,580 --> 00:32:43,900
Sort xellug nofs ta 'elementi.

703
00:32:43,900 --> 00:32:45,608
>> Allura issa u għal darb'oħra, mentalment,
u dan huwa fejn

704
00:32:45,608 --> 00:32:49,550
inti għandek jakkumulaw ħafna ta '
istorja mentali, jekk inti se.

705
00:32:49,550 --> 00:32:51,940
Issa jien issortjar ix-xellug
nofs in-nofs xellugi.

706
00:32:51,940 --> 00:32:57,000
Kull dritt, hekk issa I call istess jingħaqdu tiegħi
issortjar algoritmu, huwa n anqas minn tnejn?

707
00:32:57,000 --> 00:33:00,590
Le, huwa tnejn, so I jkollhom biex issolvi
in-nofs xellugi, u l-nofs tal-lemin.

708
00:33:00,590 --> 00:33:02,042
So here we go, sort l-nofs tax-xellug.

709
00:33:02,042 --> 00:33:03,750
Għaliex ma inti biss
tieħu pass 'il quddiem.

710
00:33:03,750 --> 00:33:04,415
X'hemm isem tiegħek?

711
00:33:04,415 --> 00:33:04,860
>> UDJENZA: Darren.

712
00:33:04,860 --> 00:33:05,260
>> SPEAKER: Dan.

713
00:33:05,260 --> 00:33:06,040
Dan żiedet l quddiem.

714
00:33:06,040 --> 00:33:06,748
>> UDJENZA: Darren.

715
00:33:06,748 --> 00:33:09,000
SPEAKER: Darren, isir.

716
00:33:09,000 --> 00:33:10,090
Ridt ngħid Darren jew Dan?

717
00:33:10,090 --> 00:33:10,550
>> UDJENZA: Darren.

718
00:33:10,550 --> 00:33:11,216
>> SPEAKER: Darren.

719
00:33:11,216 --> 00:33:14,422
OK, Darren żiedet
quddiem u huwa issa huwa magħżul.

720
00:33:14,422 --> 00:33:16,130
U dan huwa kważi
pretensjoni inane, id-dritt?

721
00:33:16,130 --> 00:33:18,862
I ma verament jidhru li huma kisba
xejn, imma ejja tipproċedi.

722
00:33:18,862 --> 00:33:20,820
Issa let me sort-dritt
nofs mill-elementi.

723
00:33:20,820 --> 00:33:21,200
X'hemm isem tiegħek?

724
00:33:21,200 --> 00:33:21,690
>> UDJENZA: Luqa.

725
00:33:21,690 --> 00:33:22,273
>> SPEAKER: Luqa.

726
00:33:22,273 --> 00:33:23,400
Come on, pass 'il quddiem.

727
00:33:23,400 --> 00:33:25,640
Magħmul, I magħżula Luqa.

728
00:33:25,640 --> 00:33:28,570
Il-half xellug issa huwa magħżul u
il-half dritt issa huwa magħżul,

729
00:33:28,570 --> 00:33:30,770
iżda għal darb'oħra, hemm pass ewlieni hawnhekk.

730
00:33:30,770 --> 00:33:32,940
What do I bżonn tagħmel li jmiss?

731
00:33:32,940 --> 00:33:33,941
Jingħaqdu l-nofsijiet magħżula.

732
00:33:33,941 --> 00:33:36,648
Issa aħna qed tmur li jkollhom biss
kulħadd quddiem u lura b'dan il-mod,

733
00:33:36,648 --> 00:33:38,620
minħabba I tip ta 'bżonn
xi spazju scratch.

734
00:33:38,620 --> 00:33:40,411
Huwa kważi simili dawn
guys huma fuq mejda,

735
00:33:40,411 --> 00:33:42,460
u I bżonn xi kamra
biex jiġu mċaqalqa madwar fuq.

736
00:33:42,460 --> 00:33:44,170
So I m ser jingħaqdu
inti guys billi tħares

737
00:33:44,170 --> 00:33:45,960
fil-nofs tax-xellug u l-nofs tal-lemin.

738
00:33:45,960 --> 00:33:48,740
U li ovvjament jiġi l-ewwel,
nofs tax-xellug jew nofs id-dritt?

739
00:33:48,740 --> 00:33:52,710
Allura nofs tal-lemin, so ejja jimxu Luke fuq
hawn għall-pożizzjoni oriġinali Darren tal.

740
00:33:52,710 --> 00:33:57,640
U issa li jingħaqdu nofs xellug tagħhom fi,
Darren għaddej biex jimxu hemm dritt.

741
00:33:57,640 --> 00:33:59,750
>> Allura iħoss bħal kważi
effett sort bużżieqa,

742
00:33:59,750 --> 00:34:02,482
iżda algoritmu fundamentali tiegħi,
differenti ħafna dan iż-żmien.

743
00:34:02,482 --> 00:34:04,815
Imma issa s fejn l-affarijiet jiksbu
ftit annoying għaliex inti

744
00:34:04,815 --> 00:34:06,810
għandek kontrina mentalment
fejn ma I leave off.

745
00:34:06,810 --> 00:34:09,893
Stajt biss ingħaqdet in-nofsijiet magħżula,
li jfisser jien fejn fil algoritmu tiegħi?

746
00:34:09,893 --> 00:34:12,229

747
00:34:12,229 --> 00:34:13,770
I jkollhom biex issolvi l-nofs tal-lemin, right?

748
00:34:13,770 --> 00:34:15,910
>> Jekk inti kontrina, litteralment
fuq il-video, inti ser

749
00:34:15,910 --> 00:34:18,339
tara li aħna ltqajna biex dan
punt ta 'Luke u Darren

750
00:34:18,339 --> 00:34:21,370
bl-għażil ix-xellug
nofs in-nofs xellugi.

751
00:34:21,370 --> 00:34:23,430
Imbagħad aħna amalgamata dawk
nofsijiet magħżula, li

752
00:34:23,430 --> 00:34:27,941
tfisser il-pass li jmiss huwa sort l-
nofs tal-lemin tan-nofs tax-xellug.

753
00:34:27,941 --> 00:34:29,649
Kull dritt, hekk ejja
tagħmel dan aktar malajr.

754
00:34:29,649 --> 00:34:33,282
Kull dritt, sitt, jien ser titlob
inti issa huma magħżula, come fuq quddiem.

755
00:34:33,282 --> 00:34:33,990
X'hemm isem tiegħek?

756
00:34:33,990 --> 00:34:34,589
>> UDJENZA: Adriano.

757
00:34:34,589 --> 00:34:35,200
>> SPEAKER: Adriano.

758
00:34:35,200 --> 00:34:36,010
Adriano issa huwa magħżul.

759
00:34:36,010 --> 00:34:36,450
U x'hemm isem tiegħek?

760
00:34:36,450 --> 00:34:37,080
>> UDJENZA: Alex.

761
00:34:37,080 --> 00:34:38,379
>> SPEAKER: Alex issa huwa magħżul.

762
00:34:38,379 --> 00:34:40,750
Nofs Xellug, nofs tal-lemin,
x'inhu l-pass finali?

763
00:34:40,750 --> 00:34:41,250
Jingħaqdu.

764
00:34:41,250 --> 00:34:44,310
Pretty trivjali, hekk jien
ser jingħaqdu f'sitt,

765
00:34:44,310 --> 00:34:46,930
tieħu pass lura,
tmienja, tieħu pass lura.

766
00:34:46,930 --> 00:34:49,530
U issa l-avviż din hija
takeaway utli, liema

767
00:34:49,530 --> 00:34:53,930
issa huwa veru dwar in-nofs xellugi tal-
lista, irrispettivament minn kif bdejna?

768
00:34:53,930 --> 00:34:55,090
Huwa magħżula.

769
00:34:55,090 --> 00:34:57,750
>> Issa huwa ma jintgħażlux fl
l-iskema ta 'affarijiet kbar,

770
00:34:57,750 --> 00:35:00,250
iżda huwa magħżul indipendentement
tal-nofs l-ieħor.

771
00:35:00,250 --> 00:35:04,100
Issa dak pass am I fuq jekk I iżommu
rewinding kif l-istorja bdiet?

772
00:35:04,100 --> 00:35:05,680
Issa I jkollhom biex issolvi l-nofs tal-lemin.

773
00:35:05,680 --> 00:35:07,630
Allura issa aħna qed mod lura fil
il-bidu tal-istorja,

774
00:35:07,630 --> 00:35:08,921
u ejja tagħmel dan aktar malajr.

775
00:35:08,921 --> 00:35:11,320
So jien ser issolvi l-
nofs tal-lemin tal-lista sħiħa.

776
00:35:11,320 --> 00:35:13,060
X'hemm-pass li jmiss?

777
00:35:13,060 --> 00:35:15,840
Sort in-nofs xellugi tal-nofs tal-lemin.

778
00:35:15,840 --> 00:35:18,715
Sort in-nofs xellugi tal-
nofs xellug tal-nofs tal-lemin.

779
00:35:18,715 --> 00:35:19,590
U x'hemm isem tiegħek?

780
00:35:19,590 --> 00:35:20,230
>> UDJENZA: Omar.

781
00:35:20,230 --> 00:35:21,970
>> SPEAKER: Omar, pass 'il quddiem, isir.

782
00:35:21,970 --> 00:35:22,860
Nofs Xellug huwa magħżul.

783
00:35:22,860 --> 00:35:23,330
U x'hemm isem tiegħek?

784
00:35:23,330 --> 00:35:23,820
>> UDJENZA: Chris.

785
00:35:23,820 --> 00:35:25,620
>> SPEAKER: Chris, tieħu pass
quddiem, inti issa huma magħżula.

786
00:35:25,620 --> 00:35:27,010
X'hemm-pass ewlieni issa?

787
00:35:27,010 --> 00:35:27,510
Jingħaqdu.

788
00:35:27,510 --> 00:35:30,509
Allura wieħed ikun ser jingħaqdu fis-seħħ
hawn, jekk inti tista 'tieħu pass lura,

789
00:35:30,509 --> 00:35:32,930
u tlieta se
tieħu pass lura, jingħaqdu.

790
00:35:32,930 --> 00:35:38,080
Allura in-nofs xellugi tal-
nofs tal-lemin, issa huwa magħżul.

791
00:35:38,080 --> 00:35:41,747
Franchement, dan algoritmu iħoss bħal aħna
huma ħela b'mod aktar żmien minn qabel,

792
00:35:41,747 --> 00:35:44,830
imma jekk aħna ma dan fil-ħin reali, aħna ser
tara x'inhuma l-takeaways se tkun.

793
00:35:44,830 --> 00:35:47,970
Issa hawnhekk I am, id-dritt
nofs il-nofs tal-lemin,

794
00:35:47,970 --> 00:35:50,170
let me imorru quddiem u sort l-nofs tax-xellug.

795
00:35:50,170 --> 00:35:51,482
Pass 'il quddiem, x'hemm isem tiegħek?

796
00:35:51,482 --> 00:35:52,190
UDJENZA: Ramsey.

797
00:35:52,190 --> 00:35:53,210
SPEAKER: Ramsey issa huwa magħżul.

798
00:35:53,210 --> 00:35:53,570
X'hemm isem tiegħek?

799
00:35:53,570 --> 00:35:54,200
>> UDJENZA: Marina.

800
00:35:54,200 --> 00:35:57,033
>> SPEAKER: Marina issa hija magħżula bħala
ukoll, jekk inti tieħu pass 'il quddiem.

801
00:35:57,033 --> 00:36:00,690
Pass Key hawn issa qed jingħaqdu, jien
ser ġewwieni minn żewġ listi tiegħi,

802
00:36:00,690 --> 00:36:01,720
xellug u lemin.

803
00:36:01,720 --> 00:36:05,150
Ta 'ħames se jasal l-ewwel,
u seba se jidħlu jmiss.

804
00:36:05,150 --> 00:36:06,410
U għal darb'oħra, dan huwa intenzjonat.

805
00:36:06,410 --> 00:36:08,535
Il-fatt li dawn qed jieħdu
passi 'l quddiem u lura

806
00:36:08,535 --> 00:36:12,997
huwa maħsub biex jirrappreżenta dak ma nistgħux
tagħmel dan algoritmu fil-post bħala faċilment

807
00:36:12,997 --> 00:36:15,830
bħala sort bużżieqa, u sort għażla,
u sort inserzjoni fejn aħna biss

808
00:36:15,830 --> 00:36:16,960
miżmuma iskambji nies.

809
00:36:16,960 --> 00:36:19,940
I litteralment bżonn sort
tal-karta scratch li fihom

810
00:36:19,940 --> 00:36:21,827
li jpoġġu dawn folks
filwaqt I do l-amalgamazzjoni,

811
00:36:21,827 --> 00:36:23,410
u mbagħad I tista 'tpoġġi lura fil-post.

812
00:36:23,410 --> 00:36:27,260
U li ċavetta għaliex jien jużaw
riżorsa ġdida, ispazju, mhux biss ħin.

813
00:36:27,260 --> 00:36:28,270
>> OK, dan huwa aqwa.

814
00:36:28,270 --> 00:36:32,050
Nofs Xellug huwa magħżul, nofs tal-lemin hija
Issortjati, issa li ċavetta jingħaqdu pass.

815
00:36:32,050 --> 00:36:33,450
Kif am I ser jingħaqdu dan?

816
00:36:33,450 --> 00:36:35,470
Mela jekk inti ser issegwi tiegħi
naħa tax-xellug u tal-lemin,

817
00:36:35,470 --> 00:36:38,930
Jien ser punt naħa tax-xellug tiegħi
fil-nofs tax-xellug, lemin tiegħi

818
00:36:38,930 --> 00:36:42,680
fil-nofs tal-lemin, u issa I għandhom
tiddeċiedi pass pass min jgħaqqad.

819
00:36:42,680 --> 00:36:44,650
Min ovvjament jiġi l-ewwel?

820
00:36:44,650 --> 00:36:45,150
Numru wieħed.

821
00:36:45,150 --> 00:36:47,327
Allura ġejjin fuq matul hawn,
hawn pad scratch tagħna.

822
00:36:47,327 --> 00:36:49,910
Allura issa numru wieħed, u avviż
dak I ser tagħmel mal-lemin tiegħi,

823
00:36:49,910 --> 00:36:54,152
Jien ser jimxu wieħed tiegħi lemin
pass fuq għal punt numru tlieta,

824
00:36:54,152 --> 00:36:55,860
u issa I għandhom jagħmlu
l-istess deċiżjoni.

825
00:36:55,860 --> 00:36:58,387
U fil-fatt stand dritt
quddiem tal Luke hawn jekk inti tista ',

826
00:36:58,387 --> 00:36:59,720
għaliex dan huwa pad scratch tagħna.

827
00:36:59,720 --> 00:37:00,610
Hekk li jiġi jmiss?

828
00:37:00,610 --> 00:37:05,000
Għandna Luke ma numru tnejn
jew Chris bin-numru tlieta.

829
00:37:05,000 --> 00:37:07,460
Ovvjament Luqa, numru
tnejn, sabiex inti jiġu hawn.

830
00:37:07,460 --> 00:37:11,270
>> Iżda naħa tax-xellug tiegħi issa se
jkun inkrementat punt fuq Darren,

831
00:37:11,270 --> 00:37:15,160
u hawn l-muftieħ tieħu bogħod ma
tingħaqad, jien ser iżommu tagħmel dan,

832
00:37:15,160 --> 00:37:17,340
ovvjament, jekk inti xorta
tal jsegwu l-loġika.

833
00:37:17,340 --> 00:37:19,670
Iżda l-idejn tiegħi huma qatt
se jmorru lura,

834
00:37:19,670 --> 00:37:23,861
li jfisser jien biss qatt jiċċaqilqu għal
fuq ix-xellug proċess li qed jingħaqdu tiegħi,

835
00:37:23,861 --> 00:37:26,360
u li għaddej biex jkun kruċjali għas-
analiżi tagħna fi ftit mument.

836
00:37:26,360 --> 00:37:27,859
>> Allura issa ejja finitura dan up malajr.

837
00:37:27,859 --> 00:37:31,650
Allura tlieta jiġi jmiss,
imbagħad erba jiġi jmiss,

838
00:37:31,650 --> 00:37:38,750
u issa ħamsa li jmiss tidħol, allura sitta,
u seba ', u mbagħad finalment tmienja.

839
00:37:38,750 --> 00:37:42,960
Iħoss bħall-algoritmu slowest
s'issa, iżda mhux jekk aħna fil-fatt

840
00:37:42,960 --> 00:37:45,510
run fl-istess tip
tal-veloċità arloġġ, hekk li

841
00:37:45,510 --> 00:37:48,106
jitkellmu, bl-istess
timmarka arloġġ bħal qabel.

842
00:37:48,106 --> 00:37:48,605
Għaliex?

843
00:37:48,605 --> 00:37:51,100
Well, Ejja tagħti
tħares lejn ir-riżultat aħħari.

844
00:37:51,100 --> 00:37:56,990
>> Ejja ħa mmorru lura hawn, let me
pull up dimostrazzjoni viżwalment

845
00:37:56,990 --> 00:37:59,030
ta 'dak li aħna biss għamlet.

846
00:37:59,030 --> 00:38:06,110
Zooming fil hawn, fuq din
paġna hawn, javżak Firefox

847
00:38:06,110 --> 00:38:08,200
li aħna rridu li kju
up f'din il-kaxxa, ejja

848
00:38:08,200 --> 00:38:11,260
jgħidu sort bużżieqa, li magħhom
aħna qed issa sew familjari,

849
00:38:11,260 --> 00:38:14,130
sort għażla, li hija ieħor
pjuttost wieħed sempliċi,

850
00:38:14,130 --> 00:38:18,250
u issa lum sort jingħaqdu, li
se jkun jispiċċa climactic tagħna.

851
00:38:18,250 --> 00:38:21,530
Ir-raġuni hija ħadet tant itwal
hawn mal-bnedmin u lili verbalment hija,

852
00:38:21,530 --> 00:38:23,480
ovvjament, jien tispjega kull pass.

853
00:38:23,480 --> 00:38:26,920
Imma jekk inti sempliċiment tesegwixxi dan, ħafna
bħal għamilna sort bużżieqa u l-għażla

854
00:38:26,920 --> 00:38:30,890
sort mhux biss viżwalment, watch
kemm kemm aktar effiċjenti

855
00:38:30,890 --> 00:38:33,330
dan leveraging ta
diviżjoni u conquering

856
00:38:33,330 --> 00:38:39,150
jistgħu jiġu meta applikati għal sett ta 'dejta li l-
lanqas daqs tmien, iżda anke ħafna,

857
00:38:39,150 --> 00:38:39,970
ħafna akbar.

858
00:38:39,970 --> 00:38:44,585
I jagħtuk jingħaqdu sort, ġenb
ġenb ma 'dawn algoritmi oħra.

859
00:38:44,585 --> 00:38:56,364

860
00:38:56,364 --> 00:38:58,530
Dan huwa se tikseb uġigħ
malajr, u għat-tmiem

861
00:38:58,530 --> 00:39:00,890
mhuwiex partikolarment climactic,
huma biss jispiċċaw magħżula.

862
00:39:00,890 --> 00:39:05,280
Iżda l-muftieħ jieħdu bogħod hija li
ħarsa kif ħafna aktar mgħaġġla jingħaqdu sort

863
00:39:05,280 --> 00:39:08,110
kien, sakemm inti taħseb jien
biss tip ta 'messing miegħek.

864
00:39:08,110 --> 00:39:13,100
Jekk nagħmlu dan finali darba,
ejja rikarigu dan, ejja mmorru lura

865
00:39:13,100 --> 00:39:14,960
u jagħżlu sort bużżieqa,
u biss għall kicks,

866
00:39:14,960 --> 00:39:17,330
ejja jagħżlu inserzjoni
sort, biss għal miżura tajba.

867
00:39:17,330 --> 00:39:20,020
U din id-darba mill-ġdid, ejja
jagħżlu sort jingħaqdu u ejja

868
00:39:20,020 --> 00:39:21,595
tmexxi effettivament dawn ġenb ma 'ġenb.

869
00:39:21,595 --> 00:39:24,140

870
00:39:24,140 --> 00:39:26,930
>> U m'humiex, fil-fatt, fluke.

871
00:39:26,930 --> 00:39:31,140
Dak li stajt effettivament isir huwa stajt
maqsum input tiegħi fil nofs, għal darb'oħra,

872
00:39:31,140 --> 00:39:32,240
u għal darb'oħra, u għal darb'oħra.

873
00:39:32,240 --> 00:39:35,590
U hemm biss hekk bosta drabi inti tista '
jaqsam input tiegħek fis nofsijiet, xellug

874
00:39:35,590 --> 00:39:36,240
u lemin.

875
00:39:36,240 --> 00:39:39,425
X'hemm-formula li aħna tibqa 'tara
li jiddeskrivi l-diviżjoni fil nofs

876
00:39:39,425 --> 00:39:41,050
għal darb'oħra, u għal darb'oħra, u għal darb'oħra, u għal darb'oħra?

877
00:39:41,050 --> 00:39:41,890
>> UDJENZA: Log n.

878
00:39:41,890 --> 00:39:42,760
>> SPEAKER: Log n.

879
00:39:42,760 --> 00:39:46,300
Iżda mbagħad hemm waħda pass ewlieni ieħor,
dan algoritmu mhuwiex log n passi.

880
00:39:46,300 --> 00:39:48,992
Jekk kienu log biss n-passi,
aħna se tkun l-istess problema

881
00:39:48,992 --> 00:39:51,200
bħal qabel fejn ma nistgħux inkunu
żgur li kollox magħżula.

882
00:39:51,200 --> 00:39:54,480
Inti għandek minimament tħares lejn elementi n
biex tkun żgur n elementi huma magħżula,

883
00:39:54,480 --> 00:39:55,950
inkella huwa qabża ta 'fidi.

884
00:39:55,950 --> 00:39:59,810
>> Allura huwa log minimament n passi, iżda
dak dwar dan il-pass ewlieni amalgamazzjoni

885
00:39:59,810 --> 00:40:04,370
fejn I ingħaqdet nofs tax-xellug tiegħi u lemin
nofs u mixi madwar l-istadju?

886
00:40:04,370 --> 00:40:06,980
Kemm passi huwa li biex jingħaqdu?

887
00:40:06,980 --> 00:40:10,150
Huwa n, imma jien ma biss
jingħaqdu l-ħin finali.

888
00:40:10,150 --> 00:40:15,089
Fuq kull wieħed minn dawk is-sejħiet nested, fuq kull
ta 'dawk tgħaqqad nested, I still magħżula.

889
00:40:15,089 --> 00:40:18,380
I amalgamata dawn iż-żewġ guys, allura dawn iż-żewġ
guys, allura dawn iż-żewġ guys u ibqa 'sejjer hekk.

890
00:40:18,380 --> 00:40:19,955
>> So I ma jingħaqdu mill-ġdid, u għal darb'oħra.

891
00:40:19,955 --> 00:40:20,580
Kif ħafna drabi?

892
00:40:20,580 --> 00:40:23,510
Hekk kull darba I maqsuma l-
lista fil nofs, I ma jingħaqdu.

893
00:40:23,510 --> 00:40:25,460
Aqsam il-lista fil nofs, do jingħaqdu.

894
00:40:25,460 --> 00:40:28,570
Mela jekk tiddividi l-lista
jista 'jsir drabi log n,

895
00:40:28,570 --> 00:40:33,880
u l-amalgamazzjoni finalment jieħu n
passi, dak li jista 'jkun issa l' fuq

896
00:40:33,880 --> 00:40:37,000
marbuta fuq it-tmexxija
żmien ta 'algoritmu tagħna?

897
00:40:37,000 --> 00:40:37,980
n log n.

898
00:40:37,980 --> 00:40:40,560
>> U fil-fatt, dan huwa dak
konna miksuba hawn.

899
00:40:40,560 --> 00:40:44,650
Allura l-jħossu li inti tara viżwalment meta
dawk it-tliet affarijiet jimxu ma 'ġenb xulxin

900
00:40:44,650 --> 00:40:47,930
hija n kwadrat kontra n
kwadrat kontra log n n.

901
00:40:47,930 --> 00:40:51,010
Liema fundamentalment Ser naraw,
mhux biss illum iżda fil-futur,

902
00:40:51,010 --> 00:40:52,760
hija ħafna, ħafna aktar mgħaġġla.

903
00:40:52,760 --> 00:40:56,010
A round ta 'applause għal dawn guys,
I se jippremjahom ma blalen istress.

904
00:40:56,010 --> 00:41:00,260
Ejja jaggorna hawn illum, u
aħna ser tara inti nhar it-Tnejn.

905
00:41:00,260 --> 00:41:02,255